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

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;
}

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
    }
}

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

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;
}

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
    }
}

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

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

Previous Next

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

What is a Doubly Linked List?

Singly vs Doubly vs Circular Linked List

LRU Cache using DLL + HashMap

Level Up Your Data structure Skills

Popular Tutorials

Ready to Level Up Your Skills?