PART 14 | RANDOM POINTER + LRU CACHE

Pavan pithdiya

13 min read

·

1 day ago

--

Listen

Share

Advanced Linked Lists in Java — Random Pointer, LRU Cache & Design

Press enter or click to view image in full size

Linked Lists are not limited to simple next pointers.

In advanced problems, a node may contain:

• A next pointer
• A prev pointer
• A random pointer
• Additional metadata such as keys, values, or frequency

Two important problems that combine these ideas are:

1. Copy List with Random Pointer
2. LRU Cache

These problems are especially useful for understanding how Linked Lists work together with HashMaps to achieve efficient O(1) operations.

Part A — Copy List with Random Pointer

1. What Is a Random Pointer?

A normal singly linked list looks like:

A → B → C → null

Each node contains:

data
next

A random-pointer linked list contains an additional pointer:

data
next
random

For example:

A → B → C → null

A.random → C
B.random → A
C.random → B

The random pointer can point to:

• Any node in the list
• The same node
• null

2. Problem

Given a linked list where every node contains:

next
random

Create a deep copy of the entire list.

The copied list must contain completely new nodes.

For example:

Original:

A → B → C
↓   ↓   ↓
C   A   B

Copy:
A' → B' → C'
↓    ↓    ↓
C'   A'   B'

The copied nodes must not point to the original nodes.

3. Node Structure

In Java:

class RandomNode {

int data;
    RandomNode next;
    RandomNode random;
    RandomNode(int data) {
        this.data = data;
    }
}

4. Why Is This Problem Tricky?

Copying the next pointer is easy.

For example:

copy.next = original.next;

But this would be wrong.

Why?

Because original.next points to an original node.

We need:

Original A → Original B

Copy A' → Copy B'

Therefore:

A'.next = B'

not:

A'.next = B

The same problem exists with the random pointer.

5. Approach 1 — HashMap

The easiest solution is to use a HashMap.

The idea is:

Original Node → Copy Node

For example:

A → A'
B → B'
C → C'

Then we can easily find the copied version of any original node.

6. Algorithm

Step 1 — Create copy nodes

Traverse the original list.

For every node:

original → copy

Store it in a HashMap.

Step 2 — Connect next pointers

For every original node:

copy.next = map.get(original.next);

Step 3 — Connect random pointers

Similarly:

copy.random = map.get(original.random);

Step 4 — Return the copied head

7. HashMap Java Solution

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

public static RandomNode copyRandomList(RandomNode head) {
    if (head == null) {
        return null;
    }
    Map<RandomNode, RandomNode> map = new HashMap<>();
    RandomNode current = head;
    // Step 1: Create copy nodes
    while (current != null) {
        map.put(current, new RandomNode(current.data));
        current = current.next;
    }
    // Step 2: Connect next and random pointers
    current = head;
    while (current != null) {
        RandomNode copy = map.get(current);
        copy.next = map.get(current.next);
        copy.random = map.get(current.random);
        current = current.next;
    }
    return map.get(head);
}

8. HashMap Dry Run

Suppose:

Original:

A → B → C
A.random → C
B.random → A
C.random → B

After the first traversal:

HashMap

A → A'
B → B'
C → C'

Now connect next:

A'.next → B'
B'.next → C'
C'.next → null

Connect random:

A'.random → C'
B'.random → A'
C'.random → B'

Final result:

A' → B' → C'
↓    ↓    ↓
C'   A'   B'

The original and copied lists are completely separate.

9. Complexity — HashMap Approach

| Operation        | Complexity |
| ---------------- | ---------- |
| Create copies    | O(n)       |
| Connect pointers | O(n)       |
| **Total Time**   | **O(n)**   |
| **Extra Space**  | **O(n)**   |

The HashMap requires O(n) extra space.

10. Approach 2 — Interleaving

Can we solve this using O(1) extra space?

Yes.

The trick is to temporarily insert each copied node immediately after its original node.

Original:

A → B → C

After inserting copies:

A → A' → B → B' → C → C'

This is called the interleaving technique.

11. Step 1 — Create Copy Nodes

Original:

A → B → C

Insert copies:

A → A' → B → B' → C → C'

Java:

RandomNode current = head;

