链表 [Linked List]的基本结构
链表 [Linked List]：链表是由一组不必相连的内存结构 ，按特定的顺序链接在一起的抽象数据类型。
注意：
- 不必相连意味着可以连续也可以不连续
- 内存结构可以理解为节点
为什么需要链表？链表有什么优点？
如果你还有印象的话，list 在头部进行插入是个相当耗时的操作（需要把后边的元素一个一个挪个位置）。假如你需要频繁在数组两头增删，list 就不太合适。 链式结构将摆脱这个缺陷。当然了链式结构本身也有缺陷，比如你不能像数组一样随机根据下标访问，你想查找一个元素只能老老实实从头遍历。
链式表可以分为三类
单链表、双向链表、循环链表的结构如下图：
单链表
单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构（链尾除外），内存结构由数据域和 Next 指针域组成。
注意：
- Data 数据 + Next 指针，组成一个单链表的内存结构 ；
- 第一个内存结构称为 链头，最后一个内存结构称为 链尾；
- 链尾的 Next 指针设置为 None [指向空]；
- 单链表的遍历方向单一，只能从链头一直遍历到链尾
单链表操作图示
单链表（Singly Linked List）在Python中的实现
#定义节点（Node） class Node(object): def __init__(self,value=None,next=None): self.value,self.next=value, next #定义单链表(Singly Linked List): class LinkedList(object): #初始化四个要素 def __init__(self,maxsize=None): self.maxsize=maxsize #最大容量设置为None，这样单链表可以扩展到无限大 self.length=0 #长度先设置为0，后面进行具体操作，如append时，长度需要更新 self.root=Node() #根节点设置为一个空节点 self.tailnode=None #链尾节点先设置为None，后面进行具体操作，如append时，尾节点需要更新 #获得链表的长度 def __len__(self): return self.length #在链尾追加一个元素 def append(self,value): if self.maxsize is not None and len(self)>=self.maxsize: raise Exception("LinkedList is Full") #如果超过了规定的最大容量，抛出异常，表示已经满了 node=Node(value) #构造一个新节点 tailnode=self.tailnode #读取尾节点 if tailnode is None: #如果尾节点为空，说明只有根节点；此时只需把根节点指向把新节点 self.root.next=node else: #如果尾节点不为空，将尾节点指向新节点 tailnode.next=node self.tailnode=node #因为我们添加了新节点在链表的最后，需要把链表的尾节点更新为新节点 self.length+=1 #链表的长度需要增加1 #在链头追加一个元素 def appendleft(self,value): if self.maxsize is not None and len(self) >= self.maxsize: raise Exception('LinkedList is Full') node = Node(value) #构造一个新节点 if self.tailnode is None: # 如果原链表为空，插入第一个元素需要设置 tailnode self.tailnode = node headnode = self.root.next #读取头节点 self.root.next = node #头节点前插入现节点 node.next = headnode #现节点指向原来的头节点 self.length += 1 #长度增加1 #遍历第一步：定义遍历的方法，遍历从head节点到tail节点 def iter_node(self): currnode=self.root.next #从第一个节点开始遍历，第一个节点是根节点指向的节点 while currnode is not self.tailnode: #只要该节点不是尾结点，就生成这个节点 yield currnode currnode=currnode.next #往后不断更新浏览下一个节点 if currnode is not None: yield currnode #最后，尾节点也需要生成出来 #遍历第二步：已经获取了节点，接下来要获取每一个节点的值 def __iter__(self): for node in self.iter_node(): yield node.value #删除一个元素 def remove(self,value): prevnode=self.root #定义要删除元素的前一个节点，这个节点会被不断更新, 从根节点开始 for node in self.iter_node(): if node.value==value: #如果找到要删除的节点 prevnode.next=node.next #前一个节点跳过要删除的节点，直接连到下一个节点 #注意，如果要删除的是尾节点，需要更新尾节点 if node is self.tailnode: if prevnode is self.root: #如果链表只有尾节点一个节点，删除之后，尾节点设为空 self.tailnode=None else: self.tailnode=prevnode #如果链表除了尾节点还有其他节点，删除之后，尾节点设为要删除节点的前一个节点 del node #删掉节点 self.length-=1 #长度缩短1 return 1 #找到要删除的节点，输出1 else: prevnode=node #如果没找到要删除的节点，前一个节点更新为当前节点， 继续找 return -1 #从头到尾都找不到要删除的节点，输出-1 #查找一个节点，返回序号，从 0 开始 def find(self,value): index=0 #序号初始设为零 for node in self.iter_node(): if node.value==value: #找到后，返回序号 return index else: index+=1 #这一轮没找到，序号加一，继续找 return -1 #从头到尾都没找到，返回－1 #删除第一个链表节点 def popleft(self): if self.root.next is None: raise Exception('pop from empty LinkedList') #如果第一个节点为空，报错 headnode = self.root.next #头结点为根节点后面的节点 self.root.next = headnode.next #跳过头结点 self.length -= 1 #长度缩短1 value = headnode.value #取原头节点的值 if headnode is self.tailnode:#如果头节点就是尾节点，更新尾节点为空 self.tailnode=None del headnode #删掉头节点 return value #pop最后要返回的是值 #清空链表 def clear(self): for node in self.iter_node(): del node self.root.next=None self.length=0 self.tailnode=None #反转链表 def reverse(self): prevnode=None #定义前一个节点，之后要把前一个节点反转成后一个节点 currnode=self.root.next #从头节点开始，一个一个反转 self.tailnode=currnode #更新尾节点 while currnode: nextnode=currnode.next #取下一个节点,因为下一步就要更新下一个节点了 currnode.next=prevnode #下一个节点更新为前一个节点,完成现节点前后的反转 if nextnode is None: #遍历到链表的末尾，最后一个反转的是前节点，现节点并没有被反转。 self.root.next=currnode #需要反转现节点到链表的头。 prevnode=currnode #前节点往后挪一个位置 currnode=nextnode #现节点往后挪一个位置 #测试 def test_linked_list(): ll = LinkedList() ll.append(0) ll.append(1) ll.append(2) ll.append(3) assert len(ll) == 4 assert ll.find(2) == 2 assert ll.find(-1) == -1 assert ll.remove(0) == 1 assert ll.remove(10) == -1 assert ll.remove(2) == 1 assert len(ll) == 2 assert list(ll) == [1, 3] assert ll.find(0) == -1 ll.appendleft(0) assert list(ll) == [0, 1, 3] assert len(ll) == 3 headvalue = ll.popleft() assert headvalue == 0 assert len(ll) == 2 assert list(ll) == [1, 3] assert ll.popleft() == 1 assert list(ll) == [3] ll.popleft() assert len(ll) == 0 assert ll.tailnode is None ll.clear() assert len(ll) == 0 assert list(ll) == [] def test_linked_list_remove(): ll = LinkedList() ll.append(3) ll.append(4) ll.append(5) ll.append(6) ll.append(7) ll.remove(7) print(list(ll)) def test_single_node(): ll = LinkedList() ll.append(0) ll.remove(0) ll.appendleft(1) assert list(ll) == [1] def test_linked_list_reverse(): ll = LinkedList() n = 10 for i in range(n): ll.append(i) ll.reverse() assert list(ll) == list(reversed(range(n))) def test_linked_list_append(): ll = LinkedList() ll.appendleft(1) ll.append(2) assert list(ll) == [1, 2] if __name__ == '__main__': test_single_node() test_linked_list() test_linked_list_append() test_linked_list_reverse()