Combining a list with a map

Understand the idea

A map locates a node by key; a doubly linked list maintains recency order. Together they support an LRU cache: read/update moves a node to the front, and eviction removes the least-recent tail.

Work through an example

With capacity 2, put A, put B, get A, put C evicts B. The map supplies B's node without searching the list.

Time and space complexity

Expected O(1) get/put with hash lookup and local link changes; O(capacity) storage.

Why it works

Each cached key appears exactly once in both map and recency list; sizes agree.

Common mistakes

• Updating an existing key must not create a duplicate node.
• Capacity zero requires an explicit no-storage policy.

Chapter lab · Python implementation

A linked list stores values in nodes connected by references. The lab reverses links while retaining the next unread node. Draw references as arrows: changing a link does not move a node in memory. Ordered traversal is cheap; locating an arbitrary position still requires walking from a known node.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Node:
    def __init__(self,value,next=None):
        self.value,self.next=value,next

def reverse(head):
    previous=None
    current=head
    while current is not None:
        following=current.next
        current.next=previous
        previous,current=current,following
    return previous

def values(head):
    output=[]
    while head is not None:
        output.append(head.value)
        head=head.next
    return output

def has_cycle(head):
    slow=fast=head
    while fast is not None and fast.next is not None:
        slow=slow.next
        fast=fast.next.next
        if slow is fast:
            return True
    return False

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

head=Node(1,Node(2,Node(3)))
assert values(reverse(head))==[3,2,1]
assert reverse(None) is None
assert not has_cycle(Node(1))
a=Node(1); b=Node(2,a); a.next=b; assert has_cycle(a)