while (current != null) {
    RandomNode copy = new RandomNode(current.data);
    copy.next = current.next;
    current.next = copy;
    current = copy.next;
}

12. Step 2 — Connect Random Pointers

This is where interleaving becomes useful.

Suppose:

A.random → C

Because every original node is followed by its copy:

C → C'

Therefore:

A.random.next

is:

C'

So we can write:

copy.random = current.random.next;

Complete loop:

current = head;

while (current != null) {
    RandomNode copy = current.next;
    if (current.random != null) {
        copy.random = current.random.next;
    }
    current = copy.next;
}

13. Step 3 — Separate the Lists

Currently:

A → A' → B → B' → C → C'

We need:

Original:
A → B → C

Copy:
A' → B' → C'

We separate them by adjusting next.

RandomNode copyHead = head.next;

current = head;
while (current != null) {
    RandomNode copy = current.next;
    current.next = copy.next;
    if (copy.next != null) {
        copy.next = copy.next.next;
    }
    current = current.next;
}

14. Complete Interleaving Solution

public static RandomNode copyRandomList(RandomNode head) {

if (head == null) {
        return null;
    }
    // Step 1: Insert copied nodes
    RandomNode current = head;
    while (current != null) {
        RandomNode copy = new RandomNode(current.data);
        copy.next = current.next;
        current.next = copy;
        current = copy.next;
    }
    // Step 2: Set random pointers
    current = head;
    while (current != null) {
        RandomNode copy = current.next;
        if (current.random != null) {
            copy.random = current.random.next;
        }
        current = copy.next;
    }
    // Step 3: Separate original and copied lists
    RandomNode copyHead = head.next;
    current = head;
    while (current != null) {
        RandomNode copy = current.next;
        current.next = copy.next;
        if (copy.next != null) {
            copy.next = copy.next.next;
        }
        current = current.next;
    }
    return copyHead;
}

15. Interleaving Dry Run

Consider:

A → B → C

Random pointers:

A.random → C
B.random → A
C.random → B

After Step 1

A → A' → B → B' → C → C'

After Step 2

A'.random → C'
B'.random → A'
C'.random → B'

After Step 3

Original:

A → B → C

Copy:

A' → B' → C'

Random pointers:

A'.random → C'
B'.random → A'
C'.random → B'

16. HashMap vs Interleaving

| Approach     | Time | Extra Space | Difficulty |
| ------------ | ---- | ----------- | ---------- |
| HashMap      | O(n) | O(n)        | Easy       |
| Interleaving | O(n) | O(1)        | Medium     |

Interview Tip

If the interviewer asks:

Can you solve it without extra HashMap space?

Think about the interleaving technique.

Part B — LRU Cache

Now let’s move to one of the most important design problems involving Linked Lists.

17. What Is an LRU Cache?

LRU stands for:

Least Recently Used

An LRU Cache stores a limited number of items.

When the cache becomes full and we need to insert a new item, we remove the item that has been used least recently.

Example:

Capacity = 3

Cache:

A B C

If A is the least recently used item:

A ← Remove

New item D:

D B C

18. Most Recently Used vs Least Recently Used

Suppose:

A B C

Assume the left side represents the most recently used item.

MRU                    LRU
 ↓                      ↓
A → B → C

If we access B:

B → A → C

Now B becomes the most recently used item.

19. Required Operations

An LRU Cache normally supports:

get(key)
put(key, value)

Both operations should be:

O(1)

This is the main challenge.

20. Why HashMap Alone Is Not Enough

A HashMap gives us:

key → value

and allows:

get(key) → O(1)

But an LRU Cache also needs to know:

Which item was used least recently?

A normal HashMap does not provide the required ordering operations efficiently.

We need to:

• Move recently used nodes
• Remove the least recently used node
• Insert nodes at the front
• Remove nodes from the middle

Therefore, HashMap alone is insufficient.

21. Why Doubly Linked List?

A Doubly Linked List provides:

prev
next

For example:

A ⇄ B ⇄ C

If we have a reference to B, we can remove it in:

O(1)

by changing:

A.next = C
C.prev = A

With a singly linked list, finding the previous node would require traversal.

Therefore:

Doubly Linked List allows O(1) insertion and deletion when we already have the node.

22. HashMap + Doubly Linked List

