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.