Doubly Linked List — The Prev Pointer Bug That Leaks Memory

package io.thecodeforge.collections;

/**
 * Node for a doubly linked list.
 * Each node holds a value, a reference to the next node,
 * and a reference to the previous node.
 *
 * The prev pointer is what distinguishes a DLL from a singly linked list.
 * It enables O(1) deletion of any known node and bidirectional traversal.
 */
public class DoublyLinkedListNode<T> {

    T value;
    DoublyLinkedListNode<T> next;
    DoublyLinkedListNode<T> prev;

    public DoublyLinkedListNode(T value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }

    @Override
    public String toString() {
        String prevVal = (prev != null) ? String.valueOf(prev.value) : "HEAD";
        String nextVal = (next != null) ? String.valueOf(next.value) : "TAIL";
        return "Node{value=" + value + ", prev=" + prevVal + ", next=" + nextVal + "}";
    }
}

package io.thecodeforge.collections;

/**
 * Doubly linked list implementation with invariant checks.
 * Tracks both head and tail for O(1) operations at both ends.
 *
 * Invariants maintained after every operation:
 * - head.prev == null
 * - tail.next == null
 * - Forward traversal count == size
 * - Backward traversal count == size
 */
public class DoublyLinkedList<T> {

    private DoublyLinkedListNode<T> head;
    private DoublyLinkedListNode<T> tail;
    private int size;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * Insert at head. O(1).
     * Critical: newNode.prev must be null for the new head.
     * Forgetting this breaks backward traversal from tail.
     */
    public void insertAtHead(T value) {
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(value);

        newNode.next = head;
        newNode.prev = null;  // CRITICAL: new head has no predecessor

        if (head != null) {
            head.prev = newNode;  // old head's prev now points to new node
        }

        head = newNode;

        if (tail == null) {
            tail = newNode;  // list was empty, new node is both head and tail
        }

        size++;
        assertInvariants();
    }

    /**
     * Insert at tail. O(1).
     * Critical: newNode.next must be null for the new tail.
     */
    public void insertAtTail(T value) {
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(value);

        newNode.prev = tail;
        newNode.next = null;  // CRITICAL: new tail has no successor

        if (tail != null) {
            tail.next = newNode;  // old tail's next now points to new node
        }

        tail = newNode;

        if (head == null) {
            head = newNode;  // list was empty
        }

        size++;
        assertInvariants();
    }

    /**
     * Delete a known node. O(1).
     * Must update up to four pointers.
     * Missing any one creates a dangling reference.
     */
    public void delete(DoublyLinkedListNode<T> node) {
        if (node == null) {
            throw new IllegalArgumentException("Cannot delete null node");
        }

        // Pointer 1: bypass from left
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;  // deleting head
        }

        // Pointer 2: bypass from right
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;  // deleting tail
        }

        // Sever dangling references to allow GC
        node.prev = null;
        node.next = null;

        size--;
        assertInvariants();
    }

    /**
     * Move an existing node to head. O(1).
     * Used by LRU cache on access.
     */
    public void moveToHead(DoublyLinkedListNode<T> node) {
        if (node == head) {
            return;  // already at head
        }

        // Unlink from current position
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;  // node was tail
        }

        // Link at head
        node.next = head;
        node.prev = null;
        if (head != null) {
            head.prev = node;
        }
        head = node;

        assertInvariants();
    }

    /**
     * Remove and return the tail node's value. O(1).
     * Used by LRU cache for eviction.
     */
    public T removeTail() {
        if (tail == null) {
            return null;
        }

        T value = tail.value;
        DoublyLinkedListNode<T> oldTail = tail;

        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null;  // list is now empty
        }

        oldTail.prev = null;
        oldTail.next = null;

        size--;
        assertInvariants();
        return value;
    }

    /**
     * Post-operation invariant checks.
     * Catches pointer bugs immediately instead of at next traversal.
     */
    private void assertInvariants() {
        if (head == null && tail == null && size == 0) {
            return;  // empty list is valid
        }

        if (head == null || tail == null) {
            throw new IllegalStateException(
                "Invariant violation: head and tail must both be null or both non-null. " +
                "head=" + head + " tail=" + tail + " size=" + size
            );
        }

        if (head.prev != null) {
            throw new IllegalStateException(
                "Invariant violation: head.prev must be null. Found: " + head.prev.value
            );
        }

        if (tail.next != null) {
            throw new IllegalStateException(
                "Invariant violation: tail.next must be null. Found: " + tail.next.value
            );
        }

        // Verify forward chain length matches size
        int forwardCount = 0;
        DoublyLinkedListNode<T> curr = head;
        while (curr != null) {
            forwardCount++;
            if (curr.prev != null && curr.prev.next != curr) {
                throw new IllegalStateException(
                    "Invariant violation: prev.next broken at node " + curr.value
                );
            }
            curr = curr.next;
        }

        if (forwardCount != size) {
            throw new IllegalStateException(
                "Invariant violation: forward chain length " + forwardCount +
                " != size " + size
            );
        }
    }

    public DoublyLinkedListNode<T> getHead() { return head; }
    public DoublyLinkedListNode<T> getTail() { return tail; }
    public int getSize() { return size; }
    public boolean isEmpty() { return size == 0; }
}

