KIỂU DỮ LIỆU LIÊN KẾT KÉP (Double Linked List)

1. Lý thuyết

Nếu bạn đã đọc bài viết về Danh sách liên kết đơn thì có thể thấy việc tổ chức dạng danh sách tiện lợi hơn rất nhiều so với dùng mảng. Tuy nhiên, danh sách liên kết đơn vẫn có nhược điểm là chỉ có thể duyệt từ đầu đến cuối. Vì vậy, một số thao tác sẽ rất khó cài đặt trên nó. Danh sách liên kết kép có thể khắc phục nhược điểm này. Hầu hết các thao tác điều giống với danh sách liên kết đơn nhưng mình cũng khuyên các bạn nên đọc bài: Danh sách liên kết đơn và các thao tác cơ bản trước khi đọc bài viết này. Các thao tác được minh họa bằng Python.

Tổ chức dữ liệu: Với danh sách liên kết kép, mỗi phần tử sẽ liên kết với phần tử đứng trước và sau nó trong danh sách. Mỗi phần tử trong danh sách (node) gồm biến lưu dữ liệu và 2 con trỏ liên kết tới phần tử trước và sau nó. 

 

 Trong minh họa dưới cài đặt một số vấn đề sau:

- Bổ sung node vào danh sách

- Xóa node khỏi danh sách

- Tìm kiếm trong danh sách

- Sắp xếp (nổi bọt)

- Duyệt danh sách

2. Cài đặt

 Code Python