LinkedHashMap's impl - Używa listy podwójnie połączonej, a nie pojedynczej listy połączonej; Dlaczego

Question

Jak już mowa dokumentacji LinkedHashMap, to mówi, podwójna lista powiązana (DLL) utrzymywana jest wewnętrznie

starałem się zrozumieć, dlaczego DLL został wybrany przez S (Ingle) LL Największą zaletą I get z DLL będzie się cofał, ale nie widzę żadnego przypadku użycia dla LinkedHashMap() wykorzystującego tę zaletę, ponieważ nie istnieje żaden() rodzaj operacji jak next() w interfejsie Iterable ..

Czy ktoś może wyjaśnić, dlaczego była DLL, a nie SLL?

Answer 1

To dlatego, że z dodatkowym hash mapie można wdrożyć Usuwa w czasie O (1). Jeśli używasz pojedynczo połączonej listy, usuwanie zajmie O (n).

Rozważmy mapę hash do przechowywania parę klucz wartość, a kolejną wewnętrzną mapę hash z kluczami wskazując na węzłach w połączonej listy. Podczas usuwania, jeśli jest to podwójnie połączona lista, mogę łatwo przejść do poprzedniego elementu i wskazać na następujący element. Nie jest to możliwe na pojedynczo połączonej liście.

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