package io.thecodeforge.cache;

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

/**
 * LRU Cache backed by a hash map + doubly linked list.
 * O(1) get and put. O(1) eviction.
 *
 * The DLL maintains access order: most recently used at head,
 * least recently used at tail. The hash map provides O(1) key-to-node
 * lookup so we can move a node to head without traversing the DLL.
 */
public class LRUCache<K, V> {

    private final int capacity;
    private final Map<K, Node<K, V>> cache;
    private Node<K, V> head;
    private Node<K, V> tail;

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
    }

    /**
     * Get value by key. O(1).
     * Moves accessed node to head (most recently used).
     */
    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null;
        }
        moveToHead(node);
        return node.value;
    }

    /**
     * Put key-value pair. O(1).
     * If key exists: update and move to head.
     * If new: insert at head. If over capacity: evict tail.
     */
    public void put(K key, V value) {
        Node<K, V> node = cache.get(key);

        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            Node<K, V> newNode = new Node<>(key, value);
            cache.put(key, newNode);
            addToHead(newNode);

            if (cache.size() > capacity) {
                Node<K, V> evicted = removeTail();
                cache.remove(evicted.key);
            }
        }
    }

    /**
     * Move node to head. O(1).
     * Step 1: unlink from current position.
     * Step 2: link at head.
     */
    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * Add node right after head sentinel (or as head if no sentinel).
     * CRITICAL: newNode.prev must be set to null (or head sentinel).
     */
    private void addToHead(Node<K, V> node) {
        node.prev = null;   // CRITICAL: see incident #7293
        node.next = head;

        if (head != null) {
            head.prev = node;
        }
        head = node;

        if (tail == null) {
            tail = node;
        }
    }

    /**
     * Remove node from its current position. O(1).
     * Updates all four pointers.
     */
    private void removeNode(Node<K, V> node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;  // node was head
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;  // node was tail
        }

        node.prev = null;
        node.next = null;
    }

    /**
     * Remove and return tail node. O(1).
     */
    private Node<K, V> removeTail() {
        if (tail == null) {
            return null;
        }
        Node<K, V> oldTail = tail;
        removeNode(tail);
        return oldTail;
    }

    public int size() {
        return cache.size();
    }
}

package io.thecodeforge.collections;

import java.util.concurrent.locks.ReentrantLock;

/**
 * Thread-safe doubly linked list using coarse-grained locking.
 * All operations acquire a single lock.
 * Simple, correct, but serializes all access.
 *
 * For high-concurrency scenarios, consider fine-grained locking
 * or Java's ConcurrentLinkedDeque.
 */
public class ConcurrentDoublyLinkedList<T> {

    private DoublyLinkedListNode<T> head;
    private DoublyLinkedListNode<T> tail;
    private int size;
    private final ReentrantLock lock = new ReentrantLock();

    public void insertAtHead(T value) {
        lock.lock();
        try {
            DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(value);
            newNode.next = head;
            newNode.prev = null;

            if (head != null) {
                head.prev = newNode;
            }
            head = newNode;

            if (tail == null) {
                tail = newNode;
            }
            size++;
        } finally {
            lock.unlock();
        }
    }

    public void insertAtTail(T value) {
        lock.lock();
        try {
            DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(value);
            newNode.prev = tail;
            newNode.next = null;

            if (tail != null) {
                tail.next = newNode;
            }
            tail = newNode;

            if (head == null) {
                head = newNode;
            }
            size++;
        } finally {
            lock.unlock();
        }
    }

