Doubly Linked List prev, next, LRU Cache

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 - Java Example

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 - Python Example

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 - JavaScript Example

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 - Java Example

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 - Python Example

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 - JavaScript Example

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

Verify Deletion from Both Directions

Deleting a node changes up to four relationships: the previous node next link, the next node previous link, the head, and the tail. Save neighboring pointers before releasing the node, update both directions, and handle the one-node list where head and tail become null together.

After each boundary operation, traverse from head to tail and then from tail to head. The sequences must contain the same nodes in reverse order. Also verify head.prev and tail.next are null; those assertions catch partial link repairs that a one-direction traversal can miss.

Delete the head, tail, only node, middle node, and a missing target.
Define whether the list or caller owns removed values and nodes.
Update size only after a deletion is confirmed.

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]))

Before you move on