Doubly & circular lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        +-----------------------------------+
        |       DOUBLY LINKED LIST NODE     |
        |  [ prev ptr | data | next ptr ]   |
        +-----------------------------------+

     +<=================>+<=================>+
     |                   |                   |
+----+----+         +----+----+         +----+----+
|   10    | <=====> |   20    | <=====> |   30    |
+----+----+         +----+----+         +----+----+
     |                   |                   |
null <                   >                   > null

O(1) Self-Unlink of Node 20:
node20.prev.next = node20.next;   // 10 points directly to 30
node20.next.prev = node20.prev;   // 30 points directly back to 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// Unconditional O(1) Node Unlinking with Sentinels
public class DoubleSentinelList {
    static class DNode {
        int key, val;
        DNode prev, next;
        DNode(int k, int v) { key = k; val = v; }
    }

    private final DNode head = new DNode(0, 0);
    private final DNode tail = new DNode(0, 0);

    public DoubleSentinelList() {
        head.next = tail;
        tail.prev = head;
    }

    // O(1) removal of any node given only its direct reference
    public void unlink(DNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }

    // O(1) insertion right before the tail sentinel (Most Recently Used)
    public void addLast(DNode node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

Most Recently Used (MRU)               Least Recently Used (LRU)
             |                                              |
             v                                              v
dummyHead <=====> [ Key: "A" | Val: 1 ] <=====> [ Key: "B" | Val: 2 ] <=====> dummyTail
   ^                       ^                               ^                       ^
   |                       |                               |                       |
   +-----------------------+-------------------------------+-----------------------+
                           |                               |
                 HashMap["A"] -> Node A          HashMap["B"] -> Node B

Get("B"): Unlink Node B -> Re-insert at dummyHead.next (Promote to MRU in O(1))!
Put("C"): If full, evict dummyTail.prev (Remove LRU in O(1))!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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

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

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToTail(node); // Promoted to MRU
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToTail(node);
            return;
        }
        if (map.size() >= capacity) {
            // Evict least recently used (first after head sentinel)
            Node lru = head.next;
            removeNode(lru);
            map.remove(lru.key);
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToTail(fresh);
    }

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

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

    private void moveToTail(Node node) {
        removeNode(node);
        addToTail(node);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Josephus Circle Problem via Circular Singly Linked List
public class JosephusCircle {
    static class Node {
        int id;
        Node next;
        Node(int id) { this.id = id; }
    }

    public static int findSurvivor(int n, int k) {
        if (n == 1) return 1;

        // Build circular linked list: 1 -> 2 -> ... -> n -> 1
        Node head = new Node(1);
        Node prev = head;
        for (int i = 2; i <= n; i++) {
            prev.next = new Node(i);
            prev = prev.next;
        }
        prev.next = head; // Close the circular ring

        Node curr = head;
        // Eliminate until 1 node remains (points to itself)
        while (curr.next != curr) {
            // Count k - 1 steps to locate predecessor of target node
            for (int count = 1; count < k - 1; count++) {
                curr = curr.next;
            }
            // Eliminate k-th node
            curr.next = curr.next.next;
            curr = curr.next; // Advance to next round
        }

        return curr.id;
    }
}