Cấu trúc dữ liệu - Danh sách được liên kết theo vòng tròn
Danh sách liên kết hình tròn là một biến thể của danh sách được liên kết trong đó phần tử đầu tiên trỏ đến phần tử cuối cùng và phần tử cuối cùng trỏ đến phần tử đầu tiên. Cả Danh sách liên kết đơn và Danh sách liên kết kép đều có thể được tạo thành một danh sách liên kết vòng.
Danh sách liên kết Singly dưới dạng vòng tròn
Trong danh sách liên kết đơn, con trỏ tiếp theo của nút cuối cùng trỏ đến nút đầu tiên.
Danh sách được liên kết gấp đôi dưới dạng hình tròn
Trong danh sách được liên kết kép, con trỏ tiếp theo của nút cuối cùng trỏ đến nút đầu tiên và con trỏ trước của nút đầu tiên trỏ đến nút cuối cùng tạo thành vòng tròn theo cả hai hướng.
Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.
Liên kết tiếp theo của liên kết cuối cùng trỏ đến liên kết đầu tiên của danh sách trong cả hai trường hợp là danh sách liên kết đơn và liên kết kép.
Liên kết trước của liên kết đầu tiên trỏ đến cuối cùng của danh sách trong trường hợp danh sách được liên kết kép.
Hoạt động cơ bản
Sau đây là các thao tác quan trọng được hỗ trợ bởi danh sách vòng tròn.
insert - Chèn một phần tử vào đầu danh sách.
delete - Xóa một phần tử khỏi đầu danh sách.
display - Hiển thị danh sách.
Thao tác chèn
Đoạn mã sau minh họa thao tác chèn trong danh sách liên kết vòng dựa trên danh sách liên kết đơn.
Thí dụ
insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
head := node
next of node = head
else
temp := head
while next of temp is not head, do
temp := next of temp
done
next of node := head
next of temp := node
head := node
end if
End
Thao tác xóa
Đoạn mã sau minh họa thao tác xóa trong danh sách liên kết vòng dựa trên danh sách liên kết đơn.
deleteFirst():
Begin
if head is null, then
it is Underflow and return
else if next of head = head, then
head := null
deallocate head
else
ptr := head
while next of ptr is not head, do
ptr := next of ptr
next of ptr = next of head
deallocate head
head := next of ptr
end if
End
Hoạt động danh sách hiển thị
Mã sau minh họa thao tác hiển thị danh sách trong danh sách liên kết vòng.
display():
Begin
if head is null, then
Nothing to print and return
else
ptr := head
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End
Để biết về cách triển khai của nó trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .