Python Data Structure 简明教程
Python - Advanced Linked list
我们在前一章中已经了解到了链表，在此链表中只能向前移动。在本教程中，我们将看到另一种链表，在此链表中可以向前和向后移动。这种链表称为双链表。以下是双链表的功能。
-
双链表包含称为 first 和 last 的链接元素。
-
每条链接都携带一个数据字段和两个称为 next 和 prev 的链接字段。
-
每条链接使用其 next 链接与其下一个链接相连。
-
每条链接使用其 prev 链接与其前一个链接相连。
-
最后一条链接带有 null 作为链接，以标记列表的末尾。
Creating Doubly linked list
我们使用 Node 类创建双链表。现在，我们使用与在单链表中使用相同的方法，但是头部和下一个指针将用于适当的分配，以便在每个节点中创建两条链接，除了节点中显示的数据之外。
Example
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)Inserting into Doubly Linked List
此处，我们将看到如何使用以下程序将节点插入到双向链表中。该程序使用一个名为 insert 的方法，该方法在双链表头的第三个位置插入新节点。
Example
# 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)Appending to a Doubly linked list
向双向链表追加会将元素添加到末尾。
Example
# 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)