Doubly Linked List Structure and Node Design in DSA Java

Mental Model

A doubly linked list is a chain of nodes where each node knows both its neighbor before and after it.

Analogy: Imagine a train where each carriage has a connector to the carriage in front and the one behind, so you can move forward or backward easily.

null ← [Node1] ↔ [Node2] ↔ [Node3] -> null

Dry Run Walkthrough

Input: Create a doubly linked list with nodes holding values 1, 2, 3 linked in order

Goal: Build the doubly linked list so each node points to the previous and next nodes correctly

Step 1: Create first node with value 1; prev and next are null

null ← [1] -> null

Why: Start the list with a single node that points nowhere

Step 2: Create second node with value 2; link it after first node

null ← [1] ↔ [2] -> null

Why: Connect second node so first node's next points to it and second node's prev points back

Step 3: Create third node with value 3; link it after second node

null ← [1] ↔ [2] ↔ [3] -> null

Why: Extend the list by linking third node after second node with proper prev and next

Result:

null ← [1] ↔ [2] ↔ [3] -> null

Annotated Code

DSA Java

public class DoublyLinkedList {
    static class Node {
        int data;
        Node prev;
        Node next;

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

    Node head;

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode; // first node becomes head
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next; // move to last node
        }
        curr.next = newNode; // link last node to new node
        newNode.prev = curr; // link new node back to last node
    }

    public void printList() {
        Node curr = head;
        StringBuilder sb = new StringBuilder();
        while (curr != null) {
            sb.append(curr.data);
            if (curr.next != null) sb.append(" ↔ ");
            curr = curr.next;
        }
        System.out.println("null ← " + sb.toString() + " -> null");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.printList();
    }
}

if (head == null) { head = newNode; return; }

set first node as head if list is empty

while (curr.next != null) { curr = curr.next; }

move to last node to append new node

curr.next = newNode; newNode.prev = curr;

link new node after last node and back link

while (curr != null) { sb.append(curr.data); if (curr.next != null) sb.append(" ↔ "); curr = curr.next; }

traverse list forward to build string representation

Output

null ← 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(n) because appending requires traversing to the end of the list

Space: O(n) because each node stores data plus two pointers

vs Alternative: Compared to singly linked list, doubly linked list uses more space but allows backward traversal

Edge Cases

empty list

append sets the new node as head with null prev and next

DSA Java

if (head == null) { head = newNode; return; }

single node list

new node is linked after head with correct prev and next

DSA Java

while (curr.next != null) { curr = curr.next; }

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list structure because each node links both ways.

Common Mistakes

Mistake: Forgetting to set the new node's prev pointer when appending
Fix: Always assign newNode.prev = curr after linking curr.next = newNode

Mistake: Not handling empty list case when appending
Fix: Check if head is null and set head to new node before traversing

Summary

It creates a chain of nodes where each node links to the previous and next nodes.

Use it when you want to move both forward and backward through a list easily.

The key is each node keeps track of two neighbors, not just one.

Practice

1. What is the main difference between a doubly linked list node and a singly linked list node?

easy

A. A doubly linked list node does not store any data.

B. A doubly linked list node stores data in a different format.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node has pointers to both the previous and next nodes.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the previous node and one to the next node.

3. Final Answer:

   A doubly linked list node has pointers to both the previous and next nodes. -> Option D

4. Quick Check:

   Doubly linked list nodes have two pointers = D [OK]

Hint: Remember: doubly means two pointers [OK]

Common Mistakes:

• Thinking doubly linked list nodes only point forward
• Confusing data storage with pointer structure
• Assuming doubly linked list nodes have no data

2. Which of the following is the correct Java declaration for a doubly linked list node class with integer data?

easy

A. class Node { int data; Node next; }

B. class Node { int data; Node previous; }

C. class Node { int data; Node prev; Node next; }

D. class Node { int data; Node left; Node right; }

Solution

1. Step 1: Check for both previous and next pointers

   A doubly linked list node must have pointers named prev and next to link both directions.

