双链表 / Doubly Linked List
目录
1 双链表
双链表和单链表的不同之处在于，双链表需要多增加一个域（C语言），即在Python中需要多增加一个属性，用于存储指向前一个结点的信息。
Doubly linked list:
node_1 <---> node_2 <---> node_3
完整代码
from linked_list import LinkedList, test class NodeDual:
def __init__(self, val=None, nxt=None, pre=None):
self.value = val
self.next = nxt
self.prev = pre def __str__(self):
return '<NodeDual, prev=%s, value=%s, next=%s>' % (self.prev.value if self.prev else self.prev,
self.value,
self.next.value if self.next else self.next) class DoublyLinkedList(LinkedList):
"""
Doubly linked list:
node_1 <---> node_2 <---> node_3
"""
def __str__(self):
def _traversal(self):
node = self.header
while node and node.next:
yield node
node = node.next
yield node
return '<->\n'.join(map(lambda x: str(x), _traversal(self))) def init(self, iterable=()):
if not iterable:
return
self.header = NodeDual(iterable[0]) # header value
pre = None
node = self.header
for i in iterable[1:]: # add all node
node.prev = pre
node.next = NodeDual(i)
pre = node
node = node.next
node.prev = pre def find_previous(self, item):
return self.find(item).prev def delete(self, item):
pre = self.find_previous(item)
if pre:
pre.next = pre.next.next
pre.next.prev = pre def insert(self, item, index):
if abs(index) > self.length:
return
if index < 0:
self.insert(item, self.length+index+1)
return
elif index == 0:
self.insert(self.header.value, 1)
self.header.value = item
return
node = self.header
i = 0
while i < index-1:
node = node.next
i += 1
n = node.next
node.next = NodeDual(item, nxt=n, pre=node)
if n:
n.prev = node.next if __name__ == '__main__':
test(DoublyLinkedList())
分段解释
双链表可以的基本特性与单链表相同，因此可以继承单链表。首先导入前面写好的单链表类和测试函数。
from linked_list import LinkedList, test
然后定义一个双向结点，包含前后两个属性，用于存放前后结点的信息。同时重定义__str__方法，在显示结点时显示该结点的前后结点及自身值，从而方便查看。
class NodeDual:
def __init__(self, val=None, nxt=None, pre=None):
self.value = val
self.next = nxt
self.prev = pre def __str__(self):
return '<NodeDual, prev=%s, value=%s, next=%s>' % (self.prev.value if self.prev else self.prev,
self.value,
self.next.value if self.next else self.next)
定义双链表类，基类为单链表，构造函数可以使用单链表的构造函数。
class DoublyLinkedList(LinkedList):
"""
Doubly linked list:
node_1 <---> node_2 <---> node_3
"""
def __str__(self):
def _traversal(self):
node = self.header
while node and node.next:
yield node
node = node.next
yield node
return '<->\n'.join(map(lambda x: str(x), _traversal(self)))
init方法，与单链表不同的地方在于，添加结点时需要同时修改结点的前后属性（引用指针）。
def init(self, iterable=()):
if not iterable:
return
self.header = NodeDual(iterable[0]) # header value
pre = None
node = self.header
for i in iterable[1:]: # add all node
node.prev = pre
node.next = NodeDual(i)
pre = node
node = node.next
node.prev = pre
find_previous方法，查找前一个结点的方法将变得很简单，只需要找到需要找的结点后，通过结点获取前一个结点即可。
def find_previous(self, item):
return self.find(item).prev
删除和插入类似于单链表的思路，只不过需要多处理一个前驱结点引用。
def delete(self, item):
pre = self.find_previous(item)
if pre:
pre.next = pre.next.next
pre.next.prev = pre def insert(self, item, index):
if abs(index) > self.length:
return
if index < 0:
self.insert(item, self.length+index+1)
return
elif index == 0:
self.insert(self.header.value, 1)
self.header.value = item
return
node = self.header
i = 0
while i < index-1:
node = node.next
i += 1
n = node.next
node.next = NodeDual(item, nxt=n, pre=node)
if n:
n.prev = node.next
同样利用测试单链表的函数对双链表进行测试，
if __name__ == '__main__':
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
2 循环双链表
循环双链表类似于双链表，但是将表的头尾两个结点相连，形成了一个循环链表结构，即头结点的前一个结点为尾结点，尾结点的下一个结点为头结点。
Doubly linked list with loop:
________________________________________________________
| |
<===> node_1 <---> node_2 <---> node_3 <---> node_4 <===>
|________________________________________________________|
首先导入需要的结点和双链表类以及测试函数，
from linked_list_doubly import NodeDual, DoublyLinkedList, test
接着定义循环双链表类，对链表的显示输出同样要先遍历链表，而这里的遍历函数需要额外增加一个判断条件，即当再次遇到头结点时，遍历停止，否则将无限循环遍历下去。
class DoublyLinkedListLoop(DoublyLinkedList):
"""
Doubly linked list with loop:
________________________________________________________
| |
<===> node_1 <---> node_2 <---> node_3 <---> node_4 <===>
|________________________________________________________|
"""
def __str__(self):
def _traversal(self):
node = self.header
while node and node.next is not self.header:
yield node
node = node.next
yield node
return '<->\n'.join(map(lambda x: str(x), _traversal(self)))
循环双链表的生成函数比双链表多了一个步骤，即将双链表的头尾结点相接。
def init(self, iterable=()):
if not iterable:
return
self.header = NodeDual(iterable[0]) # header value
pre = None
node = self.header
for i in iterable[1:]: # add all node
node.prev = pre
node.next = NodeDual(i)
pre = node
node = node.next
node.prev = pre node.next = self.header
self.header.prev = node
用于获取表长度的属性方法同样需要更改，增加一个头结点判断来终止循环遍历。
@property
def length(self):
if self.header is None:
return 0
node = self.header
i = 1
while node.next is not self.header:
node = node.next
i += 1
return i
两个查找函数也是同样需要加入头结点判断来停止循环。
def find(self, item):
node = self.header
while node.next is not self.header and node.value != item:
node = node.next
if node.value == item:
return node
return None def find_previous(self, item):
node = self.header
while node.next is not self.header and node.next.value != item:
node = node.next
if node.next is not self.header and node.next.value == item:
return node
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. 单链表