Danh sách liên kết tròn

Danh sách liên kết 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 đôi có thể được tạo thành một danh sách liên kết vòng tròn.

Danh sách liên kết đơn như thông tư

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 liên kết đôi khi là Thông tư

Trong danh sách liên kết đôi, 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.

1. Điểm tiếp theo của liên kết cuối cùng đến liên kết đầu tiên của danh sách trong cả hai trường hợp danh sách liên kết đơn cũng như gấp đôi.
2. Điểm trước của liên kết đầu tiên đến điểm cuối cùng của danh sách trong trường hợp danh sách được liên kết đôi.

Hoạt động cơ bản

Sau đây là các hoạt động quan trọng được hỗ trợ bởi một danh sách thông tư.

1. insert - Chèn một phần tử vào đầu danh sách.
2. xóa - Xóa một phần tử từ đầu danh sách.
3. hiển thị - Hiển thị danh sách.

Thao tác chèn

Đoạn mã sau biểu thị thao tác chèn trong danh sách liên kết tròn 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 biểu thị thao tác xóa trong danh sách liên kết tròn 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

Hiển thị danh sách hoạt động

Mã sau đây cho thấy hoạt động danh sách hiển thị trong một danh sách liên kết tròn.

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

Được cập nhật: 14 tháng 4 lúc 7:55:54 | Lượt xem: 404