Advanced Linked list

优质

小牛编辑

132浏览

2023-12-01

我们已经在前面的章节中看到了链接列表，它可能只是向前推进。在本章中，我们将看到另一种链接列表，其中可以向前和向后移动。这种链表称为双链表。以下是双向链表的特征。

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

创建双链表

我们使用Node类创建一个Doubly Linked列表。现在我们使用与单链接列表中使用的方法相同的方法，但是除了节点中存在的数据之外，头部和下一个指针将用于正确分配以在每个节点中创建两个链接。

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的menthod，它将新节点从双向链表的头部插入第三个位置。

# 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在追加操作中的位置。