Bạn không dùng Linked List. Nhưng chúng đang vận hành một nửa phần mềm của bạn.

Có lẽ bạn sẽ không bao giờ phải viết một danh sách liên kết (linked list) trong một dự án JavaScript thực tế. Các mảng (arrays) tích hợp sẵn trong ngôn ngữ của bạn xử lý việc thay đổi kích thước linh hoạt nhanh hơn. Các nhà tuyển dụng dạy bạn cách xây dựng chúng trên bảng trắng, nhưng điều này tạo ra một mô hình tư duy sai lệch.

Bạn không nên học danh sách liên kết chỉ để triển khai chúng. Bạn học chúng để hiểu các công cụ mà bạn sử dụng hàng ngày.

Chúng có mặt ở khắp mọi nơi: • Các nút quay lại (back) và tiến (forward) trên trình duyệt. • Lịch sử hoàn tác (undo) của trình soạn thảo văn bản. • Các bộ nhớ đệm LRU trong máy chủ web và cơ sở dữ liệu. • Các lệnh list của Redis. • Bộ lập lịch tiến trình (process scheduler) của nhân Linux.

Chúng không phải là những di vật lỗi thời. Chúng là cơ sở hạ tầng.

Lý do thực sự khiến danh sách liên kết gặp khó khăn là tính cục bộ của bộ nhớ đệm (cache locality). CPU của bạn không đọc RAM từng byte một. Nó sẽ lấy một khối 64-byte được gọi là một cache line.

Mảng nhanh vì chúng nằm liền kề nhau trong bộ nhớ. CPU đọc phần tử đầu tiên và nhận luôn 15 phần tử tiếp theo một cách miễn phí.

Danh sách liên kết phá hủy điều này. Mỗi nút (node) nằm ở một vị trí bộ nhớ khác nhau. Việc đi theo một con trỏ (pointer) buộc CPU phải nhảy đến một địa chỉ mới. Điều này kích hoạt một lần truy xuất RAM mới. Việc này tiêu tốn hàng trăm chu kỳ CPU.

Trên phần cứng hiện đại, việc duyệt mảng có thể nhanh hơn từ 10 đến 100 lần so với duyệt danh sách liên kết. Ký hiệu Big-O đã bỏ qua chi phí hằng số này.

Vậy khi nào bạn nên sử dụng chúng?

Sử dụng danh sách liên kết đơn (singly linked list) cho ngăn xếp (stack) hoặc các hàng đợi tác vụ (task queue) đơn giản, nơi bạn chỉ thêm hoặc xóa ở một đầu.

Sử dụng danh sách liên kết đôi (doubly linked list) khi bạn cần xóa với độ phức tạp O(1) bằng cách tham chiếu trực tiếp đến nút. Đây chính là bí mật của bộ nhớ đệm LRU.

Một bộ nhớ đệm LRU cần:

  • Tra cứu (lookup) với O(1).
  • Chèn (insertion) với O(1).
  • Loại bỏ (eviction) với O(1).
  • Thăng cấp (promotion) với O(1).

Một mảng không thể làm được điều này vì việc di chuyển các mục yêu cầu phải dịch chuyển tất cả các mục khác. Một hash map đơn lẻ cũng không thể làm được vì nó không có thứ tự.

Giải pháp là sự kết hợp. Một hash map cung cấp khả năng tra cứu. Một danh sách liên kết đôi duy trì thứ tự. Hash map lưu trữ tham chiếu đến nút. Khi bạn truy cập một khóa (key), bạn lấy trực tiếp nút đó từ danh sách và đưa nó lên đầu. Không cần tìm kiếm. Không cần dịch chuyển.

Đừng học cấu trúc dữ liệu chỉ để vượt qua các cuộc phỏng vấn. Hãy học chúng để hiểu cách phần mềm tương tác với phần cứng.

Nguồn: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37