Normal way is a hashmap pointing into a doubly linked list to make delete easy. To do it with a singly linked list without going to O(n) search, have the hashmap point to the preceding node in the linked list (the predecessor of the one you care about, or null if the element is at the front). Retrieve list node: hashmap(key) ? hashmap(key)->next : list.head Delete: successornode = hashmap(key)->next->next hashmap( successornode ) = hashmap(key) hashmap(key)->next = successornode hashmap.delete(key)

Cool. I was thinking of this for Dropbox interview, and here is the question with answer. Luckily, I can confirm that it is a doable solution. I think ddl was useful for you to delete a node in the list. In the leetcode question, there is a practice that to delete a node given you the node, but not the entire list. So that, even you just know the node you are going to delete without knowing the entire list, you can still do it. In LRU case, you just have to maintain a relationship between hashtable and the list. What you can do is to let the node going to be delete copy the value of this's next node. and let the hashtable value (the next node's ) re pointing to me. Now, here is the issue. What if the node that I want to delete is the last node in the linked list? You have to let the trail pointer to re pointing the next node. Now, this time you don't have prev for your linkedlist, how would you do it? You have to go through all the list in a pair, to search the last node and last node's previous one, which takes O(n).

LRU is possible with single LL. It would be O(n) but this how you would do it public class LRU { node root; node last; int capacity; int size; LRU( int c ) { size = 0; capacity = c; root = null; last = null; } public V get (K key ) { if (size == 0 ) return null; node current = root; node prev = null; node found = false; for (int i=0; i n = new node (key, value); n.next = null; last.next = n; last = n; size++; } class node { public K key; public V value; node next; public node ( K k, V v) { key = k; value = v; } } }

I do not know