Data Structures & Algorithms - Tập 10: Cấu trúc dữ liệu Doubly Linked List

Tập 10: Cấu trúc dữ liệu Doubly Linked List Tác giả: Le Nguyen & Code AI

Singly Linked List chỉ nhìn về phía trước — như đi trên con đường một chiều, lỡ bước qua rồi thì không quay lại được. Doubly Linked List thêm một sợi dây nữa: mỗi Node giờ nhớ cả quá khứ lẫn tương lai. Prev trỏ về người đi trước, Next trỏ về người đi sau — insert, delete ở đầu hay cuối đều O(1), không cần dò từ đầu. Text editor dùng nó để di chuyển cursor qua lại. Undo/Redo dùng nó để bước tới bước lui giữa các trạng thái. LRU Cache dùng nó để đẩy phần tử cũ ra, kéo phần tử mới vào. Alt+Tab dùng nó để xoay vòng giữa các cửa sổ. Đổi lại, mỗi Node tốn thêm một con trỏ — RAM tăng, code phức tạp hơn, và quên cập nhật Prev là bug âm thầm xuất hiện. Không có gì là miễn phí, nhưng khi cần sự linh hoạt — DLL là Hoàng Hậu trên bàn cờ dữ liệu.