Back to Technology

LRU Cache & Skip List: Linked Lists in Action

September 9, 2026 Wasil Zafar 28 min read

Two interview staples turn plain linked lists into production infrastructure: the LRU Cache pairs a doubly linked list with a hashmap to get O(1) eviction and lookup, and the Skip List layers randomized "express lanes" on top of a sorted linked list to get O(log n) search without ever rebalancing a tree.

Table of Contents

  1. Introduction & Motivation
  2. Prerequisites
  3. Intersection of Two Linked Lists
  4. Core Insight for LRU Cache
  5. LRU Cache Implementation
  6. LRU Cache Complexity
  7. Skip List — Core Insight
  8. Skip List — Implementation
  9. Skip List — Complexity
  10. Applications & Alternatives
  11. Exercises & Mastery
  12. Summary Cheat Sheet

1. Introduction & Motivation

A singly or doubly linked list on its own is a modest tool: fast insertion and deletion at known positions, but slow search, since finding anything requires walking node by node. This lesson looks at two designs that get far more mileage out of that simple structure by combining it with something else, or by adding structure on top of it.

The first, the LRU (Least Recently Used) Cache, pairs a doubly linked list with a hashmap so that both "find a key" and "evict the oldest entry" run in O(1) time — something neither structure achieves alone. The second, the Skip List, stacks several linked lists at increasing "skip" distances on top of a sorted base list, turning an O(n) linear scan into an O(log n) expected search without any of the rotation logic a balanced binary search tree needs. Along the way we also solve Intersection of Two Linked Lists (LeetCode 160), a two-pointer problem that sharpens the pointer-manipulation skills both later designs depend on.

2. Prerequisites

This lesson builds directly on two earlier posts and does not repeat their material:

  • The Doubly Linked List section of Part 6: Linked Lists Guide covers node insertion and O(1) deletion given a node reference — exactly the mechanics the LRU Cache's internal list reuses for moving a node to the front and evicting from the back. If prev/next pointer surgery is unfamiliar, read that section first.
  • The Hash Tables section of Part 11 covers average-case O(1) hashmap lookup, insertion, and deletion — the second half of the LRU Cache's combo.

You should also be comfortable with the two-pointer traversal and cycle-detection patterns from the Two Pointer Techniques section of the same guide; the intersection problem below is a direct application of that style of reasoning.

3. Intersection of Two Linked Lists (LeetCode 160)

Given the heads of two singly linked lists that may or may not share a tail, find the node where they intersect, or return nothing if they never merge. Comparing values is not enough — a value can repeat by coincidence. The intersection is defined by shared node identity, the point where two chains of pointers become one.

A hashmap of visited nodes solves this in O(m+n) time and O(m) space. The elegant two-pointer trick solves it in O(m+n) time and O(1) extra space: walk pointer a down list A and pointer b down list B; whenever a pointer falls off the end of its own list, redirect it to the head of the other list. Because pointer a then travels lenA + lenB nodes in total and pointer b travels lenB + lenA nodes, both pointers arrive at the intersection node — if one exists — after exactly the same number of steps, having each walked both lists' unique prefixes exactly once. If there is no intersection, both pointers become None/null at the same step and the loop ends with no match.

Worked Example

Hand trace on two different-length lists

List A (length 4): 1 → 2 → 8 → 9. List B (length 3): 6 → 8 → 9, where the nodes holding 8 and 9 are the same objects in both lists (the true intersection starts at the node holding 8). Pointer a starts at A's head, pointer b starts at B's head. At each step, compare first, then advance each pointer along its own list, or swap to the other list's head once it runs out.

Stepa (before move)b (before move)Same node?Next move
016Noa→2, b→8
128Noa→8, b→9
289Noa→9, b→null
39nullNoa→null, b→headA (1)
4null1Noa→headB (6), b→2
562Noa→8, b→8
688Yesloop ends, return node holding 8

