Python 高级LinkedList
我们已经在前一章中看到了关联列表,它只可能向前移动。在这一章中,我们看到了另一种类型的链表,它可以向前和向后移动。这样的链接表被称为双链接表。以下是双链表的特点。
- 双重链接列表包含一个叫做首尾相连的链接元素。
-
每个链接都有一个数据字段和两个链接字段,称为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
# Adding data elements
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Print the Doubly Linked list
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
插入到双链表中
在这里,我们将看到如何使用下面的程序向双链接列表插入一个节点。该程序使用一个名为insert的方法,将新节点插入到双链表头部的第三个位置。
例子
# Create the Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Create the doubly linked list
class doubly_linked_list:
def __init__(self):
self.head = None
# Define the push method to add elements
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Define the insert method to insert the element
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
# Define the method to print the linked list
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.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)
输出
当上述代码被执行时,它产生了以下结果 –
62 8 13 12
向双链表加注
向双链表追加将在最后添加元素。
例子
# Create the node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Create the doubly linked list class
class doubly_linked_list:
def __init__(self):
self.head = None
# Define the push method to add elements at the begining
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Define the append method to add elements at the end
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
# Define the method to print
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.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)
输出
当上述代码被执行时,它产生了以下结果 –
62 8 12 9 45
请注意附加操作的元素9和45的位置。