Doubly Linked List prev, next, LRU Cache: Tutorial, Examples, FAQs & Interview Tips

Doubly Linked List prev, next, LRU Cache

Doubly is a practical Data Structure topic that becomes clear when you connect the definition to a small working example.

Use this page to understand what happens, why it happens, how to verify it, and what mistake usually breaks the concept.

After reading, practice Doubly with a normal case, a boundary case, and a broken case so the idea becomes usable instead of memorized.

Doubly Linked List prev next LRU Cache should be studied as a practical Data Structure lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.

In the data-structure > doubly-linked-list page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.

What is a Doubly Linked List?

A doubly linked list (DLL) is a linked list where each node has two pointers: one pointing to the next node and one pointing to the previous node. This allows traversal in both directions and makes deletion O(1) when you have a reference to the node.

Singly vs Doubly vs Circular Linked List

Feature	Singly	Doubly	Circular
Pointers per node	1 (next)	2 (prev + next)	1 or 2 (last -> first)
Traversal direction	Forward only	Forward & backward	Forward (loops)
Delete given node	O(n) - need prev	O(1) - has prev pointer	O(1) with prev
Memory per node	Less	More (extra pointer)	Same as singly/doubly
Use cases	Simple lists, stacks	LRU cache, browser history	Round-robin scheduling

Doubly Linked List - Insert, Delete, Traverse

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
    Node* head;
    Node* tail;
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertFront(int data) {
        Node* node = new Node(data);
        if (!head) { head = tail = node; return; }
        node->next = head;
        head->prev = node;
        head = node;
    }

    void insertEnd(int data) {
        Node* node = new Node(data);
        if (!tail) { head = tail = node; return; }
        tail->next = node;
        node->prev = tail;
        tail = node;
    }

    // O(1) delete when you have the node pointer
    void deleteNode(Node* node) {
        if (!node) return;
        if (node->prev) node->prev->next = node->next;
        else head = node->next;
        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;
        delete node;
    }

    void printForward() {
        Node* curr = head;
        while (curr) { cout << curr->data << " <-> "; curr = curr->next; }
        cout << "NULL" << endl;
    }

    void printBackward() {
        Node* curr = tail;
        while (curr) { cout << curr->data << " <-> "; curr = curr->prev; }
        cout << "NULL" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(1); dll.insertEnd(2); dll.insertEnd(3);
    dll.insertFront(0);
    dll.printForward();   // 0 <-> 1 <-> 2 <-> 3 <-> NULL
    dll.printBackward();  // 3 <-> 2 <-> 1 <-> 0 <-> NULL
    return 0;
}

Singly vs Doubly vs Circular Linked List

public class DoublyLinkedList {
    static class Node {
        int data;
        Node prev, next;
        Node(int d) { data = d; }
    }

    Node head, tail;

    void insertFront(int data) {
        Node node = new Node(data);
        if (head == null) { head = tail = node; return; }
        node.next = head;
        head.prev = node;
        head = node;
    }

    void insertEnd(int data) {
        Node node = new Node(data);
        if (tail == null) { head = tail = node; return; }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

    void deleteNode(Node node) {
        if (node == null) return;
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next;
        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev;
    }

    void printForward() {
        Node curr = head;
        while (curr != null) { System.out.print(curr.data + " <-> "); curr = curr.next; }
        System.out.println("NULL");
    }

    void printBackward() {
        Node curr = tail;
        while (curr != null) { System.out.print(curr.data + " <-> "); curr = curr.prev; }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertEnd(1); dll.insertEnd(2); dll.insertEnd(3);
        dll.insertFront(0);
        dll.printForward();   // 0 <-> 1 <-> 2 <-> 3 <-> NULL
        dll.printBackward();  // 3 <-> 2 <-> 1 <-> 0 <-> NULL
    }
}

Singly vs Doubly vs Circular Linked List

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_front(self, data):
        node = Node(data)
        if not self.head:
            self.head = self.tail = node
            return
        node.next = self.head
        self.head.prev = node
        self.head = node

    def insert_end(self, data):
        node = Node(data)
        if not self.tail:
            self.head = self.tail = node
            return
        self.tail.next = node
        node.prev = self.tail
        self.tail = node

    def delete_node(self, node):
        if node.prev: node.prev.next = node.next
        else: self.head = node.next
        if node.next: node.next.prev = node.prev
        else: self.tail = node.prev

    def print_forward(self):
        curr, parts = self.head, []
        while curr:
            parts.append(str(curr.data))
            curr = curr.next
        print(" <-> ".join(parts) + " <-> NULL")