Swapping heads is what synchronizes the pointers: by the time they might meet, pointer a has walked A's 2 unique nodes plus all of B (3 nodes) plus is now re-walking A, and pointer b has walked B's 1 unique node plus all of A (4 nodes) plus is now re-walking B. Both have covered lenA + lenB = 7 total nodes by step 6, which lands them on the same shared node at the same time — no length pre-computation needed.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_intersection_node(head_a, head_b):
    if head_a is None or head_b is None:
        return None
    a, b = head_a, head_b
    while a is not b:
        a = a.next if a is not None else head_b
        b = b.next if b is not None else head_a
    return a

# Build two lists sharing a tail: A = 1 -> 2 -> [8 -> 9], B = 6 -> [8 -> 9]
shared_9 = ListNode(9)
shared_8 = ListNode(8, shared_9)
head_a = ListNode(1, ListNode(2, shared_8))
head_b = ListNode(6, shared_8)

result = get_intersection_node(head_a, head_b)
print("Intersection value:", result.val if result else None)  # Intersection value: 8

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val, ListNode* next = nullptr) : val(val), next(next) {}
};

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (headA == nullptr || headB == nullptr) {
        return nullptr;
    }
    ListNode* a = headA;
    ListNode* b = headB;
    while (a != b) {
        a = (a != nullptr) ? a->next : headB;
        b = (b != nullptr) ? b->next : headA;
    }
    return a;
}

int main() {
    // Build two lists sharing a tail: A = 1 -> 2 -> [8 -> 9], B = 6 -> [8 -> 9]
    ListNode* shared9 = new ListNode(9);
    ListNode* shared8 = new ListNode(8, shared9);
    ListNode* headA = new ListNode(1, new ListNode(2, shared8));
    ListNode* headB = new ListNode(6, shared8);

    ListNode* result = getIntersectionNode(headA, headB);
    std::cout << "Intersection value: " << (result ? result->val : -1) << '\n';  // Intersection value: 8
}

public class IntersectionOfLinkedLists {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }

    public static void main(String[] args) {
        // Build two lists sharing a tail: A = 1 -> 2 -> [8 -> 9], B = 6 -> [8 -> 9]
        ListNode shared9 = new ListNode(9);
        ListNode shared8 = new ListNode(8, shared9);
        ListNode headA = new ListNode(1, new ListNode(2, shared8));
        ListNode headB = new ListNode(6, shared8);

        ListNode result = getIntersectionNode(headA, headB);
        System.out.println("Intersection value: " + (result != null ? result.val : -1)); // Intersection value: 8
    }
}

4. Core Insight for LRU Cache

Core insight: An LRU Cache needs two things at once on every operation: locate a key's value instantly, and know which entry is least recently used so it can be evicted instantly when the cache is full. A hashmap alone gives O(1) lookup by key, but it has no notion of order, so finding "the oldest entry" means scanning everything — O(n). A doubly linked list alone gives O(1) reordering (move a node to the front) and O(1) removal of the tail, but finding which node corresponds to a given key means walking the list — again O(n). Neither structure achieves O(1) for both get and put by itself.

The fix is to run them side by side over the same set of nodes. The doubly linked list stores nodes in recency order — most recently used near the head, least recently used near the tail — and gives O(1) "move this node to the front" and O(1) "drop the tail node" once you already have a node reference. The hashmap maps each key directly to its node object in that list, so a get(key) or put(key, value) never has to search: the hashmap supplies the node reference in O(1), and the list repositions or evicts that node in O(1). Every node lives in exactly one place in memory but is reachable through both structures.

5. LRU Cache (LeetCode 146)

The implementation below uses a doubly linked list with two dummy sentinel nodes — head and tail — so that every real node always has a non-null prev and next, removing edge cases for the first/last real node. Recency order runs head-side (most recently used) to tail-side (least recently used): inserting a node always places it right after head, and eviction always removes the node right before tail. The hashmap stores key → node.

class _Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = _Node()  # dummy, most-recently-used side
        self.tail = _Node()  # dummy, least-recently-used side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) >= self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = _Node(key, value)
        self.map[key] = node
        self._add_front(node)

# Canonical LeetCode 146 sequence, capacity 2
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))     # 1
cache.put(3, 3)          # evicts key 2
print(cache.get(2))     # -1 (evicted)
cache.put(4, 4)          # evicts key 1
print(cache.get(1))     # -1 (evicted)
print(cache.get(3))     # 3
print(cache.get(4))     # 4

