News for hackers. Stuff that matters.
Re:Linked List Problems (2002) [pdf] by praptak on Saturday November 25, 2017 @02:48PM (#15777612)
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.
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.