    def print_backward(self):
        curr, parts = self.tail, []
        while curr:
            parts.append(str(curr.data))
            curr = curr.prev
        print(" <-> ".join(parts) + " <-> NULL")

dll = DoublyLinkedList()
dll.insert_end(1); dll.insert_end(2); dll.insert_end(3)
dll.insert_front(0)
dll.print_forward()   # 0 <-> 1 <-> 2 <-> 3 <-> NULL
dll.print_backward()  # 3 <-> 2 <-> 1 <-> 0 <-> NULL

Singly vs Doubly vs Circular Linked List

class Node {
    constructor(data) { this.data = data; this.prev = null; this.next = null; }
}

class DoublyLinkedList {
    constructor() { this.head = null; this.tail = null; }

    insertFront(data) {
        const node = new Node(data);
        if (!this.head) { this.head = this.tail = node; return; }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

    insertEnd(data) {
        const node = new Node(data);
        if (!this.tail) { this.head = this.tail = node; return; }
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }

    deleteNode(node) {
        if (node.prev) node.prev.next = node.next; else this.head = node.next;
        if (node.next) node.next.prev = node.prev; else this.tail = node.prev;
    }

    printForward() {
        const parts = [];
        let curr = this.head;
        while (curr) { parts.push(curr.data); curr = curr.next; }
        console.log(parts.join(" <-> ") + " <-> NULL");
    }

    printBackward() {
        const parts = [];
        let curr = this.tail;
        while (curr) { parts.push(curr.data); curr = curr.prev; }
        console.log(parts.join(" <-> ") + " <-> NULL");
    }
}

const dll = new DoublyLinkedList();
dll.insertEnd(1); dll.insertEnd(2); dll.insertEnd(3);
dll.insertFront(0);
dll.printForward();   // 0 <-> 1 <-> 2 <-> 3 <-> NULL
dll.printBackward();  // 3 <-> 2 <-> 1 <-> 0 <-> NULL

LRU Cache using DLL + HashMap

An LRU (Least Recently Used) Cache evicts the least recently used item when capacity is full. The optimal implementation uses a doubly linked list (for O(1) insert/delete) combined with a HashMap (for O(1) lookup). All operations are O(1).

LRU Cache - O(1) get and put

#include <iostream>
#include <unordered_map>
using namespace std;

struct Node {
    int key, val;
    Node *prev, *next;
    Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
    int cap;
    unordered_map<int, Node*> map;
    Node *head, *tail;  // dummy head and tail

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void insertFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        if (!map.count(key)) return -1;
        Node* node = map[key];
        remove(node);
        insertFront(node);
        return node->val;
    }
    void put(int key, int value) {
        if (map.count(key)) { remove(map[key]); delete map[key]; map.erase(key); }
        if (map.size() == cap) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* node = new Node(key, value);
        insertFront(node);
        map[key] = node;
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;  // 1 (key 1 now most recent)
    cache.put(3, 3);                // evicts key 2
    cout << cache.get(2) << endl;  // -1 (evicted)
    cout << cache.get(3) << endl;  // 3
    return 0;
}

LRU Cache using DLL + HashMap

import java.util.HashMap;

public class LRUCache {
    private final int cap;
    private final HashMap<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

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

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

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node); insertFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) { remove(map.get(key)); map.remove(key); }
        if (map.size() == cap) {
            Node lru = tail.prev;
            remove(lru); map.remove(lru.key);
        }
        Node node = new Node(key, value);
        insertFront(node); map.put(key, node);
    }

    public static void main(String[] args) {
        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
        System.out.println(cache.get(3));  // 3
    }
}

LRU Cache using DLL + HashMap

from collections import OrderedDict

# Python's OrderedDict makes LRU Cache very clean
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()  # maintains insertion order

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)  # mark as most recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # remove least recently used (front)

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1 (key 1 now most recent)
cache.put(3, 3)       # evicts key 2
print(cache.get(2))   # -1 (evicted)
print(cache.get(3))   # 3

LRU Cache using DLL + HashMap

class LRUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.map = new Map();  // Map preserves insertion order in JS
    }

    get(key) {
        if (!this.map.has(key)) return -1;
        const val = this.map.get(key);
        this.map.delete(key);
        this.map.set(key, val);  // move to end (most recent)
        return val;
    }

    put(key, value) {
        if (this.map.has(key)) this.map.delete(key);
        this.map.set(key, value);
        if (this.map.size > this.cap) {
            // Delete the first (least recently used) entry
            this.map.delete(this.map.keys().next().value);
        }
    }
}

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));  // 1 (key 1 now most recent)
cache.put(3, 3);            // evicts key 2
console.log(cache.get(2));  // -1 (evicted)
console.log(cache.get(3));  // 3

