Giới thiệu về Danh Sách Liên Kết Vòng
Danh sách liên kết vòng (Circular Linked List) là cấu trúc dữ liệu tương tự như danh sách liên kết đơn (Singly Linked List) nhưng có những điểm khác biệt quan trọng:
- Node cuối cùng (tail node) sẽ trỏ trở về node đầu (head node) thay vì trỏ đến null (
None). - Không có điểm kết thúc rõ ràng trong danh sách, điều này có nghĩa là nếu bạn duyệt qua nó mà không kiểm tra điều kiện cụ thể, bạn có thể lặp lại mãi mãi.
Danh sách liên kết vòng thường được sử dụng trong các bài toán cần tính năng lặp vô hạn hoặc khi bạn cần quay trở lại điểm đầu tiên sau khi hoàn thành một chu kỳ, ví dụ như trong việc phát lại danh sách nhạc.
Khởi Tạo Danh Sách Liên Kết Vòng
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = NonePhương Thức Append
Phương thức append được sử dụng để thêm một node mới vào cuối danh sách. Trong trường hợp danh sách rỗng, node mới sẽ trở thành node đầu (head) và trỏ đến chính nó, tạo thành vòng tròn. Nếu danh sách đã có node, ta sẽ duyệt đến node cuối cùng và gán node mới sau node cuối đó, tiếp tục giữ cấu trúc vòng tròn.
python
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.headIn Nội Dung Danh Sách
Phương thức print_list cho phép bạn duyệt và in dữ liệu của từng node trong danh sách bắt đầu từ head cho đến khi trở về vị trí head, để thấy được tính chất vòng. Điều này rất hữu ích để kiểm tra nội dung của danh sách.
python
def print_list(self):
current = self.head
if self.head:
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("(head)")
else:
print("Danh sách trống.")Phương Thức Prepend
Nếu bạn muốn thêm một node mới vào đầu danh sách, bạn có thể sử dụng phương thức prepend. Nó sẽ đặt node mới trước head hiện tại và cập nhật con trỏ next của node cuối cùng, đảm bảo rằng danh sách vẫn giữ được tính chất vòng tròn.
python
def prepend(self, data):
new_node = Node(data)
current = self.head
new_node.next = self.head
if not self.head:
new_node.next = new_node
else:
while current.next != self.head:
current = current.next
current.next = new_node
self.head = new_nodePhương Thức Remove
Phương thức remove giúp bạn xóa một node theo giá trị cụ thể khỏi danh sách. Khi thực hiện xóa, bạn cần đảm bảo rằng cấu trúc vòng của danh sách vẫn được bảo toàn, đặc biệt khi xóa head hoặc node giữa danh sách.
python
def remove(self, key):
if self.head:
if self.head.data == key:
current = self.head
while current.next != self.head:
current = current.next
if self.head == self.head.next:
self.head = None
else:
current.next = self.head.next
self.head = self.head.next
else:
current = self.head
prev = None
while current.next != self.head:
prev = current
current = current.next
if current.data == key:
prev.next = current.next
breakChia Danh Sách Liên Kết Vòng Thành Hai Nửa
Bạn có thể chia danh sách liên kết vòng thành hai nửa bằng cách:
- Tìm kiếm chiều dài danh sách.
- Tính toán điểm giữa.
- Duyệt đến điểm giữa và ngắt liên kết vòng tại đó.
Dưới đây là cách thực hiện điều này:
python
def length(self):
if not self.head:
return 0
temp = self.head
count = 1
while temp.next != self.head:
count += 1
temp = temp.next
return count
def split(self):
if not self.head:
return None, None
length = self.length()
if length == 1:
return self, None
mid = length // 2
current = self.head
prev = None
for _ in range(mid):
prev = current
current = current.next
second_list = CircularLinkedList()
second_list.head = current
prev.next = self.head
temp = second_list.head
while temp.next != self.head:
temp = temp.next
temp.next = second_list.head
return self, second_listVí Dụ Sử Dụng
Dưới đây là ví dụ về cách sử dụng danh sách liên kết vòng:
python
# Tạo một danh sách liên kết vòng mới
cll = CircularLinkedList()
for i in range(1, 11):
cll.append(i)
print("Danh sách liên kết vòng ban đầu:")
cll.print_list()
list1, list2 = cll.split()
print("\nDanh sách liên kết vòng thứ nhất:")
list1.print_list()
print("\nDanh sách liên kết vòng thứ hai:")
list2.print_list()Kết quả sẽ là:
Danh sách liên kết vòng ban đầu:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> (head)
Danh sách liên kết vòng thứ nhất:
1 -> 2 -> 3 -> 4 -> 5 -> (head)
Danh sách liên kết vòng thứ hai:
6 -> 7 -> 8 -> 9 -> 10 -> (head)source: viblo
