双链表 / Doubly Linked List
目录
双链表和单链表的不同之处在于，双链表需要多增加一个域（C语言），即在Python中需要多增加一个属性，用于存储指向前一个结点的信息。
Doubly linked list:
node_1 <---> node_2 <---> node_3
完整代码
1 from linked_list import LinkedList, test 2 3 4 class NodeDual: 5 def __init__(self, val=None, nxt=None, pre=None): 6 self.value = val 7 self.next = nxt 8 self.prev = pre 9 10 def __str__(self): 11 return '<NodeDual, prev=%s, value=%s, next=%s>' % (self.prev.value if self.prev else self.prev, 12 self.value, 13 self.next.value if self.next else self.next) 14 15 16 class DoublyLinkedList(LinkedList): 17 """ 18 Doubly linked list: 19 node_1 <---> node_2 <---> node_3 20 """ 21 def __str__(self): 22 def _traversal(self): 23 node = self.header 24 while node and node.next: 25 yield node 26 node = node.next 27 yield node 28 return '<-> '.join(map(lambda x: str(x), _traversal(self))) 29 30 def init(self, iterable=()): 31 if not iterable: 32 return 33 self.header = NodeDual(iterable[0]) # header value 34 pre = None 35 node = self.header 36 for i in iterable[1:]: # add all node 37 node.prev = pre 38 node.next = NodeDual(i) 39 pre = node 40 node = node.next 41 node.prev = pre 42 43 def find_previous(self, item): 44 return self.find(item).prev 45 46 def delete(self, item): 47 pre = self.find_previous(item) 48 if pre: 49 pre.next = pre.next.next 50 pre.next.prev = pre 51 52 def insert(self, item, index): 53 if abs(index) > self.length: 54 return 55 if index < 0: 56 self.insert(item, self.length+index+1) 57 return 58 elif index == 0: 59 self.insert(self.header.value, 1) 60 self.header.value = item 61 return 62 node = self.header 63 i = 0 64 while i < index-1: 65 node = node.next 66 i += 1 67 n = node.next 68 node.next = NodeDual(item, nxt=n, pre=node) 69 if n: 70 n.prev = node.next 71 72 73 if __name__ == '__main__': 74 test(DoublyLinkedList())
分段解释
双链表可以的基本特性与单链表相同，因此可以继承单链表。首先导入前面写好的单链表类和测试函数。
1 from linked_list import LinkedList, test
然后定义一个双向结点，包含前后两个属性，用于存放前后结点的信息。同时重定义__str__方法，在显示结点时显示该结点的前后结点及自身值，从而方便查看。
1 class NodeDual: 2 def __init__(self, val=None, nxt=None, pre=None): 3 self.value = val 4 self.next = nxt 5 self.prev = pre 6 7 def __str__(self): 8 return '<NodeDual, prev=%s, value=%s, next=%s>' % (self.prev.value if self.prev else self.prev, 9 self.value, 10 self.next.value if self.next else self.next)
定义双链表类，基类为单链表，构造函数可以使用单链表的构造函数。
1 class DoublyLinkedList(LinkedList): 2 """ 3 Doubly linked list: 4 node_1 <---> node_2 <---> node_3 5 """ 6 def __str__(self): 7 def _traversal(self): 8 node = self.header 9 while node and node.next: 10 yield node 11 node = node.next 12 yield node 13 return '<-> '.join(map(lambda x: str(x), _traversal(self)))
init方法，与单链表不同的地方在于，添加结点时需要同时修改结点的前后属性（引用指针）。
1 def init(self, iterable=()): 2 if not iterable: 3 return 4 self.header = NodeDual(iterable[0]) # header value 5 pre = None 6 node = self.header 7 for i in iterable[1:]: # add all node 8 node.prev = pre 9 node.next = NodeDual(i) 10 pre = node 11 node = node.next 12 node.prev = pre
find_previous方法，查找前一个结点的方法将变得很简单，只需要找到需要找的结点后，通过结点获取前一个结点即可。
1 def find_previous(self, item): 2 return self.find(item).prev
删除和插入类似于单链表的思路，只不过需要多处理一个前驱结点引用。
1 def delete(self, item): 2 pre = self.find_previous(item) 3 if pre: 4 pre.next = pre.next.next 5 pre.next.prev = pre 6 7 def insert(self, item, index): 8 if abs(index) > self.length: 9 return 10 if index < 0: 11 self.insert(item, self.length+index+1) 12 return 13 elif index == 0: 14 self.insert(self.header.value, 1) 15 self.header.value = item 16 return 17 node = self.header 18 i = 0 19 while i < index-1: 20 node = node.next 21 i += 1 22 n = node.next 23 node.next = NodeDual(item, nxt=n, pre=node) 24 if n: 25 n.prev = node.next
同样利用测试单链表的函数对双链表进行测试，
1 if __name__ == '__main__': 2 test(DoublyLinkedList())
得到结果
Show linked list: None Init linked list: <NodeDual, prev=None, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=8><-> <NodeDual, prev=xd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=None> Insert element: <NodeDual, prev=None, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=xxd><-> <NodeDual, prev=xd, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=None> Append element: <NodeDual, prev=None, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=xxd><-> <NodeDual, prev=xd, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=None> Find element: xd Find previous element: 6 Delete element: <NodeDual, prev=None, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xxd><-> <NodeDual, prev=6, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=None> Find element not exist: None Insert element to header: <NodeDual, prev=None, value=cc, next=1><-> <NodeDual, prev=cc, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xxd><-> <NodeDual, prev=6, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=None> Clear linked list: None Current length: 0 Is empty: True
循环双链表类似于双链表，但是将表的头尾两个结点相连，形成了一个循环链表结构，即头结点的前一个结点为尾结点，尾结点的下一个结点为头结点。
Doubly linked list with loop: ________________________________________________________ | | <===> node_1 <---> node_2 <---> node_3 <---> node_4 <===> |________________________________________________________|
首先导入需要的结点和双链表类以及测试函数，
1 from linked_list_doubly import NodeDual, DoublyLinkedList, test
接着定义循环双链表类，对链表的显示输出同样要先遍历链表，而这里的遍历函数需要额外增加一个判断条件，即当再次遇到头结点时，遍历停止，否则将无限循环遍历下去。
1 class DoublyLinkedListLoop(DoublyLinkedList): 2 """ 3 Doubly linked list with loop: 4 ________________________________________________________ 5 | | 6 <===> node_1 <---> node_2 <---> node_3 <---> node_4 <===> 7 |________________________________________________________| 8 """ 9 def __str__(self): 10 def _traversal(self): 11 node = self.header 12 while node and node.next is not self.header: 13 yield node 14 node = node.next 15 yield node 16 return '<-> '.join(map(lambda x: str(x), _traversal(self)))
循环双链表的生成函数比双链表多了一个步骤，即将双链表的头尾结点相接。
1 def init(self, iterable=()): 2 if not iterable: 3 return 4 self.header = NodeDual(iterable[0]) # header value 5 pre = None 6 node = self.header 7 for i in iterable[1:]: # add all node 8 node.prev = pre 9 node.next = NodeDual(i) 10 pre = node 11 node = node.next 12 node.prev = pre 13 14 node.next = self.header 15 self.header.prev = node
用于获取表长度的属性方法同样需要更改，增加一个头结点判断来终止循环遍历。
1 @property 2 def length(self): 3 if self.header is None: 4 return 0 5 node = self.header 6 i = 1 7 while node.next is not self.header: 8 node = node.next 9 i += 1 10 return i
两个查找函数也是同样需要加入头结点判断来停止循环。
1 def find(self, item): 2 node = self.header 3 while node.next is not self.header and node.value != item: 4 node = node.next 5 if node.value == item: 6 return node 7 return None 8 9 def find_previous(self, item): 10 node = self.header 11 while node.next is not self.header and node.next.value != item: 12 node = node.next 13 if node.next is not self.header and node.next.value == item: 14 return node 15 return None
最后用测试函数进行测试，
if __name__ == '__main__': test(DoublyLinkedListLoop())
测试结果为
Show linked list: None Init linked list: <NodeDual, prev=9, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=8><-> <NodeDual, prev=xd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=1> Insert element: <NodeDual, prev=9, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=xxd><-> <NodeDual, prev=xd, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=1> Append element: <NodeDual, prev=10, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xd><-> <NodeDual, prev=6, value=xd, next=xxd><-> <NodeDual, prev=xd, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=1> Find element: xd Find previous element: 6 Delete element: <NodeDual, prev=10, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xxd><-> <NodeDual, prev=6, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=1> Find element not exist: None Insert element to header: <NodeDual, prev=10, value=cc, next=1><-> <NodeDual, prev=cc, value=1, next=2><-> <NodeDual, prev=1, value=2, next=3><-> <NodeDual, prev=2, value=3, next=4><-> <NodeDual, prev=3, value=4, next=5><-> <NodeDual, prev=4, value=5, next=6><-> <NodeDual, prev=5, value=6, next=xxd><-> <NodeDual, prev=6, value=xxd, next=8><-> <NodeDual, prev=xxd, value=8, next=9><-> <NodeDual, prev=8, value=9, next=10><-> <NodeDual, prev=9, value=10, next=cc> Clear linked list: None Current length: 0 Is empty: True
相关阅读
1. 单链表