Danh sách liên kết vòng đơn, vòng đôi
| |

Danh sách liên kết vòng – Circular Linked List

This entry is part 6 of 16 in the series Cấu trúc dữ liệu

Danh sách liên kết vòng(Circular Linked List) là danh sách liên kết có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín. Bài viết này Nguyễn Văn Hiếu sẽ hướng dẫn bạn cách cài đặt DSLK vòng trong C/C++ nhé.

1. Lý thuyết về danh sách liên kết vòng

Danh sách liên kết vòng có kết nối của phần tử cuối với head
Danh sách liên kết vòng có kết nối của phần tử cuối với head

Đó là sự khác biệt giữa DSLK vòng và danh sách liên kết đơn. Tất nhiên, bạn cũng có thể cài đặt DSLK vòng trên danh sách liên kết đôi. Tuy nhiên, trong bài này tôi sẽ hướng dẫn bạn cài đặt trên danh sách liên kết đơn trước nhé.

2. Cài đặt DSLK vòng đơn

Khai báo kiểu dữ liệu Node

Khai báo Node của DSLK vòng trong bài này giống với danh sách liên kết đơn

Tạo mới Node

Lấy số lượng Node

Thêm vào đầu

Thêm vào cuối

Trong Circular Linked List, để thêm vào cuối bạn có thể thêm vào đầu và trả về đầu mới là next của node mới thêm vào.

Thêm vào vị trí bất kỳ

Các bạn lưu ý là vị trí, không phải chỉ số nhé. Do đó, phần tử đầu tiên có vị trí là 1 và phần tử cuối là len.

Xóa theo giá trị chỉ định

Xóa theo vị trí chỉ định

Sắp xếp theo giá trị tăng dần

3. Full code DSLK vòng đơn

Kết quả chạy:

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

Với dslk vòng đôi, nếu bạn nào quan tâm có thể tham khảo source code sau đây. Mình xin phép không đi sâu giải thích nữa.

Danh sách liên kết vòng đôi(Circular Doubly Linked List)
Hình ảnh mô phỏng DSLK vòng đôi(Circular Doubly Linked List)

Kết quả chạy:

Như vậy, sau bài này mình đã hoàn thành phần hướng dẫn về cấu trúc dữ liệu danh sách liên kết. Ở bài viết tiếp theo, mình sẽ hướng dẫn các bạn kiến thức về cấu trúc dữ liệu Cây(Tree). Mong được các bạn quan tâm và chia sẻ cho bạn bè của mình. Thân ái!

Similar Posts

Subscribe
Notify of
guest
1 Bình luận
Inline Feedbacks
View all comments