News for hackers. Stuff that matters.
Re:Linked List Problems (2002) [pdf] by winstonewert on Saturday November 25, 2017 @06:37PM (#15778596)
But how do you find the element to be moved from the middle if not by iterating over the list?
Re:Linked List Problems (2002) [pdf] by KMag on Saturday November 25, 2017 @11:57PM (#15779494)
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<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;
    }
Re:Linked List Problems (2002) [pdf] by baddox on Saturday November 25, 2017 @09:33PM (#15779167)
The 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.
Re:Linked List Problems (2002) [pdf] by KMag on Saturday November 25, 2017 @11:58PM (#15779498)
Or, 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.
Re:Linked List Problems (2002) [pdf] by baddox on Sunday November 26, 2017 @12:40AM (#15779592)
The entire LRU used multiple data structures, but the ability to efficiently remove from the middle of the linked list is still important.
Re:Linked List Problems (2002) [pdf] by winstonewert on Saturday November 25, 2017 @09:44PM (#15779192)
Oy! I can't believe I missed that.