Liên kết của LinkHashMap - Sử dụng Danh sách Liên kết Đôi, không phải là một Danh sách Liên kết Đơn; Tại sao

Question

Như tôi đã đề cập đến các tài liệu của LinkedHashMap, Nó nói, một danh sách liên kết kép (DLL) được duy trì trong nội bộ

Tôi đã cố gắng tìm hiểu tại sao một DLL đã được lựa chọn qua S (Ingle) LL Ưu điểm lớn nhất tôi nhận được với một DLL sẽ đi qua phía sau, nhưng tôi không thấy bất kỳ trường hợp sử dụng cho LinkedHashMap() khai thác lợi thế này, vì không có trước() loại hoạt động như tiếp theo() trong giao diện Iterable ..

Bất cứ ai có thể giải thích tại sao là một DLL, và không phải là một SLL?

Answer 1

Đó là vì với bản đồ băm bổ sung, bạn có thể triển khai các lần xóa trong O (1). Nếu bạn đang sử dụng một danh sách liên kết đơn lẻ, xóa sẽ mất O (n).

Xem xét bản đồ băm để lưu trữ cặp giá trị khóa và một bản đồ băm nội bộ khác bằng các phím trỏ đến các nút trong danh sách được liên kết. Khi xóa, nếu đó là danh sách được liên kết kép, tôi có thể dễ dàng truy cập phần tử trước đó và làm cho nó trỏ đến phần tử sau. Điều này là không thể với một danh sách liên kết đơn lẻ.

http://www.quora.com/Java-programming-language/Why-is-a-Java-LinkedHashMap-or-LinkedHashSet-backed-by-a-doubly-linked-list