The ideal design is:

HashMap
   ↓
key → Node

and:

Doubly Linked List

MRU                         LRU
 ↓                           ↓
HEAD ⇄ A ⇄ B ⇄ C ⇄ D ⇄ TAIL

The HashMap tells us:

Where is the node?

The Doubly Linked List tells us:

What is its usage order?

Together:

HashMap + Doubly Linked List

give us:

get() → O(1)
put() → O(1)

23. LRU Cache Design

We use two dummy nodes:

HEAD
TAIL

The actual nodes are between them.

HEAD ⇄ A ⇄ B ⇄ C ⇄ TAIL

Meaning:

HEAD → Most Recently Used
TAIL → Least Recently Used

So:

HEAD ⇄ MRU ⇄ ... ⇄ LRU ⇄ TAIL

24. Important Operations

We need four helper operations.

1. Remove Node

Remove a node from its current position.

A ⇄ B ⇄ C

Remove B:

A ⇄ C

2. Insert at Front

Add a node immediately after HEAD.

HEAD ⇄ A ⇄ B

Insert C:

HEAD ⇄ C ⇄ A ⇄ B

3. Move to Front

If B is accessed:

Before:

HEAD ⇄ A ⇄ B ⇄ C ⇄ TAIL

After:

HEAD ⇄ B ⇄ A ⇄ C ⇄ TAIL

4. Remove Last

The node before TAIL is the least recently used node.

HEAD ⇄ A ⇄ B ⇄ C ⇄ TAIL
              ↑
             LRU

Remove C.

25. Node Structure

Each cache node stores:

key
value
prev
next

Java:

class Node {

int key;
    int value;
    Node prev;
    Node next;
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Why store the key inside the node?

Because when we evict a node, we need to remove its key from the HashMap:

map.remove(node.key);

26. Complete LRU Cache Implementation

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

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;
    private final Node tail;
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    // Remove a node from the linked list
    private void remove(Node node) {
        Node previous = node.prev;
        Node next = node.next;
        previous.next = next;
        next.prev = previous;
    }
    // Insert node immediately after head
    private void insertAtFront(Node node) {
        Node first = head.next;
        node.next = first;
        node.prev = head;
        head.next = node;
        first.prev = node;
    }
    // Get value
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        // Move to front because it was recently used
        remove(node);
        insertAtFront(node);
        return node.value;
    }
    // Put key-value
    public void put(int key, int value) {
        // Key already exists
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            insertAtFront(node);
            return;
        }
        // Create new node
        Node node = new Node(key, value);
        map.put(key, node);
        insertAtFront(node);
        // Cache is full
        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

27. Understanding get()

Suppose:

HEAD ⇄ A ⇄ B ⇄ C ⇄ TAIL

Call:

get(B);

B was recently accessed.

So:

Step 1

Remove B.

HEAD ⇄ A ⇄ C ⇄ TAIL

Step 2

Insert B after HEAD.

HEAD ⇄ B ⇄ A ⇄ C ⇄ TAIL

Therefore:

B = MRU
C = LRU

28. Understanding put()

Suppose:

Capacity = 3

Current cache:

HEAD ⇄ A ⇄ B ⇄ C ⇄ TAIL

Insert:

put(D, 4)

First:

HEAD ⇄ D ⇄ A ⇄ B ⇄ C ⇄ TAIL

Now size becomes:

4

But capacity is:

3

Therefore, remove:

C

Final:

HEAD ⇄ D ⇄ A ⇄ B ⇄ TAIL

C was the least recently used item.

29. Complete LRU Dry Run

Let’s use:

capacity = 2

Operations:

put(1, 10)
put(2, 20)
get(1)
put(3, 30)
get(2)

Step 1 — put(1, 10)

HEAD ⇄ 1 ⇄ TAIL

HashMap:

1 → Node(1,10)

Step 2 — put(2, 20)

HEAD ⇄ 2 ⇄ 1 ⇄ TAIL

Most recently used:

2

Least recently used:

1

Step 3 — get(1)

We access key 1.

Move it to the front:

HEAD ⇄ 1 ⇄ 2 ⇄ TAIL

Now:

MRU = 1
LRU = 2

Step 4 — put(3, 30)