#include <iostream>
#include <unordered_map>

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int key = 0, int value = 0) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, Node*> map;
    Node* head;  // dummy, most-recently-used side
    Node* tail;  // dummy, least-recently-used side

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1;
        }
        Node* node = it->second;
        remove(node);
        addFront(node);
        return node->value;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            Node* node = it->second;
            node->value = value;
            remove(node);
            addFront(node);
            return;
        }
        if ((int)map.size() >= capacity) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* node = new Node(key, value);
        map[key] = node;
        addFront(node);
    }
};

int main() {
    // Canonical LeetCode 146 sequence, capacity 2
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << '\n';   // 1
    cache.put(3, 3);                        // evicts key 2
    std::cout << cache.get(2) << '\n';   // -1
    cache.put(4, 4);                        // evicts key 1
    std::cout << cache.get(1) << '\n';   // -1
    std::cout << cache.get(3) << '\n';   // 3
    std::cout << cache.get(4) << '\n';   // 4
}

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node() {}
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node();  // dummy, most-recently-used side
    private final Node tail = new Node();  // dummy, least-recently-used side

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        addFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addFront(node);
            return;
        }
        if (map.size() >= capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addFront(fresh);
    }

    public static void main(String[] args) {
        // Canonical LeetCode 146 sequence, capacity 2
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));   // 1
        cache.put(3, 3);                     // evicts key 2
        System.out.println(cache.get(2));   // -1
        cache.put(4, 4);                     // evicts key 1
        System.out.println(cache.get(1));   // -1
        System.out.println(cache.get(3));   // 3
        System.out.println(cache.get(4));   // 4
    }
}

Tracing the recency order (front = most recently used, back = least recently used) confirms the eviction choices:

OperationOrder front → back afterReturned
put(1, 1)[1]—
put(2, 2)[2, 1]—
get(1)[1, 2]1
put(3, 3)[3, 1] (evicted 2, the back-most entry)—
get(2)[3, 1]-1 (not found)
put(4, 4)[4, 3] (evicted 1, the back-most entry)—
get(1)[4, 3]-1 (not found)
get(3)[3, 4]3
get(4)[4, 3]4

6. Complexity Analysis for LRU Cache

Time: $O(1)$ for both get and put — a hashmap lookup plus a constant number of pointer updates on the doubly linked list, regardless of how many entries the cache holds. Space: $O(\text{capacity})$ — one node and one hashmap entry per cached key, plus the two dummy sentinels.

7. Skip List — Core Insight

Core insight: A plain sorted singly linked list gives O(1) insertion once you know where to insert, but finding that position takes O(n), since there is no way to skip ahead. A Skip List fixes this by building extra "express lane" linked lists above the base list. Level 0 is the full sorted list; level 1 links roughly every second node; level 2 links roughly every fourth node; and so on. A search starts at the top, sparsest level and moves right as far as possible without overshooting the target, then drops down a level and repeats, funneling toward the target through fewer and fewer nodes per level.

Which nodes appear at which levels is decided by a coin flip at insertion time: a new node is promoted to level 1 with probability $p$ (typically $0.5$), promoted again to level 2 with probability $p$ again, and so on, so roughly half as many nodes populate each successive level. This randomization is what gives a Skip List its expected $O(\log n)$ height and search cost without any deterministic rebalancing step — there is no rotation logic and no invariant to repair after every insert or delete, unlike a self-balancing BST. See Part 9: BST, AVL & Red-Black Trees for that deterministic-rebalancing alternative, which trades randomized simplicity for worst-case (rather than expected) logarithmic guarantees.

8. Skip List — Implementation

Each node stores a value and a forward array of next-pointers, one per level the node participates in. The list keeps a header sentinel with pointers at every possible level and tracks the highest level currently in use. search, insert, and delete all share the same top-down descent: at each level, advance while the next node's value is still less than the target, then drop a level.

import random

