前段时间一直在看前段，准备用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
总的来说，顺序表和链表时间复杂度相差不多。由于顺序表需要存储时需要连续的内存空间，而链表不需要，所以如果存储大批量的数据的时间或者没有足够连续的内存空间时，采用链表存储。因为链表不仅要存储节点的值，还要存储下个节点的地址（链条）。
