4 ms·
But how do you find the element to be moved from the middle if not by iterating over the list?
by winstonewert 9y ago
But how do you find the element to be moved from the middle if not by iterating over the list?
- baddox 9y agoThe commenter mentions that in the last sentence. There is some separate data structure that also has references to nodes in the middle of the linked list.
- winstonewert 9y agoOy! I can't believe I missed that.
- KMag 9y agoOr, you've removed one indirection and made the linked list actually a part of another data structure, as in how LRU caches are generally implemented.
- baddox 9y agoThe entire LRU used multiple data structures, but the ability to efficiently remove from the middle of the linked list is still important.
- KMag 9y agoYou 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<K,V> { Entry<K,V> younger; // LRU doubly linked list Entry<K,V> older; // LRU doubly linked list Entry<K,V> next; // for hash map bucket chaining V value; K key; } The naive solution using two separate data structures would look like: class MapEntry<K,V> { Entry<K,V> next; DoublyLinkedListEntry<MapEntry<K,V>> LruEntry; K key; V value; } class DoublyLinkedListEntry<T> { ListEntry<T> prev; LintEntry<T> next; T value; }