单向链表

单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。

单链表的示意图如下：

231244591436996.jpg

表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，...

单链表删除节点

231246130639479.jpg

删除"节点30" 删除之前："节点20" 的后继节点为"节点30"，而"节点30" 的后继节点为"节点40"。 删除之后："节点20" 的后继节点为"节点40"。

单链表添加节点

231246431888916.jpg

在"节点10"与"节点20"之间添加"节点15" 添加之前："节点10" 的后继节点为"节点20"。 添加之后："节点10" 的后继节点为"节点15"，而"节点15" 的后继节点为"节点20"。

单链表的特点是：节点的链接方向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很高。

#!/usr/bin/env python3
# -*- encoding:utf-8 -*-
"""
@author: jjcoder
@file: SingleLinkList.py
@time: 9/2/1910:56 PM
"""

class Node(object):
    """
    节点类
    表元素域elem用来存放具体的数据
    链接域next用来存放下一个节点的位置
    变量p指向链表的头节点位置,从p出发能找到表中的任意节点
    链表: 如果内存中没有一块完整的内存满足我们需要的存储(顺序表),我们可以使用链表充分利用内存空间,同样付出的代价也是高于顺序表的.
    """

    def __init__(self, elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    def __init__(self, node=None):
        self.__head = node

    # is_empty()链表是否为空
    def is_empty(self):
        return self.__head is None

    # length()链表的长度
    def length(self):
        # cur游标,用来移动遍历节点
        # 这里注意如果是空链表的话,也是满足条件的,但是如果count的初始值是1,就需要进行判空操作.
        cur = self.__head
        # count用来记录数量
        count = 0
        while cur is not None:
            # 这里先加1,在开始移动游标
            count += 1
            cur = cur.next
        return count

    # travel()遍历整个链表
    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.elem, end=' ')
            print()
            cur = cur.next

    # add(item)头部插入元素
    def add(self, item):
        node = Node(item)
        # 这里如果原有的链表是空链表,也是满足效果的.
        # 为了防止后面的节点被丢弃,需要先将新的节点的next指向head指向的节点
        node.next = self.__head
        self.__head = node

    # append(item)链表尾部插入元素
    def append(self, item):
        # 通过传入的元素构建一个node节点
        node = Node(item)
        # 这里需要判断链表是否为空
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            # 这里需要游标走到最后一个节点停止,软后将cur.next指向node就可以了,注意与上面计算链表长度做对比.
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    # insert(pos, item)指定位置插入元素
    def insert(self, pos, item):
        # 这里的pos是从0开始的
        node = Node(item)
        # 如果pos<=0理解为在头部插入元素,不支持反向插入
        if pos <= 0:
            self.add(item)
        # 如果pos>length() - 1, 就理解为在尾部插入元素,但是这里需要注意如果pos=length - 1,并不是在尾部插入元素,而是在最后面元素的前一位插入.
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self.__head
            # for i in range(pos - 1):  # 这种方式也是可以的
            count = 0
            while count < (pos - 1):
                # 为防止后面的节点被丢弃,先将新节点的next区域指向cur的next区域,然后在将cur的next指向新节点
                # 这里也可以定义一个pre游标,为了方便继续使用cur游标
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # remove(item)删除节点
    def remove(self, item):
        cur = self.__head
        pre = None
        # 如果是空链表也是满足条件的
        while cur is not None:
            if cur.elem == item:
                # 如果删除的元素恰好是首节点
                # 如果链表只有一个节点,下面的操作也满足
                # 先判断此节点是否是头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    # 如果删除的节点是尾节点,下面也是可以满足条件的
                    pre.next = cur.next
                break
            else:
                # 下面这两行代码顺序不能变
                pre = cur
                cur = cur.next

    # search(item)查找节点是否存在
    def search(self, item):
        cur = self.__head
        # 如果有相同的元素一样,这里不做过多的判断,只是需要找到给定的元素就可以了.
        # 特殊情况:如果链表是一个空链表,也是满足情况的.
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

single_obj = SingleLinkList()

单链表的特点

链表增删元素的时间复杂度为O(1) 查找一个元素的时间复杂度为 O(n); 单链表不用像数组那样预先分配存储空间的大小，避免了空间浪费 单链表不能进行回溯操作，如：只知道链表的头节点的时候无法快读快速链表的倒数第几个节点的值。