Khi nào nên lựa chọn Double Linked List thay vì Singly Linked List trong thiết kế phần mềm ứng dụng thực tế?

Question

Accepted Answer

1. Định nghĩa cơ bản

Singly Linked List (Danh sách liên kết đơn): Mỗi node chứa dữ liệu và con trỏ (pointer) trỏ tới node tiếp theo.
Double Linked List (Danh sách liên kết đôi): Mỗi node chứa dữ liệu, con trỏ trỏ tới node tiếp theo (next) và con trỏ trỏ tới node trước đó (prev).

2. Điểm khác biệt về hiệu năng

Thao tác xóa một node biết trước:
Singly Linked List: Tốn O(N) vì phải duyệt từ đầu danh sách để tìm node đứng trước nhằm cập nhật lại con trỏ.
Double Linked List: Tốn O(1) vì có sẵn con trỏ prev để truy cập trực tiếp node phía trước.

Duyệt danh sách:
Singly Linked List: Chỉ duyệt được một chiều từ trái sang phải.
Double Linked List: Duyệt được cả hai chiều (tiến và lùi).

3. Ứng dụng thực tế trong Enterprise

Double Linked List được sử dụng làm cấu trúc nền tảng để cài đặt thuật toán LRU Cache (Least Recently Used Cache) trong các hệ thống phân tán hoặc bộ nhớ đệm ứng dụng, nơi các thao tác đưa node lên đầu danh sách hoặc loại bỏ node cuối cùng cần phải thực hiện với độ phức tạp O(1).
Nhược điểm cần cân nhắc: Double Linked List tiêu tốn nhiều bộ nhớ hơn cho mỗi node do phải lưu trữ thêm một con trỏ phụ.

Khi nào nên lựa chọn Double Linked List thay vì Singly Linked List trong thiết kế phần mềm ứng dụng thực tế?

1. Định nghĩa cơ bản

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi data structures liên quan cùng chủ đề