Insert 3 at the front:

HEAD ⇄ 3 ⇄ 1 ⇄ 2 ⇄ TAIL

Capacity is exceeded.

The LRU node is:

2

Remove it:

HEAD ⇄ 3 ⇄ 1 ⇄ TAIL

Step 5 — get(2)

Key 2 was evicted.

Therefore:

get(2)

returns:

-1

30. LRU Cache Pointer Operations

The most important operations to understand are:

Remove

previous ⇄ node ⇄ next

After removal:

previous ⇄ next

Java:

node.prev.next = node.next;
node.next.prev = node.prev;

Insert at Front

Before:

HEAD ⇄ first

After inserting node:

HEAD ⇄ node ⇄ first

Java:

node.next = head.next;
node.prev = head;

head.next.prev = node;
head.next = node;

31. Why Dummy Head and Tail?

Without dummy nodes, we need special handling for:

• Empty list
• First node
• Last node
• Removing head
• Removing tail

With dummy nodes:

HEAD ⇄ ... ⇄ TAIL

Every real node always has:

prev
next

This makes insertion and deletion much simpler.

This is another excellent example of the Dummy Node Technique from earlier parts of the series.

32. LRU Cache Complexity

| Operation             | Time Complexity | Extra Space     |
| --------------------- | --------------- | --------------- |
| `get()`               | O(1)            | O(1)            |
| `put()`               | O(1)            | O(1)            |
| Insert node           | O(1)            | O(1)            |
| Remove node           | O(1)            | O(1)            |
| Move to front         | O(1)            | O(1)            |
| Evict LRU             | O(1)            | O(1)            |
| **Total Cache Space** | —               | **O(capacity)** |

The entire cache requires:

O(capacity)

space.

33. Why Is LRU Cache O(1)?

This is the key interview question.

HashMap

Find a node:

key → Node

in:

O(1)

Doubly Linked List

Move or remove that node:

O(1)

Tail

Find LRU:

tail.prev

in:

O(1)

Therefore:

get() → HashMap + DLL → O(1)
put() → HashMap + DLL → O(1)

34. Common Mistakes in LRU Cache

Mistake 1 — Using Only HashMap

HashMap does not provide the required LRU ordering behavior.

Mistake 2 — Using Singly Linked List

Removing a node requires finding its previous node.

That can take:

O(n)

Mistake 3 — Forgetting to Update HashMap

When an item is evicted:

map.remove(lru.key);

must also happen.

Otherwise, the HashMap contains a stale node.

Mistake 4 — Not Moving Accessed Nodes

Calling:

get(key)

must make the node the most recently used.

Mistake 5 — Forgetting Existing Keys

If put() is called with an existing key:

put(key, newValue);

we should:

1. Update the value
2. Move the node to the front

Mistake 6 — Incorrect Pointer Updates

Always carefully update both:

prev
next

For a Doubly Linked List:

A ⇄ B ⇄ C

Removing B requires:

A.next = C
C.prev = A

35. Copy Random Pointer vs LRU Cache

Both problems combine Linked Lists with another concept.

| Problem          | Linked List        | Additional Structure   | Main Challenge         | Target               |
| ---------------- | ------------------ | ---------------------- | ---------------------- | -------------------- |
| Copy Random List | Singly Linked List | HashMap / Interleaving | Copy random references | Deep Copy            |
| LRU Cache        | Doubly Linked List | HashMap                | Maintain usage order   | O(1) `get` and `put` |

36. Important Patterns From This Part

This part introduces several reusable patterns.

Pattern 1 — HashMap + Linked List

HashMap
   ↓
key → Node

Useful when we need:

Fast lookup + ordering

Pattern 2 — Interleaving

A → B → C

A → A' → B → B' → C → C'

Useful for:

Copying linked structures

Pattern 3 — Dummy Nodes

HEAD ⇄ ... ⇄ TAIL

Useful for simplifying:

Insertion
Deletion
Edge cases

Pattern 4 — Node Identity

For linked-list problems, remember:

node1 == node2

checks whether two references point to the same node.

Whereas:

node1.data == node2.data

only compares values.

This distinction is extremely important for:

• Random pointers
• Cycle detection
• Intersection
• LRU Cache
• Deep-copy problems

