如何在 Python 中创建双向链表
双向链表是一种常见的数据结构，它可以在 O(1) 的时间复杂度内进行插入和删除操作。Python 中的列表虽然也具有这样的特性，但是在某些场景下，双向链表可能更加适用。本文将介绍如何在 Python 中创建双向链表，并且讨论一些需要注意的问题。
定义节点类
双向链表的节点需要记录前驱和后继节点的地址，因此我们需要先定义一个节点类。节点类的定义如下：
class Node:
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
这里我们使用了 Python 中的类来定义节点，其中 data 代表节点存储的数据，prev 和 next 分别代表前驱和后继节点的地址。在初始化节点时，我们将 prev 和 next 设为 None。
定义双向链表类
双向链表类需要记录头节点和尾节点的地址，以及链表的长度。我们可以定义一个 DoublyLinkedList 类来管理双向链表。DoublyLinkedList 类的定义如下：
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
在初始化 DoublyLinkedList 类时，我们将 head 和 tail 设为 None，并且将链表长度设为 0。
实现插入操作
在双向链表中，插入操作可以分为三种情况：在链表头部插入、在链表尾部插入和在链表中间插入。我们分别来实现这三种情况下的插入操作。
3.1 在链表头部插入
在链表头部插入一个节点时，需要将新节点的 next 设为原头节点，将原头节点的 prev 设为新节点，然后将新节点设为新的头节点。插入操作的代码如下：
def insert_at_head(self, data):
new_node = Node(data)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
我们首先创建一个新节点 new_node，并将其 next 设为原头节点。如果链表长度为 0，说明原链表为空，此时我们将新节点设为头节点和尾节点。否则，我们将原头节点的 prev 设为新节点，然后将新节点设为新的头节点。最后，链表长度加 1。
3.2 在链表尾部插入
在链表尾部插入一个节点时，需要将新节点的 prev 设为原尾节点，将原尾节点的 next 设为新节点，然后将新节点设为新的尾节点。插入操作的代码如下：
def insert_at_tail(self, data):
new_node = Node(data)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.length += 1
我们首先创建一个新节点 new_node，并将其 prev 设为原尾节点。如果链表长度为 0，说明原链表为空，此时我们将新节点设为头节点和尾节点。否则，我们将原尾节点的 next 设为新节点，然后将新节点设为新的尾节点。最后，链表长度加 1。
3.3 在链表中间插入
在链表中间插入一个节点时，需要先找到插入位置的前驱节点，然后将新节点的 prev 设为前驱节点，将新节点的 next 设为前驱节点的后继节点，将前驱节点的后继节点的 prev 设为新节点，最后将前驱节点的 next 设为新节点。插入操作的代码如下：
def insert_at_index(self, index, data):
if index < 0 or index > self.length:
raise IndexError("Index out of range")
new_node = Node(data)
if index == 0:
self.insert_at_head(data)
elif index == self.length:
self.insert_at_tail(data)
else:
current_node = self.head
for i in range(index - 1):
current_node = current_node.next
new_node.prev = current_node
new_node.next = current_node.next
current_node.next.prev = new_node
current_node.next = new_node
self.length += 1
如果插入位置是头节点，我们可以直接调用 insert_at_head() 方法。如果插入位置是尾节点，我们可以直接调用 insert_at_tail() 方法。否则，我们需要遍历链表，找到插入位置的前驱节点 current_node。然后，我们将新节点的 prev 设为 current_node，将新节点的 next 设为 current_node 的后继节点，将 current_node 的后继节点的 prev 设为新节点，最后将 current_node 的 next 设为新节点。插入操作完成后，链表长度加 1。
实现删除操作
在双向链表中，删除操作和插入操作类似，也可以分为三种情况：删除头节点、删除尾节点和删除中间节点。我们分别来实现这三种情况下的删除操作。
4.1 删除头节点
删除头节点时，需要将头节点的后继节点设为新的头节点，并将新的头节点的 prev 设为 None。删除操作的代码如下：
def delete_at_head(self):
if self.length == 0:
raise IndexError("List is empty")
elif self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.length -= 1
如果链表长度为 0，说明链表为空，此时抛出异常。如果链表长度为 1，说明只有一个节点，此时将头节点和尾节点都设为 None。否则，将头节点的后继节点设为新的头节点，并将新的头节点的 prev 设为 None。最后，链表长度减 1。
4.2 删除尾节点
删除尾节点时，需要将尾节点的前驱节点设为新的尾节点，并将新的尾节点的 next 设为 None。删除操作的代码如下：
def delete_at_tail(self):
if self.length == 0:
raise IndexError("List is empty")
elif self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.length -= 1
如果链表长度为 0，说明链表为空，此时抛出异常。如果链表长度为 1，说明只有一个节点，此时将头节点和尾节点都设为 None。否则，将尾节点的前驱节点设为新的尾节点，并将新的尾节点的 next 设为 None。最后，链表长度减 1。
4.3 删除中间节点
删除中间节点时，需要先找到要删除的节点，然后将要删除节点的前驱节点的后继节点设为要删除节点的后继节点，将要删除节点的后继节点的前驱节点设为要删除节点的前驱节点。删除操作的代码如下：
def delete_at_index(self, index):
if index < 0 or index >= self.length:
raise IndexError("Index out of range")
if index == 0:
self.delete_at_head()
elif index == self.length - 1:
self.delete_at_tail()
else:
current_node = self.head
for i in range(index):
current_node = current_node.next
current_node.prev.next = current_node.next
current_node.next.prev = current_node.prev
self.length -= 1
如果要删除的节点是头节点，我们可以直接调用 delete_at_head() 方法。如果要删除的节点是尾节点，我们可以直接调用 delete_at_tail() 方法。否则，我们需要遍历链表，找到要删除的节点 current_node。然后，将 current_node 的前驱节点的后继节点设为 current_node 的后继节点，将 current_node 的后继节点的前驱节点设为 current_node 的前驱节点。最后，链表长度减 1。
其他操作
除了插入和删除操作，双向链表还可以进行以下操作：
5.1 获取链表长度
获取链表长度只需要返回链表对象的 length 属性即可。
def get_length(self):
return self.length
5.2 获取节点数据
获取节点数据可以通过遍历链表找到对应节点，然后返回节点的 data 属性。
def get_node_data(self, index):
if index < 0 or index >= self.length:
raise IndexError("Index out of range")
current_node = self.head
for i in range(index):
current_node = current_node.next
return current_node.data
5.3 修改节点数据
修改节点数据也可以通过遍历链表找到对应节点，然后修改节点的 data 属性。
def set_node_data(self, index, data):
if index < 0 or index >= self.length:
raise IndexError("Index out of range")
current_node = self.head
for i in range(index):
current_node = current_node.next
current_node.data = data
注意事项
在实现双向链表时，需要注意以下几点：
6.1 插入和删除操作需要特判链表为空和链表长度为 1 的情况。
6.2 在插入和删除操作时，需要注意节点的 prev 和 next 属性的更新顺序。
6.3 在实现插入和删除操作时，需要注意链表长度的更新。
6.4 在访问节点数据时，需要特判索引越界的情况。
6.5 在修改节点数据时，需要特判索引越界的情况。
总结
本文介绍了如何在 Python 中创建双向链表，并实现了插入、删除、获取长度、获取节点数据和修改节点数据等操作。在实现双向链表时，需要注意节点的 prev 和 next 属性的更新顺序，以及特判链表为空、链表长度为 1 和索引越界的情况。双向链表可以在 O(1) 的时间复杂度内进行插入和删除操作，适用于某些场景下需要频繁进行插入和删除操作的情况。
