Python数据结构之双向链表详解
⽬录
0.学习⽬标
1.双向链表简介
1.1双向链表介绍
1.2双向链表结点类
1.3双向链表优缺点
2.双向链表实现
2.1双向链表的初始化
2.2获取双向链表长度
2.3读取指定位置元素
2.4查指定元素
2.5在指定位置插⼊新元素
2.6删除指定位置元素
2.7其它⼀些有⽤的操作
3.双向链表应⽤
3.1双向链表应⽤⽰例
3.2利⽤双向链表基本操作实现复杂操作
0. 学习⽬标
单链表只有⼀个指向直接后继的指针来表⽰结点间的逻辑关系，因此可以⽅便的从任⼀结点开始查其后继结点，但要前驱结点则⽐较困难，双向链表是为了解决这⼀问题，其使⽤两个指针表⽰结点间的逻辑关系。在上⼀节中我们已经讨论了单链表及其相关操作的实现，本节中我们将重点讨论双向链表及其相关操作的实现。
通过本节学习，应掌握以下内容：
双向链表的基本概念及其优缺点
双向链表基本操作的实现
利⽤双向链表的基本操作实现复杂算法
1. 双向链表简介
1.1 双向链表介绍
双向链表 (doubly linked list) 与单链表相似，同样使⽤结点和指针的相关概念，属于顺序表的链式存储结构，单链表和双向链表的唯⼀区别在于双向链表是⽤两个指针表⽰结点间的逻辑关系，增加了⼀个指向其直接前驱的指针域，这样形成的链表有两条不同⽅向的链——前驱链和后继链，因此称为双向链表，或称为双链表。
1.2 双向链表结点类
在双向链表中，根据已知结点查其直接前驱结点可以与查其直接后继结点⼀样⽅便。与单链表相同，
双向链表同样可以分为带有头结点和不带头结点两类，本节仅讨论带头结点的双向链表。双向链表的结点⽰意图如下所⽰，每个结点都有两个指针——指向直接后继的指针 next 和指向直接前驱的指针 previous：
⽤ Python 实现双向链表结点类如下：
class Node:
def __init__(self, data=None):
self.data = data
< = None
self.previous = None
def __str__(self):
return str(self.data)
previous 变量指向直接前驱结点，⽽ next 变量保留对直接后继结点的引⽤，⽽ data 变量⽤于存储数据，
重载 __str__ ⽅法⽤于便于打印结点对象。
1.3 双向链表优缺点
双向链表的优点在于给定双向链表中的⼀个节点，我们可以双向遍历，直接访问它的前驱结点，这样在需要查前驱的操作中，就不必再从头开始遍历整个链表，极⼤的⽅便了诸如删除结点等操作。
⽽双向链表的主要缺点如下：
每个结点需要⼀个额外的前驱指针，需要更多的空间；
结点的插⼊或删除需要更多的指针修改操作。
2. 双向链表实现
类似于单链表，接下来让我们实现⼀个带有头结点的双链表类，并⽤头指针标识链表的开头，如果你还不了解单链表，可以参考《》相关介绍。
2.1 双向链表的初始化
双向链表的初始化建⽴⼀个空的带头结点的单链表，其表长 length 初始化为 0，此时链表中没有元素结
点，只有⼀个头结点：
class DoublyLinkedList:
def __init__(self, data=None):
self.length = 0
# 初始化头结点
head_node = Node()
self.head = head_node
创建双向链表 DoublyLinkedList 对象的时间复杂度为O(1)。
NOTE：如果你还记得的话，我们也可以令 DoublyLinkedList 继承⾃在《》中实现的 SinglyLinkedList，可以极⼤的化简双向链表的实现。
2.2 获取双向链表长度
求取双向链表长度只需要重载 __len__ 从对象返回 length 的值，因此时间复杂度为O(1)：
def __len__(self):
return self.length
2.3 读取指定位置元素
双向链表中读取指定位置元素的算法与单链表完全相同，只需要使⽤后继链访问每⼀个结点即可，因此操作的复杂度同样为O(n)，接下来我们将重载 __getitem__ 操作实现读取链表指定位置元素的操作；同时，我们希望确保索引在可接受的索引范围内，否则将引发 IndexError 异常：
def __getitem__(self, index):
if index > self.length - 1 or index < 0:
raise IndexError("DoublyLinkedList assignment index out of range")
else:
count = -1
current = self.head
while count < index:
current =
count += 1
return current.data
类似的，我们也可以实现修改指定位置元素的操作，只需要重载 __setitem__ 操作，其复杂度同样为O(n)：
def __setitem__(self, index, value):
if index > self.length - 1 or index < 0:
raise IndexError("DoublyLinkedList assignment index out of range")
else:
count = -1
current = self.head
while count < index:
current =
count += 1
current.data = value
2.4 查指定元素
与单链表相同，当查指定元素时，需要设置⼀个跟踪链表结点的指针 current，令其顺着 next 域依次指向每个结点，每指向⼀个结点就判断其值是否等于指定值 value，若是则返回该结点索引；否则继续往后搜索，如果链表中⽆此元素，则引发ValueError 异常，其时间复杂度为O(n)：
def locate(self, value):
count = -1
current = self.head
while current != None and current.data != value:
count += 1
current =
if current and current.data == value:
return count
else:
raise ValueError("{} is not in sequential list".format(value))
2.5 在指定位置插⼊新元素
在指定位置插⼊新元素有两种不同的⽅法，⼀种是到待插⼊位置的结点 current，然后将待插结点插⼊ current 之前；另⼀种⽅法是到待插⼊位置结点的前驱结点 prev，然后待插结点插⼊ prev 之后，两种⽅法的操作略有不同，这⾥以第⼆种⽅法的操作为例，第⼀种⽅法的具体操作留给⼤家进⾏推导。
由于 prev 指向待插⼊位置的后继结点，因此如果插⼊位置为列表末尾，由于 = None，⽆法使⽤
(1) 在双向链表的末尾插⼊⼀个结点步骤如下：
遍历列表直到最后⼀个结点，创建新结点；
将新节点的 previous 指针指向链表的最后⼀个结点；
更新原链表最后⼀个结点的 next 指针指向新结点。
(2) 在双链表中间插⼊结点与单链表类似，但是需要更多的步骤⽤于修改指针：
⾸先遍历链表到插⼊位置的前驱结点 prev，创建新结点；
新结点的 next 指针指向要插⼊新结点位置的下⼀个节点，新结点的 previous 指针指向 prev；
插⼊位置后继节点的 previous 指向新节点，prev 结点的 next 指针指向新节点。
算法实现如下所⽰：
def insert(self, index, data):
count = 0
prev = self.head
# 判断插⼊位置的合法性
if index > self.length or index < 0:
raise IndexError("DoublyLinkedList assignment index out of range")
else:
new_node = Node(data)
while count < index:
prev =
count += 1
new_node.previous = prev
self.length += 1
:
# 链表中间插⼊结点
=
< = new_node
else:
# 链尾插⼊结点
< = new_node
2.6 删除指定位置元素
删除指定位置元素，只需要到相应位置结点 current，修改指针后，删除结点即可。需要注意的是，除
了需要将 current 的前驱结点的 next 指针指向 current 的后继节点外，如果删除的并⾮链尾元素，还需要将 current 的后继节点的 previous 指针指向current 的前驱结点：
算法实现如下所⽰：
def get_node(self, index):
"""辅助函数，⽤于根据位置返回结点"""
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
count = -1
current = self.head
while count < index:
current =
count += 1
return current
def __delitem__(self, index):
"""删除指定位置元素"""
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
current = _node(index)
if current:
=
# 如果删除的并⾮最后⼀个结点
:
self.length -= 1
del current
在插⼊和删除操作中，都是先确定操作位置，然后再进⾏插⼊和删除操作，所以其时间复杂度均为O(n)。
2.7 其它⼀些有⽤的操作
2.7.1 链表元素输出操作
将双向链表转换为字符串以便进⾏打印，使⽤ str 函数调⽤对象上的 __str__ ⽅法可以创建适合打印的字符串表⽰：
def __str__(self):
s = "["
current =
count = 0
while current != None:
count += 1
s += str(current)
current =
if count < self.length:
s += '<-->'
s += "]"
return s
2.7.2 删除指定元素
与删除指定位置元素略有不同，删除指定元素需要在链表中删除第⼀个具有与给定值相同数据元素的结点，但修改指针的操作是类似的，其时间复杂度同样为O(n)：
def del_value(self, value):
current = self.head
while current:
if current.data == value:
=
:
self.length -= 1
del current
return
else:
current =
raise ValueError("The value provided is not present!")
2.7.3 在链表尾部追加新元素
为了⽅便的在链表尾部追加新元素，可以实现函数 append：
def append(self, data):
new_node = Node(data)
current = self.head
:
current =
< = new_node
new_node.previous = current
self.length += 1
此算法的时间复杂度为O(n)，如果需要经常在链表尾部追加新元素，可以使⽤增加尾指针 tail ⽤于追踪链表的最后⼀个元素，利⽤尾指针在链表尾部追加新元素时间复杂度可以降⾄O(1)。
3. 双向链表应⽤
接下来，我们⾸先测试上述实现的双向链表，以验证操作的有效性，然后利⽤实现的基本操作来实现更复杂的算法。
3.1 双向链表应⽤⽰例
⾸先初始化⼀个链表 dllist，并在其中追加若⼲元素：
dllist = DoublyLinkedList()
# 在链表末尾追加元素
dllist.append('apple')
dllist.append('banana')
dllist.append('orange')
# 在指定位置插⼊元素
dllist.insert(0, 'grape')
dllist.insert(4, 'lemon')
我们可以直接打印链表中的数据元素、链表长度等信息：
print('双向链表 sllist 为：', dllist)
print('双向链表 sllist 长度为：', len(dllist))
print('双向链表 sllist 第0个元素为：', dllist[0])
# 修改数据元素
dllist[0] = 'pear'
del(dllist[3])
print('双向修改链表 sllist 数据后：', dllist)
以上代码输出如下：
双向链表 dllist 为： [grape<-->apple<-->banana<-->orange<-->lemon]
python index函数
双向链表 dllist 长度为： 5
双向链表 dllist 第0个元素为： grape
修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->lemon]
接下来，我们将演⽰在指定位置添加/删除元素、以及如何查指定元素等：
# 修改数据元素
dllist[0] = 'pear'
print('修改双向链表 dllist 数据后：', dllist)
dllist.insert(0, 'watermelon')
print('在位置 0 添加 watermelon 后双向链表链表 ddlist 数据：', dllist)
del(dllist[3])
print('删除位置 3 处元素后双向链表 ddlist 数据：', dllist)
dllist.append('lemon')
print('在尾部追加元素 lemon 后双向链表 ddlist 数据：', dllist)
dllist.del_value('lemon')
print('删除 lemon 后双向链表 dllist 数据：', dllist)
print('watermelon 在双向链表 dllist 中的索引为：', dllist.locate('orange'))
以上代码输出如下：
修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后双向链表链表 ddlist 数据： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
删除位置 3 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
删除 lemon 后双向链表 dllist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在双向链表 dllist 中的索引为： 3
3.2 利⽤双向链表基本操作实现复杂操作
[1] 利⽤双向链表的基本操作，合并两个双向链表：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。