Earlier quoted context omitted.
That's why I mentioned the LRU implementation. It does not iterate over the list, only adds elements to the front, deletes from the back and moves from the middle to the front. Refs to nodes are stored in a map, so iteration is not necessary to find an element.
But how do you find the element to be moved from the middle if not by iterating over the list?
You use a hash map, and make the linked list a linked list of hash entries. So, if you're using chaining (as opposed to the many variations on open addressing):
class Entry {
Entry younger; // LRU doubly linked list
Entry older; // LRU doubly linked list
Entry next; // for hash map bucket chaining
V value;
K key;
}
class MapEntry {
Entry next;
DoublyLinkedListEntry> LruEntry;
K key;
V value;
}
class DoublyLinkedListEntry {
ListEntry prev;
LintEntry next;
T value;
}