    public void delete(DoublyLinkedListNode<T> node) {
        lock.lock();
        try {
            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;
            }

            node.prev = null;
            node.next = null;
            size--;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Traverse the list with a lock held.
     * For read-heavy workloads, consider a ReadWriteLock.
     */
    public void traverse(java.util.function.Consumer<T> action) {
        lock.lock();
        try {
            DoublyLinkedListNode<T> curr = head;
            while (curr != null) {
                action.accept(curr.value);
                curr = curr.next;
            }
        } finally {
            lock.unlock();
        }
    }

    public int getSize() {
        lock.lock();
        try {
            return size;
        } finally {
            lock.unlock();
        }
    }
}

package io.thecodeforge.collections;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

/**
 * Boundary condition tests for doubly linked list.
 * Each test verifies invariants after every operation.
 */
public class DoublyLinkedListTest {

    @Test
    public void testInsertIntoEmptyList() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("first");

        assertNotNull(list.getHead());
        assertNotNull(list.getTail());
        assertSame(list.getHead(), list.getTail());
        assertEquals(1, list.getSize());
        assertNull(list.getHead().prev);
        assertNull(list.getTail().next);
    }

    @Test
    public void testDeleteOnlyElement() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("only");
        DoublyLinkedListNode<String> node = list.getHead();

        list.delete(node);

        assertNull(list.getHead());
        assertNull(list.getTail());
        assertEquals(0, list.getSize());
        assertNull(node.prev);
        assertNull(node.next);
    }

    @Test
    public void testInsertAtHeadBoundary() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("second");
        list.insertAtHead("first");

        assertEquals("first", list.getHead().value);
        assertNull(list.getHead().prev);
        assertEquals("second", list.getHead().next.value);
    }

    @Test
    public void testDeleteHead() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("third");
        list.insertAtHead("second");
        list.insertAtHead("first");

        list.delete(list.getHead());

        assertEquals("second", list.getHead().value);
        assertNull(list.getHead().prev);
        assertEquals(2, list.getSize());
    }

    @Test
    public void testDeleteTail() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("third");
        list.insertAtHead("second");
        list.insertAtHead("first");

        list.delete(list.getTail());

        assertEquals("second", list.getTail().value);
        assertNull(list.getTail().next);
        assertEquals(2, list.getSize());
    }

    @Test
    public void testMoveToHeadWhenAlreadyHead() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("first");
        list.insertAtHead("second");
        DoublyLinkedListNode<String> head = list.getHead();

        list.moveToHead(head);

        assertSame(head, list.getHead());
        assertEquals(2, list.getSize());
    }

    @Test
    public void testMoveTailToHead() {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.insertAtHead("first");
        list.insertAtHead("second");
        list.insertAtHead("third");
        DoublyLinkedListNode<String> tail = list.getTail();

        list.moveToHead(tail);

        assertSame(tail, list.getHead());
        assertEquals(3, list.getSize());
        assertNull(tail.prev);
        assertEquals("third", tail.next.value);
        assertNotSame(tail, list.getTail());
    }

    @Test
    public void testForwardAndBackwardTraversalMatch() {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        for (int i = 1; i <= 10; i++) {
            list.insertAtTail(i);
        }

        // Forward traversal
        int forwardCount = 0;
        DoublyLinkedListNode<Integer> curr = list.getHead();
        while (curr != null) {
            forwardCount++;
            curr = curr.next;
        }

        // Backward traversal
        int backwardCount = 0;
        curr = list.getTail();
        while (curr != null) {
            backwardCount++;
            curr = curr.prev;
        }

        assertEquals(forwardCount, backwardCount);
        assertEquals(list.getSize(), forwardCount);
    }

    @Test
    public void testInterleavedInsertDelete() {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

        list.insertAtHead(1);
        list.insertAtTail(2);
        list.insertAtHead(0);
        list.insertAtTail(3);

        assertEquals(4, list.getSize());

        list.delete(list.getHead());
        list.delete(list.getTail());

        assertEquals(2, list.getSize());
        assertEquals(Integer.valueOf(1), list.getHead().value);
        assertEquals(Integer.valueOf(2), list.getTail().value);
        assertNull(list.getHead().prev);
        assertNull(list.getTail().next);
    }
}

package io.thecodeforge.collections;

/**
 * Illustration of memory overhead in DLL vs ArrayList.
 * Run with -javaagent:path/to/jol-cli.jar to measure actual size.
 */
public class MemoryFootprintDemo {

    // Each DLL node: value ref (8) + next (8) + prev (8) + header (12-16) ≈ 36-40 bytes
    // plus alignment padding.

    // ArrayList: one reference per element (8) + array overhead (24 + 4 * N) ≈ 12 + 8 per element

    public static void main(String[] args) {
        System.out.println("DLL node overhead: ~40 bytes per node");
        System.out.println("ArrayList element overhead: ~8 bytes per reference");
        System.out.println("For 1M nodes: DLL ~40MB, ArrayList ~8MB");
    }
}