Doubly Linked Lists

IB Syllabus: B4.1.2, B4.1.3 (HL) – Evaluate linked lists: singly, doubly, circular. Construct and apply linked lists.

This page is HL only.

Table of Contents

1. Key Concepts
   1. The Doubly Linked Node
   2. Head and Tail
   3. Singly vs Doubly Linked Lists
   4. Circular Linked Lists
2. Worked Examples
   1. Example 1: Building a Doubly Linked List
   2. Example 2: Deletion in a Doubly Linked List
   3. Example 3: Insert Before a Given Node
3. Quick Code Check
4. Trace Exercise
5. Code Completion
6. Spot the Bug
7. Output Prediction
8. Practice Exercises
   1. Core
   2. Extension
   3. Challenge
9. Connections

---

Key Concepts

A doubly linked list is a linked list where each node has two references: one pointing to the next node and one pointing to the previous node. This allows traversal in both directions – forward and backward.

The Doubly Linked Node

public class DNode {
    String data;
    DNode next;
    DNode prev;

    public DNode(String data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

Each node now stores three things: the data, a forward reference (next), and a backward reference (prev).

Head and Tail

A doubly linked list typically maintains both a head reference (first node) and a tail reference (last node):

• head.prev is always null (nothing before the first node)
• tail.next is always null (nothing after the last node)
• In an empty list, both head and tail are null

Singly vs Doubly Linked Lists

Feature	Singly Linked	Doubly Linked
References per node	1 (next)	2 (next + prev)
Memory per node	Less (one reference)	More (two references)
Traverse forward	Yes	Yes
Traverse backward	No	Yes
Delete a given node	Need predecessor – O(n) to find	Have predecessor via prev – O(1)
Insert before a given node	Need predecessor – O(n) to find	Have predecessor via prev – O(1)
Add to end	O(n) without tail reference	O(1) with tail reference
Complexity of implementation	Simpler	More pointer updates per operation

The main advantage: bidirectional traversal and O(1) deletion when you already have a reference to the node. The trade-off is more memory per node and more pointers to update during insertion and deletion.

Circular Linked Lists

A circular linked list is a variation where the tail’s next points back to the head (instead of null). In a circular doubly linked list, the head’s prev also points to the tail. Circular lists are useful for round-robin scheduling and playlist loops.

This page focuses on non-circular doubly linked lists. The circular variant uses the same node structure but changes how the end conditions work.

---

Worked Examples

Example 1: Building a Doubly Linked List

public class DoublyLinkedList {
    private DNode head;
    private DNode tail;

    public DoublyLinkedList() {
        head = null;
        tail = null;
    }

    // Add to the front
    public void addToFront(String data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // Add to the end
    public void addToEnd(String data) {
        DNode newNode = new DNode(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // Print forward: head to tail
    public void printForward() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Print backward: tail to head
    public void printBackward() {
        DNode current = tail;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }

    public int size() {
        int count = 0;
        DNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.addToEnd("Apple");
        list.addToEnd("Banana");
        list.addToEnd("Cherry");

        System.out.println("Forward:");
        list.printForward();

        System.out.println("Backward:");
        list.printBackward();

        System.out.println("Size: " + list.size());
    }
}

Output:

Forward:
Apple <-> Banana <-> Cherry <-> null
Backward:
Cherry <-> Banana <-> Apple <-> null
Size: 3

Notice that addToEnd is O(1) because we maintain a tail reference – no traversal needed.

Example 2: Deletion in a Doubly Linked List

The key advantage of a doubly linked list: when you have a reference to a node, you can remove it in O(1) by updating the neighbors’ pointers.

// Remove a specific node (given a reference to it)
private void removeNode(DNode node) {
    if (node == head && node == tail) {
        // Only node in the list
        head = null;
        tail = null;
    } else if (node == head) {
        head = head.next;
        head.prev = null;
    } else if (node == tail) {
        tail = tail.prev;
        tail.next = null;
    } else {
        // Middle node: bypass it
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

// Remove first occurrence by value
public boolean remove(String target) {
    DNode current = head;
    while (current != null) {
        if (current.data.equals(target)) {
            removeNode(current);
            return true;
        }
        current = current.next;
    }
    return false;
}

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    list.addToEnd("Red");
    list.addToEnd("Green");
    list.addToEnd("Blue");
    list.addToEnd("Yellow");

    System.out.println("Before:");
    list.printForward();

    list.remove("Green");  // middle
    System.out.println("After removing Green:");
    list.printForward();

    list.remove("Red");    // head
    System.out.println("After removing Red:");
    list.printForward();
    list.printBackward();
}

Output:

Before:
Red <-> Green <-> Blue <-> Yellow <-> null
After removing Green:
Red <-> Blue <-> Yellow <-> null
After removing Red:
Blue <-> Yellow <-> null
Yellow <-> Blue <-> null

How removeNode handles the four cases:

Case	Action
Only node	Set head and tail to null
Head node	Move head forward, clear new head’s prev
Tail node	Move tail backward, clear new tail’s next
Middle node	Link predecessor to successor and successor to predecessor

Four pointer updates for middle deletion. When removing a middle node, you must update both node.prev.next and node.next.prev. Missing either one creates a broken chain that only works in one direction.

Example 3: Insert Before a Given Node

// Insert a new node before a target value
public void insertBefore(String target, String data) {
    DNode current = head;
    while (current != null) {
        if (current.data.equals(target)) {
            if (current == head) {
                addToFront(data);
            } else {
                DNode newNode = new DNode(data);
                newNode.next = current;
                newNode.prev = current.prev;
                current.prev.next = newNode;
                current.prev = newNode;
            }
            return;
        }
        current = current.next;
    }
}

In a singly linked list, inserting before a given node requires finding the predecessor by traversing from the head – O(n). In a doubly linked list, the predecessor is available via current.prev – making the insertion itself O(1) once the target is found.

---

Quick Code Check

Q1. How many references does each node in a doubly linked list contain?

Q2. In a non-circular doubly linked list, what is the value of head.prev?

Q3. What is the time complexity of addToEnd in a doubly linked list that maintains a tail reference?

Q4. What is the main disadvantage of a doubly linked list compared to a singly linked list?

Q5. Why is deleting a node faster in a doubly linked list when you already have a reference to it?

---

Trace Exercise

Trace through the following code and fill in the state after each operation.

DoublyLinkedList list = new DoublyLinkedList();
list.addToEnd("X");
list.addToEnd("Y");
list.addToFront("W");
list.addToEnd("Z");
list.remove("Y");

After operation	head	tail	Forward list	size()
addToEnd("X")			X <-> null	1
addToEnd("Y")	X			2
addToFront("W")		Y
addToEnd("Z")	W		W <-> X <-> Y <-> Z <-> null	4
remove("Y")	W	Z

---

Code Completion

Complete the addToEnd method for a doubly linked list.

Fill in the blanks to link the new node at the end:

public void addToEnd(String data) {
    DNode newNode = new DNode(data);
    if (tail == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode. = tail;
        tail. = newNode;
         = newNode;
    }
}

---

Complete the middle-node removal (bypass the node in both directions).

Given a reference to a middle node, fill in the blanks to remove it:

// node is not head or tail
node.prev. = node.next;
node..prev = node.prev;

---

Spot the Bug

This addToFront method breaks the backward chain -- printBackward does not work correctly:

1public void addToFront(String data) { 2 DNode newNode = new DNode(data); 3 if (head != null) { 4 newNode.next = head; 5 head = newNode; 6 head.prev = newNode; 7 } else { 8 head = newNode; 9 tail = newNode; 10 } 11}

Pick the correct fix:

---

After removing the tail node, printBackward returns an incomplete list (missing nodes):

1// Removing the tail node: 2tail = tail.prev; 3tail.prev = null;

Pick the correct fix for line 3:

---

Output Prediction

What does this code print?

DoublyLinkedList d = new DoublyLinkedList();
d.addToFront("B");
d.addToFront("A");
d.addToEnd("C");
d.printForward();
d.printBackward();

Type the exact output:

---

What does this code print?

DoublyLinkedList d = new DoublyLinkedList();
d.addToEnd("P");
d.addToEnd("Q");
d.addToEnd("R");
d.addToEnd("S");
d.remove("Q");
d.remove("S");
System.out.println(d.size());
d.printForward();

Type the exact output:

---

Practice Exercises

Core

1. Build and traverse both ways – Create a doubly linked list with 5 elements. Print forward and backward. Verify the backward output is the reverse of the forward output.
2. Delete all cases – Create a 4-node list. Remove the head, a middle node, and the tail (in separate steps). Print the list after each removal and verify both forward and backward traversal work correctly.
3. Size tracking – Add a private int size field that is incremented on every insertion and decremented on every removal. Verify it matches the size() traversal method after every operation.

Extension

1. Insert at index – Write a method public void insertAt(int index, String data) that inserts a new node at a given position (0-based). Use the prev pointer to handle insertion efficiently once the position is found.
2. Palindrome check – Write a method public boolean isPalindrome() that checks whether the list reads the same forward and backward. Use two pointers starting at head and tail, moving toward the center.

Challenge

1. Circular doubly linked list – Modify the DoublyLinkedList class so that tail.next points to head and head.prev points to tail. Update addToFront, addToEnd, and printForward (use a counter or stop condition to avoid infinite loops). Test by adding 4 elements and printing from any starting node.
2. Compare all three variants – Write a program that creates a singly linked list, a doubly linked list, and a circular doubly linked list, each with 5 elements. For each, count the number of pointer updates required to: (a) add to front, (b) add to end, (c) remove the 3rd element. Present results in a table and explain which variant is best for each operation.

---

Connections

• Prerequisites: Linked Lists – singly linked list operations and Node class
• Related: Stacks from Scratch – stacks can be implemented using a doubly linked list
• Related: Queues from Scratch – doubly linked lists make deque (double-ended queue) implementations natural
• Next: Stacks from Scratch – implementing a stack using nodes