class _SkipNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.header = _SkipNode(None, self.MAX_LEVEL)
        self.level = 0  # highest level currently in use

    def _random_level(self):
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, target):
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] is not None and current.forward[i].value < target:
                current = current.forward[i]
        current = current.forward[0]
        return current is not None and current.value == target

    def insert(self, value):
        update = [self.header] * (self.MAX_LEVEL + 1)
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] is not None and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]
        if current is not None and current.value == value:
            return  # no duplicates
        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level
        new_node = _SkipNode(value, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def delete(self, value):
        update = [self.header] * (self.MAX_LEVEL + 1)
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] is not None and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]
        if current is None or current.value != value:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] is not current:
                break
            update[i].forward[i] = current.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1
        return True

random.seed(42)
skip_list = SkipList()
for v in (3, 6, 7, 9, 12):
    skip_list.insert(v)

print("search(7):", skip_list.search(7))   # True
print("search(8):", skip_list.search(8))   # False
skip_list.delete(6)
print("search(6) after delete:", skip_list.search(6))  # False

#include <iostream>
#include <vector>
#include <cstdlib>

const int MAX_LEVEL = 16;
const double P = 0.5;

struct Node {
    int value;
    std::vector<Node*> forward;
    Node(int value, int level) : value(value), forward(level + 1, nullptr) {}
};

class SkipList {
private:
    Node* header;
    int level;  // highest level currently in use

