Chào ace, bài này chúng ta sẽ tìm hiểu về Circular Linked List – Danh sách liên kết vòng trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Danh sách liên kết vòng – Circular linked list là một danh sách liên kết (linked list) trong đó tất cả các nodes được kết nối với nhau để tạo thành một vòng tròn. Sẽ không có con trỏ NULL ở cuối danh sách liên kết vòng. Một danh sách liên kết vòng có thể ở dạng danh sách liên kết vòng đơn (singly circular linked list) hoặc danh sách liên kết vòng kép (doubly circular linked list).
Ưu điểm của danh sách liên kết vòng:
1. Bất kỳ node nào cũng có thể là điểm bắt đầu (starting point). Chúng ta có thể duyệt toàn bộ danh sách bằng cách bắt đầu tại bất kỳ điểm nào, tùy ý. Chúng ta chỉ cần dừng lại khi node đầu tiên được duyệt, lại được duyệt tới một lần nữa.
2. Danh sách liên kết vòng rất hữu dụng trong việc triển khai queue – hàng đợi. Khi sử dụng danh sách liên kết vòng để cài đặt queue, chúng ta sẽ không cần phải duy trì hai điểm front (điểm đầu) và rear (điểm cuối) của queue. Chúng ta chỉ cần duy trì một con trỏ dành cho note mới nhất được chèn vào (nằm ở cuối danh sách), lấy node cuối cùng này làm mốc, ta có thể dễ dàng truy cập tới các nodes nằm ở phần đầu danh sách.
3. Danh sách liên kết dạng vòng còn hữu dụng trong các ứng dụng phần mềm, để lặp đi lặp lại danh sách. Ví dụ, khi nhiều ứng dụng đang chạy trên một Máy tính, thông thường hệ điều hành sẽ đặt các ứng dụng đang chạy vào một danh sách, và sau đó duyệt qua chúng, mỗi lần duyệt tới ứng dụng nào thì lại cho ứng dụng đó một khoảng thời gian để thực thi, và sau đó lại đưa chúng về trạng thái đợi trong khi CPU được cấp cho một ứng dụng khác. Vì thế, sẽ rất lý tưởng khi hệ điều hành sử dụng một danh sách liên kết vòng để khi duyệt đến cuối danh sách, nó có thể quay vòng lên phía trước danh sách/phần đầu danh sách.
4. Danh sách liên kết vòng kép (Circular Doubly Linked List) được sử dụng để cài đặt các cấu trúc dữ liệu nâng cao, ví dụ như Fibonacci Heap.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật){kind=link}