Các loại danh sách liên kết DSA
Các loại danh sách liên kết
Có ba dạng danh sách liên kết cơ bản:
- Danh sách liên kết đơn
- Danh sách liên kết đôi
- Danh sách liên kết vòng
Danh sách liên kết đơn là loại danh sách liên kết đơn giản nhất. Nó chiếm ít không gian hơn trong bộ nhớ vì mỗi nút chỉ có một địa chỉ cho nút tiếp theo, như trong hình bên dưới.
Danh sách liên kết đôi có các nút có địa chỉ cho cả nút trước và nút tiếp theo, như trong hình bên dưới và do đó chiếm nhiều bộ nhớ hơn. Nhưng danh sách liên kết đôi là tốt nếu bạn muốn có thể di chuyển cả lên và xuống trong danh sách.
Danh sách liên kết vòng giống như danh sách liên kết đơn hoặc đôi với nút đầu tiên, "đầu" và nút cuối cùng, "đuôi", được kết nối.
Trong danh sách liên kết đơn hoặc đôi, chúng ta có thể tìm thấy điểm bắt đầu và kết thúc của danh sách chỉ bằng cách kiểm tra xem các liên kết có rỗng hay không. Nhưng đối với danh sách liên kết vòng, cần có mã phức tạp hơn để kiểm tra rõ ràng các nút bắt đầu và kết thúc trong một số ứng dụng nhất định.
Danh sách liên kết vòng rất phù hợp cho những danh sách bạn cần duyệt qua liên tục.
Hình ảnh bên dưới là ví dụ về danh sách liên kết vòng đơn:
Hình ảnh bên dưới là ví dụ về danh sách liên kết vòng tròn kép:
Lưu ý: Bạn cần loại danh sách liên kết nào sẽ tùy thuộc vào vấn đề bạn đang cố gắng giải quyết.
Triển khai danh sách liên kết
Dưới đây là cách triển khai cơ bản của:
- Danh sách liên kết đơn
- Danh sách liên kết đôi
- Danh sách liên kết đơn vòng
- Danh sách liên kết đôi vòng
Trang tiếp theo sẽ trình bày các thao tác khác nhau có thể được thực hiện trên danh sách liên kết.
1. Triển khai danh sách liên kết đơn
Dưới đây là cách triển khai danh sách liên kết đơn này:
Ví dụ
Danh sách liên kết đơn cơ bản trong Python:
(Đây là ví dụ tương tự như ở cuối trang trước.)
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null") Chạy ví dụ »2. Triển khai danh sách liên kết đôi
Dưới đây là cách triển khai danh sách liên kết đôi này:
Ví dụ
Danh sách liên kết đôi cơ bản trong Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
print("\nTraversing forward:")
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
print("\nTraversing backward:")
currentNode = node4
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("null") Chạy ví dụ »3. Thực hiện danh sách liên kết đơn tuần hoàn
Dưới đây là cách triển khai danh sách liên kết đơn vòng tròn này:
Ví dụ
Danh sách liên kết đơn tròn cơ bản trong Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...") Chạy ví dụ »Dòng 14: Điều này làm cho danh sách đơn lẻ trở thành vòng tròn.
Dòng 17: Đây là cách chương trình biết khi nào nên dừng để chỉ duyệt qua danh sách một lần.
4. Thông tư thực hiện danh sách liên kết đôi
Dưới đây là cách triển khai danh sách liên kết kép vòng tròn này:
Ví dụ
Danh sách liên kết đôi vòng tròn cơ bản trong Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node1.prev = node4
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node1
print("\nTraversing forward:")
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")
print("\nTraversing backward:")
currentNode = node4
startNode = node4
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("...") Chạy ví dụ »Dòng 13 và 22: Các liên kết này làm cho danh sách liên kết đôi trở thành vòng tròn.
Dòng 26: Đây là cách chương trình biết khi nào nên dừng để chỉ duyệt qua danh sách một lần.