37. Interview Questions

Beginner

1. What does LRU stand for?
2. What is a random pointer?
3. Why do we need a HashMap for copying a random-pointer list?
4. What is a deep copy?
5. Why is a Doubly Linked List useful for LRU Cache?

Intermediate

1. Why can’t HashMap alone implement an LRU Cache efficiently?
2. Why can’t a singly linked list easily provide O(1) deletion?
3. How does the interleaving approach copy random pointers?
4. Why are dummy head and tail nodes useful?
5. Why is get() an update operation in an LRU Cache?

Advanced

1. How would you implement LRU Cache using generics?
2. How would you make an LRU Cache thread-safe?
3. What is the difference between LRU and LFU?
4. Can an LRU Cache be implemented using Java’s LinkedHashMap?
5. How would you design a distributed cache?
6. What happens when multiple threads call get() and put() simultaneously?

38. Advanced Extension — LFU Cache

After LRU Cache, the next important cache design problem is:

LFU Cache

LFU stands for:

Least Frequently Used

LRU considers:

Recency

LFU considers:

Frequency

Example:

A → used 10 times
B → used 3 times
C → used 1 time

If the cache needs to evict an item, LFU prefers:

C

because it has the lowest usage frequency.

A typical efficient LFU design combines:

HashMap
+
Frequency Map
+
Doubly Linked Lists

This is more complex than LRU because we need to maintain both:

frequency

and:

recency within the same frequency

39. Advanced Extension — Skip List

Another advanced linked data structure is the:

Skip List

A normal linked list:

1 → 3 → 5 → 7 → 9

requires traversal to search for an element.

A Skip List adds multiple levels:

Level 2:       1 ─────────── 7
               ↓             ↓
Level 1:       1 ─── 5 ───── 7 ─── 9
               ↓     ↓       ↓     ↓
Level 0:       1 → 3 → 5 → 7 → 9

The higher levels allow us to skip over many nodes.

Average complexity:

Search  → O(log n)
Insert  → O(log n)
Delete  → O(log n)

Skip Lists are an important example of how Linked Lists can be extended to support faster searching.

40. LRU vs LFU

| Feature           | LRU                           | LFU                          |
| ----------------- | ----------------------------- | ---------------------------- |
| Full Form         | Least Recently Used           | Least Frequently Used        |
| Eviction Based On | Recency                       | Frequency                    |
| Main Concern      | What was used least recently? | What was used least often?   |
| Typical Structure | HashMap + DLL                 | HashMaps + DLLs              |
| Complexity        | O(1)                          | O(1) with appropriate design |
| Difficulty        | Medium                        | Hard                         |

41. Final Takeaways

The most important concepts from this part are:

Copy Random Pointer

HashMap

provides a direct mapping:

Original → Copy

The advanced solution uses:

Interleaving

to achieve:

O(n) time
O(1) extra space

LRU Cache

The core design is:

HashMap + Doubly Linked List

HashMap provides:

O(1) lookup

Doubly Linked List provides:

O(1) insertion
O(1) deletion
O(1) movement

Together:

get() → O(1)
put() → O(1)

42. One Diagram to Remember

If you remember only one LRU diagram, remember this:

                  HashMap
                    │
                    ▼
              key → Node
                    │
                    ▼
HEAD ⇄ MRU ⇄ Node ⇄ Node ⇄ LRU ⇄ TAIL
 ↑                                      ↑
Most Recently Used              Least Recently Used

When a node is accessed:

Node → move to HEAD

When a new node is inserted:

Node → insert after HEAD

When capacity is exceeded:

TAIL.prev → remove

That is the entire core idea behind an O(1) LRU Cache.

Practice Problems

Try solving these without looking at the solution:

Easy

1. Implement a Doubly Linked List.
2. Reverse a Doubly Linked List.
3. Delete a node from a Doubly Linked List.
4. Copy a linked list without random pointers.

Medium

1. Copy List with Random Pointer.
2. Implement LRU Cache.
3. Implement LRU Cache using LinkedHashMap.
4. Design a browser history using a Doubly Linked List.

Hard

1. Implement LFU Cache.
2. Implement a Skip List.
3. Design a thread-safe LRU Cache.
4. Design a cache supporting expiration and LRU eviction.