Danh sách liên kết vòng đôi C++

Danh sách liên kết vòng

Danh sách liên kết vòng 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.

Tạo danh sách liên kết vòng từ danh sách liên kết đơn

Trong danh sách liên kết đơn, điểm trỏ tới kế tiếp của nút cuối sẽ trỏ tới nút đầu tiên, thay vì sẽ trỏ tới NULL.

Tạo danh sách liên kết vòng từ danh sách liên kết đôi

Trong danh sách liên kết đôi, điểm trỏ tới kế tiếp của nút cuối sẽ trỏ tới 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.

• Đ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ư danh sách liên kết đôi.
• Điểm trước của liên kết đầu tiên trỏ đến điểm cuối cùng của danh sách trong trường hợp danh sách 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 liên kết vòngd.

• chèn- Chèn một phần tử vào đầu danh sách.
• xóa- Xóa một phần tử từ đầu danh sách.
• 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 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 ifEnd

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 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 ifEnd

Hiển thị danh sách

Mã sau đây cho thấy hoạt động hiển thị danh sách trong một 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 ifEnd

- Hiếu Kiều -