    int randomLevel() {
        int lvl = 0;
        while (((double)rand() / RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

public:
    SkipList() {
        header = new Node(0, MAX_LEVEL);
        level = 0;
    }

    bool search(int target) {
        Node* current = header;
        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->value < target) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return current != nullptr && current->value == target;
    }

    void insert(int value) {
        std::vector<Node*> update(MAX_LEVEL + 1, header);
        Node* current = header;
        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        current = current->forward[0];
        if (current != nullptr && current->value == value) {
            return;  // no duplicates
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }
        Node* newNode = new Node(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    // named remove(), not delete(), since delete is a reserved keyword in C++
    bool remove(int value) {
        std::vector<Node*> update(MAX_LEVEL + 1, header);
        Node* current = header;
        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        current = current->forward[0];
        if (current == nullptr || current->value != value) {
            return false;
        }
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }
        delete current;
        while (level > 0 && header->forward[level] == nullptr) {
            level--;
        }
        return true;
    }
};

int main() {
    srand(42);
    SkipList list;
    for (int v : {3, 6, 7, 9, 12}) {
        list.insert(v);
    }
    std::cout << std::boolalpha;
    std::cout << "search(7): " << list.search(7) << '\n';   // true
    std::cout << "search(8): " << list.search(8) << '\n';   // false
    list.remove(6);
    std::cout << "search(6) after remove: " << list.search(6) << '\n';  // false
}

import java.util.Arrays;
import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;

    private static class Node {
        int value;
        Node[] forward;
        Node(int value, int level) {
            this.value = value;
            this.forward = new Node[level + 1];
        }
    }

    private final Node header;
    private int level;  // highest level currently in use
    private final Random random = new Random(42);

    public SkipList() {
        header = new Node(0, MAX_LEVEL);
        level = 0;
    }

    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    public boolean search(int target) {
        Node current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < target) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == target;
    }

    public void insert(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Arrays.fill(update, header);
        Node current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        current = current.forward[0];
        if (current != null && current.value == value) {
            return;  // no duplicates
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }
        Node newNode = new Node(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean delete(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Arrays.fill(update, header);
        Node current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        current = current.forward[0];
        if (current == null || current.value != value) {
            return false;
        }
        for (int i = 0; i <= level; i++) {
            if (update[i].forward[i] != current) {
                break;
            }
            update[i].forward[i] = current.forward[i];
        }
        while (level > 0 && header.forward[level] == null) {
            level--;
        }
        return true;
    }

    public static void main(String[] args) {
        SkipList list = new SkipList();
        for (int v : new int[]{3, 6, 7, 9, 12}) {
            list.insert(v);
        }
        System.out.println("search(7): " + list.search(7));   // true
        System.out.println("search(8): " + list.search(8));   // false
        list.delete(6);
        System.out.println("search(6) after delete: " + list.search(6));  // false
    }
}

9. Skip List — Complexity Analysis

Time: $O(\log n)$ expected time for search, insert, and delete — each level descent is expected to examine only a small constant number of nodes before dropping down, and there are an expected $O(\log n)$ levels. Space: $O(n)$ expected — every element occupies exactly one level-0 node, and the geometric level-promotion process adds only a small constant-factor overhead of extra forward pointers per node on average (about $\frac{1}{1-p}$ pointers per node for promotion probability $p$).

10. Applications & Alternatives

Where these structures show up in real systems

  • LRU Cache — OS page replacement: approximations of LRU decide which memory pages to evict when physical RAM is full.
  • LRU Cache — browser cache: browsers evict least-recently-viewed cached resources first when local storage limits are hit.
  • LRU Cache — database buffer pools: database engines keep recently accessed disk pages in memory using LRU or LRU-like eviction policies.
  • Skip List — Redis sorted sets: Redis implements the ZSET data type internally with a Skip List for ordered, O(log n) range and rank operations.
  • Skip List — LevelDB / RocksDB memtables: both storage engines use Skip Lists as the in-memory sorted structure that buffers writes before they are flushed to disk.

11. Exercises & Mastery

Easy

  1. Design a fixed-size circular buffer cache with simple FIFO eviction (oldest inserted entry is evicted first, regardless of access pattern). Contrast it with the LRU Cache above: what workload makes FIFO perform identically to LRU, and what workload makes FIFO perform much worse?

Medium

  1. LFU Cache (LeetCode 460): design a cache that evicts the least frequently used key instead of the least recently used one, breaking frequency ties by recency. Sketch the data structures needed — a hashmap from key to (value, frequency), a hashmap from frequency to a doubly linked list of keys at that frequency (ordered by recency), and a pointer to the minimum frequency currently in use — so that get and put both remain O(1). A brief sketch of the frequency-bucket structure is sufficient; a fully working implementation is not required.

Hard

  1. Extend the Skip List above to support a range query, range(low, high), that returns all stored values in [low, high] in sorted order. Use level 0's descent to locate low in O(log n), then walk level 0 forward, collecting values until exceeding high. State the total complexity in terms of n and the number of matching elements k.
Mastery challenge: A service must cache the last 10,000 API responses with O(1) get/put and evict the least recently used entry when full, while a second, independent subsystem must maintain a sorted index of a few million active session IDs supporting fast insert, delete, and "is this ID present" queries without periodic rebuild. Choose and justify a structure for each subsystem, state its complexity, and explain what would change if the session index also needed fast "give me the 1000 smallest active IDs" range queries.

Review rhythm: tomorrow, redraw the LRU Cache's doubly linked list plus hashmap from memory and re-derive why each alone is insufficient; next week, implement both the LRU Cache and the Skip List in a language you did not use here; several weeks later, connect the "randomized level promotion" idea in Skip Lists to other randomized algorithms you have studied, such as randomized quicksort.

12. Summary Cheat Sheet

  • Intersection of Two Linked Lists: two pointers, each swapping to the other list's head on reaching its own end, meet at the intersection (or both reach null) after lenA + lenB steps — O(m+n) time, O(1) space.
  • LRU Cache: doubly linked list (recency order, O(1) reorder/evict) + hashmap (key → node, O(1) lookup) together give O(1) get and put; neither structure alone achieves that.
  • LRU Cache complexity: O(1) time for get/put, O(capacity) space.
  • Skip List: layered linked lists with randomized level promotion give O(log n) expected search/insert/delete, without the rotation logic of a balanced BST.
  • Skip List complexity: O(log n) expected time for all operations, O(n) expected space with a small constant-factor overhead.
  • Real systems: LRU underlies OS page replacement, browser caches, and database buffer pools; Skip Lists underlie Redis sorted sets and LSM-tree memtables (LevelDB/RocksDB).

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Browse the complete 18-level algorithm curriculum and practical project sequence.

Open the DSA Hub
Part 6: Linked Lists Guide

The full linked-list foundation this lesson builds on: singly/doubly/circular lists, reversal, cycle detection, and merge sort on lists.

Read the Linked Lists Guide
Part 11: Heaps, Sorting & Hashing

Hash tables, heaps, and sorting algorithms — the hashmap half of the LRU Cache combo lives here.

Read the Heaps, Sorting & Hashing Guide