python中单链表的实现

前段时间一直在看前段，准备用vue.js写一个新闻客户端。但是文章发表在简书后被禁了，😂。不想了，这几天转战python了。
我们知道，线性表分为顺序表和链表，顺序表也就是常见的数组，在python中称之为列表。关于列表的操作，python已经把我们实现好了，下面简单说说链表的实现。

节点类的实现

节点类主要包含两部分，一个为节点的值elem，另一个节点存储的地址，默认指向None

class Node(object):
    '''节点'''
    def __init__(self, elem):
        self.elem = elem
        self.next = None

链表类的实现

链表类实现的方法有判空、求长、遍历、头部添加、尾部添加、指定位置添加、删除指定元素、判断是否包含等.

class SingleLinkList(object):
    '''单链表'''

    def __init__(self, node = None): #设置默认参数
        '''头节点，设置成私有'''
        self.__head = node

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

    def length(self):
        '''链表长度'''
        # cur游标，用来移动遍历节点
        cur = self.__head
        #count记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历整个链表'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ") #换行方式。默认python为换行，加上end=" "在python3默认为空格换行。python2默认为,隔开
            cur = cur.next

    def add(self, item):
        '''链表头部添加元素，头插法 时间复杂度O(1)'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''链表尾部添加元素，尾插法 时间复杂度O(n)'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        '''指定位置添加元素 时间复杂度O(n)，顺序表为O(n) '''
        #:param pos 从0开始
        if pos < 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                pre = pre.next
                count += 1
            #当循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node


    def remove(self, item):
        '''删除节点'''
        pre = self.__head

        if pre.elem == item:
            self.__head = pre.next
        else:
            while pre.next != None:
                if pre.next.elem == item:
                    pre.next = pre.next.next
                else:
                    pre = pre.next

    def conatain(self, item):
        '''查找节点是否存在 时间复杂度O(n)'''
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

测试运行

if __name__ == "__main__":
    link_list = SingleLinkList()
    print(link_list.is_empty())
    print(link_list.length())

    link_list.append(1)

    link_list.append(2)
    link_list.add(10)
    link_list.append(3)
    link_list.append(4)

    link_list.insert(-1, 9) 

    ll.remove(10) 
    ll.remove(4)
    ll.travel()

最后说说，顺序表和链表时间复杂度的关系。如下图:

顺序表和链表时间复杂度比较.png

总的来说，顺序表和链表时间复杂度相差不多。由于顺序表需要存储时需要连续的内存空间，而链表不需要，所以如果存储大批量的数据的时间或者没有足够连续的内存空间时，采用链表存储。因为链表不仅要存储节点的值，还要存储下个节点的地址（链条）。