Trường hợp sử dụng cho LinkedList

Question

Bài đăng này chỉ thảo luận về scala.collection.mutable.LinkedList. Các triển khai khác không phải là chủ đề của chủ đề này.

Câu hỏi của tôi là: trường hợp sử dụng của lớp học này là gì? Tôi thấy nó có các vấn đề của cả hai loại cấu trúc có thể thay đổi và bất biến trong khi mang lại lợi ích cho không. Tôi nói như vậy vì:

• API vẻ với tôi như thể nó là một API bất biến (filter, map, drop, take vv tất cả trở lại một mới LinkedList thay vì làm thay đổi tại chỗ)
• tất cả các lợi ích của danh sách liên kết không thay đổi, ít nhất tôi đoán, không có mặt, tức là chia sẻ tối đa giữa các cấu trúc, bởi vì đó là vẫn có thể thay đổi (thông qua var elem và var next.

vì vậy, về cơ bản chúng ta có một thời gian truy cập tuyến tính, ap tuyến tính pend thời gian, không gian tuyến tính vv và không có gì để hiển thị cho nó trong không gian phức tạp hoặc trong khả năng lý do về mã (ngoại trừ có thể là O (1) prepend nhưng nó vẫn là trường hợp với danh sách bất biến).

Tôi không thấy lợi ích quan trọng của loại cấu trúc này? Tôi đang tìm kiếm các biện pháp khách quan và/hoặc trường hợp sử dụng có thể áp dụng cho lớp học này.

Answer 1

Tôi muốn nói lý do phức tạp - lớp danh sách được liên kết cho phép bạn giữ tham chiếu đến nút ở giữa danh sách và sử dụng insert hoặc update tại nút đó thay vì đi qua phần đầu của danh sách.

[] --> [] --> ... --> [] --> ... --> [] --| 
^     ^
head     myReference 

Trong một ứng dụng mà tôi biết chính xác nơi một sự thay đổi trong một số trình tự sẽ xảy ra (myReference ở trên), chi phí ít hơn nhiều để thay đổi vị trí đó vì sao chép tất cả mọi thứ lên đến vị trí đó như sẽ là trường hợp với immutable.List (tức là tôi chỉ chèn một nút mới sau myReference).

       myNewNode 
          v 
[] --> [] --> ... --> [] --> [] ---> ... --> [] --| 
^     ^
head     myReference 

Ví dụ về ứng dụng như vậy - L-system nơi bạn mở rộng các phần của chuỗi. Nó rẻ hơn nhiều để chèn các nút mới tại chỗ, hơn là sao chép toàn bộ chuỗi mỗi khi nó cần được mở rộng.

Lý do khác là đầy đủ - kể từ DoubleLinkedList và LinkedListLike chia sẻ nhiều cơ sở hạ tầng chung, cung cấp thêm một lớp học là chi phí thấp cho kích thước thư viện chuẩn.