Python - 高级链表_Python 数据结构和算法教程

我们已经在前面的章节中看到了链表，其中只能向前移动。在本章中，我们看到了另一种类型的链表，其中可以向前和向后移动。这样的链表称为双向链表。以下是双向链表的特点。

双向链表包含一个名为 first 和 last 的链接元素。
每个链接都带有一个数据字段和两个名为 next 和 prev 的链接字段。
每个链接都使用其下一个链接与其下一个链接链接。
每个链接都使用其前一个链接与其前一个链接链接。
最后一个链接将链接作为 null 来标记列表的末尾。

创建双向链表

我们使用 Node 类创建一个双向链表。现在我们使用与单向链表中相同的方法，但 head 和 next 指针将用于正确分配，除了节点中存在的数据外，还可以在每个节点中创建两个链接。

例

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

插入双向链表

在这里，我们将看到如何使用下面的程序将节点插入到 Doubly Link List。该程序使用一个名为 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 的位置，以便进行 append 操作。

<< Python - 取消排队 Python - 哈希表的数据结构 >>