Deep Study Notes for Doubly

Doubly should be learned as a practical Data Structure skill, not only as a definition. Start by asking what problem the topic solves, what input or state it receives, what rule it applies, and what visible result proves it worked.

A strong explanation of Doubly includes the normal case, a boundary case, and a failure case. When you practice, write down the before-state, the operation, the after-state, and the reason the result changed.

This lesson was expanded because the audit reported: limited checklist/practice/mistake/FAQ notes . The added notes below focus on clearer explanation, more examples, and concrete practice so the topic is easier to understand from the page itself.

Define the exact problem solved by Doubly before looking at syntax.
Trace one small example by hand and describe every step in plain language.
Identify what changes when the input is empty, repeated, invalid, delayed, or larger than expected.
Connect the topic to a realistic project scenario instead of treating it as isolated theory.
Verify your answer with output, logs, query results, browser behavior, compiler feedback, or a state table.

Worked Explanation: Using Doubly Correctly

Imagine you are adding Doubly to a small learning project. The first step is to choose the smallest scenario that still shows the main idea. Avoid starting with a large production design; it hides the concept behind too many details.

Next, isolate the moving parts. Name the input, the rule, the output, and the possible error. This habit makes the topic easier to debug because you can see whether the problem is caused by bad data, wrong configuration, incorrect syntax, timing, permissions, or misunderstanding of the rule.

Finally, compare two versions: one correct version and one intentionally broken version. The broken version is valuable because it teaches you how the topic fails in real work, which is usually what interviews and debugging tasks test.

Normal case: show the expected behavior with simple, valid input.
Boundary case: test the smallest, largest, empty, repeated, or unusual value that still belongs to the topic.
Failure case: introduce one realistic mistake and explain the symptom it creates.
Repair step: change one thing at a time so you know exactly what fixed the problem.

Doubly trace helper

def trace_doubly(items):
    print('Input:', items)
    for index, value in enumerate(items):
        print(f'step={index}, value={value}, remaining={items[index+1:]}')
    return len(items)

print('operations:', trace_doubly([4, 1, 7, 1]))

Doubly edge-case practice

test_cases = [[], [5], [3, 3, 3], [9, -1, 0, 9]]
for case in test_cases:
    print('case:', case, 'size:', len(case))

# Explain the behavior for empty, single, repeated, and mixed data before optimizing.

Key Takeaways

State the purpose of Doubly in one sentence before using it.
Create a tiny Data Structure example that demonstrates the topic without unrelated code.
Test one normal input, one edge input, and one incorrect input for Doubly.
Explain the result using before-state, operation, and after-state.
Add a verification step such as output, logs, query results, browser behavior, or compiler feedback.

Common Mistakes to Avoid

WRONG Memorizing Doubly as a definition only.

RIGHT Pair the definition with a small working example and a failure example.

The fastest way to remember the topic is to explain why the output changes.

WRONG Copying syntax without checking the state before and after.

RIGHT Write the input state, apply the rule, then inspect the output state.

State tracing turns confusing behavior into a visible sequence.

WRONG Ignoring the error path for Doubly.

RIGHT Create one intentionally broken version and document the symptom and fix.

A page is much easier to learn from when it explains both success and failure.

WRONG Memorizing Doubly Linked List prev next LRU Cache without the situation where it is useful.

RIGHT Connect Doubly Linked List prev next LRU Cache to a concrete Data Structure task.

Purpose makes syntax easier to recall.

Practice Tasks

Build the smallest working demo for Doubly and write what each line does.
Change one input or setting and predict the result before running it.
Break the example in a realistic way, then fix it and describe the repair.
Create a two-column note comparing when to use Doubly and when another approach is better.
Explain Doubly aloud as if teaching a beginner who knows basic Data Structure only.

Frequently Asked Questions

What should I understand first in Doubly?

Understand the problem it solves, the input or state it works on, and the visible result that proves the concept is working.

How should I practice Doubly?

Use one tiny correct example, one boundary example, and one broken example. Compare the output or state after each change.

Why do beginners struggle with Doubly?

They often memorize the term without tracing the behavior. Tracing makes the rule easier to remember and debug.

What should I remember first about Doubly Linked List prev next LRU Cache?

Remember the problem it solves in Data Structure, then attach the syntax or steps to that problem.

Previous Next

Doubly Linked List prev, next, LRU Cache: Tutorial, Examples, FAQs & Interview Tips