Python - Danh sách được liên kết nâng cao

Chúng ta đã thấy Danh sách liên kết ở chương trước mà chỉ có thể đi tiếp. Trong chương này, chúng ta thấy một loại danh sách liên kết khác, trong đó nó có thể di chuyển cả về phía trước và phía sau. Một danh sách được liên kết như vậy được gọi là Danh sách liên kết kép. Sau đây là các tính năng của danh sách liên kết kép.

  • Danh sách được liên kết đôi chứa một phần tử liên kết được gọi là đầu tiên và cuối cùng.
  • Mỗi liên kết mang (các) trường dữ liệu và hai trường liên kết được gọi là tiếp theo và trước.
  • Mỗi liên kết được liên kết với liên kết tiếp theo của nó bằng cách sử dụng liên kết tiếp theo của nó.
  • Mỗi liên kết được liên kết với liên kết trước của nó bằng cách sử dụng liên kết trước của nó.
  • Liên kết cuối cùng mang một liên kết là null để đánh dấu phần cuối của danh sách.

Tạo danh sách liên kết kép

Chúng tôi tạo danh sách được Liên kết kép bằng cách sử dụng lớp Node. Bây giờ chúng ta sử dụng cách tiếp cận tương tự như được sử dụng trong Danh sách liên kết Singly nhưng con trỏ đầu và con trỏ tiếp theo sẽ được sử dụng để chỉ định thích hợp để tạo hai liên kết trong mỗi nút ngoài dữ liệu có trong nút.

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)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

62 8 12

Chèn vào danh sách được liên kết kép

ở đây chúng ta sẽ xem cách chèn một nút vào Danh sách liên kết đôi bằng chương trình sau. Chương trình sử dụng một chèn có tên menthod chèn nút mới ở vị trí thứ ba từ phần đầu của danh sách liên kết kép.

# 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)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

62  8  13  12

Thêm vào một danh sách được liên kết kép

Việc thêm vào một danh sách được liên kết kép sẽ thêm phần tử vào cuối.

# 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)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

62 8 12 9 45

Hãy lưu ý vị trí của các phần tử 9 và 45 cho hoạt động nối thêm.