Doubly Linked List

A bidirectional linked structure enabling O(1) insertions and deletions at both ends, with efficient middle operations when node references are known.

Context

A Doubly Linked List is a dynamically resizable linear collection where each node maintains references to both its previous and next neighbour.

This bidirectional linkage enables efficient insertions and removals at both the head and tail in O(1) time.

However, random index access remains inefficient because traversal is required. Access by index is O(n) in the worst case.

Insertion or removal in the middle is:

• O(1) if you already hold a reference to the target node
• O(n) if you must first locate it by index or value

This distinction is critical: linked lists optimise structural modification, not random access.

See also Singly Linked List.

Core idea

• Store elements inside Node<T> objects.
• Each node contains:
  • value
  • next
  • prev
• Maintain:
  • head
  • tail
  • size

Track structural modifications using modCount to support fail-fast iteration.

The invariant:

Every node’s next.prev must point back to the node, and every node’s prev.next must point forward to the node.

If that invariant breaks, the structure is corrupted.

Implementation

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

public class DoublyLinkedList<T> implements Iterable<T> {
    private int size;
    private Node<T> head;
    private Node<T> tail;
    private int modCount;

    public int size() { return size; }

    public void prepend(T value) {
        if (size == 0) {
            head = tail = new Node<>(value, null, null);
        } else {
            var temp = head;
            head = new Node<>(value, null, temp);
            temp.prev = head;
        }
        size++;
        modCount++;
    }

    public void append(T value) {
        if (size == 0) {
            head = tail = new Node<>(value, null, null);
        } else {
            var temp = tail;
            tail = new Node<>(value, temp, null);
            temp.next = tail;
        }
        size++;
        modCount++;
    }

    public T get(int index) {
        assertIndexForAccess(index);
        return getNodeAt(index).value;
    }

    public void insertAt(int index, T value) {
        assertIndexForInsert(index);

        if (index == 0) {
            prepend(value);
        } else if (index == size) {
            append(value);
        } else {
            var previousNode = getNodeAt(index - 1);
            var next = previousNode.next;
            var newNode = new Node<T>(value, previousNode, next);
            previousNode.next = newNode;
            if (next != null) next.prev = newNode;
            size++;
            modCount++;
        }
    }

    public T remove(T value) {
        if (isEmpty()) return null;
        if (head.value.equals(value)) return removeHead();
        
        var node = head.next;
        
        while (node != null) {
            if (Objects.equals(node.value, value)) break;
            node = node.next;
        }
        
        if (node == null) return null;

        if (node == tail) return removeTail(); 

        node.prev.next = node.next;
        if (node.next != null) 
            node.next.prev = node.prev;
        
        modCount++;
        size--;
        
        return node.value;
    }

    public T removeAt(int index) {
        assertIndexForAccess(index);
        
        if (index == 0) return removeHead();
        if (index == size - 1) return removeTail();
        
        var node = getNodeAt(index);
        node.prev.next = node.next;
        
        if (node.next != null) 
            node.next.prev = node.prev;
        
        modCount++;
        size--;
        
        return node.value;
    }
    
    public boolean isEmpty() { return size == 0; }
    
    @Override
    public Iterator<T> iterator() { return new DoublyLinkedListIterator(); }
    
    private T removeHead() {
        var temp = head;
        
        if (head.next == null) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        
        size--;
        modCount++;

        return temp.value;
    }
    
    private T removeTail() {
        var temp = tail;
        if (temp.prev == null) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        
        modCount++;
        size--;
        
        return temp.value;
    }
    
    private Node<T> getNodeAt(int index) {
        if (index == 0) return head;
        if (index == size - 1) return tail;
        
        if (index > size / 2) {
            var node = tail;
            for (var i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        } else {
            var node = head;
            for (var i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }
    }
    
    private void assertIndexForAccess(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
    }

    private void assertIndexForInsert(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
    }
    
    private final class DoublyLinkedListIterator implements Iterator<T> {
        private final int expectedModCount = modCount;
        private Node<T> current = head;
        
        @Override
        public boolean hasNext() {
            if (expectedModCount != modCount) 
                throw new ConcurrentModificationException();
            return current != null;
        }
        
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            var value = current.value;
            current = current.next;
            return value;
        }
    }

    private static class Node<T> {
        private final T value;
        private Node<T> next;
        private Node<T> prev;

        private Node(T value, Node<T> previous, Node<T> next) {
            this.value = value;
            this.prev = previous;
            this.next = next;
        }
    }
}