Python实现双向链表
单向链表请参考:
在本文中,我们将看到另一种类型的链表,可以向前和向后移动;这样的链接列表称为双重链接列表(双向链表)。以下是双向链表的功能:
- 双链表包含一个名为first和last的链接元素。
- 每个链接包含一个数据字段和两个链接字段,分别称为next和prev。
- 每个链接都使用其下一个链接与其下一个链接链接。
- 每个链接都使用其先前的连接与其先前的链接链接。
- 最后一个链接带有一个空链接,以标记列表的结尾。
创建双向链表
我们使用Node类创建一个双向链接列表。 现在,我们使用与“单链接列表”中相同的方法,但是除了节点中存在的数据之外,还将使用头和后指针进行正确分配,以在每个节点中创建两个链接。
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class doubly_linked_list:
def __init__(self):
self.head = None
# 添加数据元素
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# 打印双向链表
def listprint(self, node):
while (node is not None):
print(node.data),
last = node
node = node.next
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)
执行上面代码将打印 62 8 12 。
插入双向链表
将新节点插入到双向链表的开头的第三个位置。
修改代码,为doubly_linked_list类添加insert方法:
# 定义插入方法插入元素
def insert(self, prev_node, NewVal):
if prev_node is None:
return
NewNode = Node(NewVal)
NewNode.next = prev_node.next
prev_node.next = NewNode
NewNode.prev = prev_node
if NewNode.next is not None:
NewNode.next.prev = NewNode
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)
重新运行程序等到:62 8 13 12。
附加到双向列表
将元素追加到双向链表的最后。
修改代码,加入append()方法。
#定义append方法 添加元素到末端
def append(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = None
if self.head is None:
NewNode.prev = None
self.head = NewNode
return
last = self.head
while (last.next is not None):
last = last.next
last.next = NewNode
NewNode.prev = last
return
dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)
重新执行程序,将打印:62 8 12 9 45。
请注意附加操作的元素9和45的位置。