2. Step 2: Verify data type and pointer names

   class Node { int data; Node prev; Node next; } declares int data and Node prev and Node next, which matches the doubly linked list node structure.

3. Final Answer:

   class Node { int data; Node prev; Node next; } -> Option C

4. Quick Check:

   Node with prev and next pointers = C [OK]

Hint: Look for both prev and next pointers in class [OK]

Common Mistakes:

• Missing prev pointer in node class
• Using incorrect pointer names like left/right
• Declaring only one pointer for next node

3. What will be the output of the following code snippet that creates a doubly linked list with nodes 10 and 20 and prints the data from head to tail?

class Node {
  int data;
  Node prev, next;
  Node(int d) { data = d; prev = next = null; }
}

public class TestDLL {
  public static void main(String[] args) {
    Node head = new Node(10);
    Node second = new Node(20);
    head.next = second;
    second.prev = head;
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
  }
}

medium

A. 10 20

B. 20 10

C. 10

D. Compilation error

Solution

1. Step 1: Understand node linking

   Node head points to 10, second node is 20. head.next = second and second.prev = head links them correctly.

2. Step 2: Trace the while loop printing

   Starting at head (10), print 10, move to next (20), print 20, then next is null, loop ends.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Print from head to tail = 10 20 [OK]

Hint: Follow next pointers from head to print data [OK]

Common Mistakes:

• Printing in reverse order by mistake
• Forgetting to link prev pointer
• Assuming output includes null or extra spaces

4. Identify the error in the following doubly linked list node insertion code and select the correct fix:

Node newNode = new Node(30);
newNode.next = head;
head.prev = newNode;
head = newNode;

medium

A. head.prev = newNode; causes NullPointerException if head is null; fix by checking if head != null before assignment.

B. No error; code correctly inserts newNode at head.

C. newNode.next should be null; fix by setting newNode.next = null.

D. head = newNode; should be before setting pointers.

Solution

1. Step 1: Analyze pointer assignments

   newNode.next = head sets newNode's next to current head. Then head.prev = newNode sets head's prev to newNode.

2. Step 2: Check for null head case

   If head is null (empty list), head.prev causes NullPointerException. Need to check if head != null before assigning head.prev.

3. Final Answer:

   head.prev = newNode; causes NullPointerException if head is null; fix by checking if head != null before assignment. -> Option A

4. Quick Check:

   Check for null before head.prev assignment = B [OK]

Hint: Always check if head is null before accessing head.prev [OK]

Common Mistakes:

• Ignoring null check on head before setting prev
• Setting newNode.next to null incorrectly
• Changing head before linking nodes

5. You want to insert a new node with data 40 between two existing nodes in a doubly linked list: nodeA and nodeB, where nodeA.next = nodeB and nodeB.prev = nodeA. Which sequence of pointer updates correctly inserts the new node between nodeA and nodeB?

hard

A. newNode.next = nodeA; newNode.prev = nodeB; nodeA.prev = newNode; nodeB.next = newNode;

B. newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode;

C. nodeA.next = newNode; nodeB.prev = newNode; newNode.prev = nodeB; newNode.next = nodeA;

D. newNode.prev = nodeB; newNode.next = nodeA; nodeA.next = nodeB; nodeB.prev = nodeA;

Solution

1. Step 1: Set newNode pointers to link between nodeA and nodeB

   newNode.prev must point to nodeA and newNode.next must point to nodeB to place it between them.

2. Step 2: Update nodeA and nodeB pointers to include newNode

   nodeA.next should point to newNode and nodeB.prev should point to newNode to complete the insertion.

3. Final Answer:

   newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode; -> Option B

4. Quick Check:

   Link newNode between nodeA and nodeB correctly = A [OK]

Hint: Set newNode pointers first, then update neighbors [OK]

Common Mistakes:

• Swapping prev and next pointers incorrectly
• Updating neighbors before setting newNode pointers
• Not updating both nodeA.next and nodeB.prev