Doubly Linked List

A linear collection where each node has references to both the next and previous nodes. Provides O(1) insertion/deletion at both ends.

How Doubly Linked List Works Internally

Node Structure

Each node contains three fields: data, next, and prev. The prev pointer allows backward traversal and enables O(1) deletion from the end.

class Node {
    E data;
    Node next;
    Node prev;
}

Head and Tail

Both head and tail references are maintained. head.prev is null, tail.next is null. This enables efficient operations at both ends of the list.

Bidirectional Traversal

You can traverse forward (using next) or backward (using prev). For get(index), you can optimize by starting from the closer end: if index < size/2, start from head; otherwise start from tail.

More Pointers to Update

Insert and delete operations require updating more pointers than singly-linked. For middle insertions, you update 4 pointers: new.next, new.prev, prev.next, and next.prev.

Time Complexity

Operation	Time	Why
get(index)	O(n/2) = O(n)	Traverse from closer end (head or tail)
set(index, value)	O(n/2) = O(n)	Traverse from closer end (head or tail)
addFirst(value)	O(1)	Update head pointer and new.next
addLast(value)	O(1)	Update tail pointer and new.prev
add(index, value)	O(n)	Traverse to index, then O(1) insert
removeFirst()	O(1)	Update head and new head's prev
removeLast()	O(1)	Update tail using tail.prev
remove(index)	O(n)	Traverse to index, then O(1) remove

Interactive Visualizer

Notice the bidirectional arrows between nodes. Watch how both next and prev pointers are updated during operations.

Size: 4

head↓

[0]10

⇄

[1]20

⇄

[2]30

⇄

[3]40

→ null

← tail

Node data Pointer

Operation

Index

Value

Speed:

Java Implementation

public void add(int index, E element) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException();
    Node newNode = new Node(element);
    if (size == 0) {
        head = tail = newNode;
    } else if (index == 0) {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    } else if (index == size) {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    } else {
        Node current = getNode(index);
        newNode.next = current;
        newNode.prev = current.prev;
        current.prev.next = newNode;
        current.prev = newNode;
    }
    size++;
}

Pseudocode

1. Check if index is valid (0 to size)

2. Create a new node with the element

3. If list is empty: set head and tail to new node

4. If adding at index 0:

- Point new node's next to head

- Point head's prev to new node

- Update head to new node

5. If adding at end:

- Point new node's prev to tail

- Point tail's next to new node

- Update tail to new node

6. If adding in middle:

- Traverse to node at index

- Update all four pointers

7. Increment size

Node Class Structure

private class Node {
    E data;
    Node next;
    Node prev;

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

Pointer Operations Explained