在Python中创建一个二重链接的列表
本文将演示用Python编程语言创建一个双链表。
在Python中创建一个双链式列表
一个双链表指的是一个由顺序链接的记录集组成的链接数据结构，称为节点。每个节点都包含一个上一个指针，一个下一个指针，和一个数据字段。
上一个和下一个指针指向上一个和下一个节点。第一个节点上的上一个指针和最后一个节点上的下一个指针都指向None 。
我们可以在双链表的某个节点前后插入一个新节点。此外，我们还可以向前和向后遍历双链表。
然而，每一个双链表的节点都需要额外的空间来放置前一个指针。
一个节点类被创建如下。指针和数据值默认为None 。
class Node:
def __init__(self, next=None, previous=None, data=None):
self.next = next
self.previous = previous
self.data = data
然后，用于双链表的类被创建。self.head 表示列表的头部，一开始是None 。
我们将使用add_to_end 函数在双链表的末端添加一个新的节点。首先，我们用new_node 变量创建一个 Node 类实例。
由于new_node 将是列表的最后一个值，我们将它的下一个指针设置为None 。我们定义last 变量来寻找我们将添加new_node 的节点。
首先，这个变量是双链表的头部（对于第一个添加的节点，这个头部将是None ）。
我们检查self.head 是否是if 块中的None 。如果是，那么列表中就没有节点了，现在列表的头部将是新添加的节点。
在while 块中，我们检查next 变量的指针last ，找到列表的最后一个值。我们用last.next 替换last 变量，直到我们得到None 。
当我们找到last.next 值为None 的节点时，我们结束列表。
我们将找到的last 节点值的next 指针设置为指向new_node 。最后，我们将new_node 变量的previous 指针设置为指向last 变量。
因此，new_node 节点被添加到双链表的末尾。
请看下面的代码。
class DoublyLinkedList:
def __init__(self):
self.head = None
def add_to_end(self, new_node):
new_node = Node(data = new_node)
new_node.next = None
last = self.head
if self.head is None:
new_node.previous = None
self.head = new_node
return
while (last.next is not None):
last = last.next
last.next = new_node
new_node.previous = last
我们可以使用add_to_beginning 函数将一个节点添加到双链表的开头。这个过程更加简单明了。
首先，我们将new_node 变量的指针next 设置为self.head ，将previous 指针设置为None 。因此，头部值，即旧列表的第一个值，成为new_node 所指向的下一个值。
在if 块中，如果列表为空，我们检查self.head 值是否为None 。如果这个值是定义的，或者有一个与头部对应的节点，我们把这个节点的previous 指针改为new_node 。
最后，我们将self.head 改为new_node 。这样，new_node 被添加到双链表的开头。
请看下面的代码演示。
class DoublyLinkedList:
def __init__(self):
self.head = None
def add_to_end(self, new_node):
# previous function
def add_to_beginning(self, new_node):
new_node = Node(data = new_node)
new_node.next = self.head
new_node.previous = None
if self.head is not None:
self.head.previous = new_node
self.head = new_node
在下面的例子中，首先创建了doubly_linked_list 变量。这个变量是DoublyLinkedList类的一个实例。
然后我们分别在列表的末尾添加1 和3 ，在开头添加5 。列表的最终状态是5 -> 1 -> 3 -> None 。
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)
