Create and Initialize Doubly Linked List in DSA Java

Mental Model

A doubly linked list is a chain of nodes where each node knows both its previous and next neighbor, making it easy to move forward and backward.

Analogy: Imagine a train where each carriage is connected to the one before and after it, so you can walk from the front to the back or back to front easily.

null ← [head] 1 ↔ 2 ↔ 3 [tail] → null

Dry Run Walkthrough

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

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

Step 1: Create first node with value 1; head and tail point to it

null ← [head/tail] 1 → null

Why: Start the list with a single node that is both head and tail

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

null ← 1 ↔ 2 [tail] → null

Why: Add second node and update tail; link previous and next pointers

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

null ← 1 ↔ 2 ↔ 3 [tail] → null

Why: Add third node at the end and update tail pointer

Result:

null ← 1 ↔ 2 ↔ 3 [tail] → 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;
    Node tail;

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

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        tail.next = newNode; // link current tail to new node
        newNode.prev = tail; // link new node back to current tail
        tail = newNode;      // update tail to new node
    }

    public void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) {
                System.out.print(" ↔ ");
            }
            curr = curr.next;
        }
        System.out.println();
    }

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

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

initialize head and tail when list is empty

tail.next = newNode;

link current tail's next to new node

newNode.prev = tail;

link new node's prev to current tail

tail = newNode;

update tail pointer to new node

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

traverse list from head to tail to print values

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(n) because we add each node once and print all nodes once

Space: O(n) because we store n nodes in the list

vs Alternative: Compared to singly linked list, doubly linked list uses extra space for prev pointers but allows backward traversal

Edge Cases

Empty list before any append

Head and tail are null; first append sets both to new node

DSA Java

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

Appending only one node

List has one node with prev and next as null

DSA Java

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

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list to keep track of both neighbors.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer when appending
Fix: Always set newNode.prev = tail before updating tail

Mistake: Not updating tail pointer after adding new node
Fix: Set tail = newNode to keep tail at the last node

Summary

Creates a doubly linked list where each node links to both previous and next nodes.

Use it when you want to traverse a list forwards and backwards efficiently.

Remember to update both next and prev pointers and maintain head and tail references.

Practice

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

easy

A. A doubly linked list does not allow traversal in reverse order.

B. A doubly linked list has nodes with pointers to both previous and next nodes.

C. A doubly linked list stores data in arrays instead of nodes.

D. A doubly linked list only has a pointer to the next node.

Solution

1. Step 1: Understand node pointers in linked lists

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

2. Step 2: Identify doubly linked list node pointers

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

3. Final Answer:

   A doubly linked list has nodes with pointers to both previous and next nodes. -> Option B

4. Quick Check:

   Doubly linked list = two pointers per node [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Confusing singly and doubly linked list pointers
• Thinking doubly linked lists use arrays
• Assuming doubly linked lists cannot go backward

2. Which of the following is the correct way to declare a node class for a doubly linked list in Java?

easy

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

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

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

D. class Node { int data; Node next; Node previous; }

Solution

1. Step 1: Check node fields for doubly linked list

   A doubly linked list node must have data, next pointer, and previous pointer.

2. Step 2: Match correct field names

   class Node { int data; Node next; Node prev; } uses 'next' and 'prev' which are standard and consistent.

3. Final Answer:

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

4. Quick Check:

   Node has data, next, and prev [OK]

Hint: Node needs both next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer in node class
• Using inconsistent pointer names
• Confusing singly linked list node with doubly linked

3. What will be the output of the following Java code that creates a doubly linked list with nodes 10, 20, 30 and prints it forward?

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

public class Main {
  public static void main(String[] args) {
    Node head = new Node(10);
    Node second = new Node(20);
    Node third = new Node(30);
    head.next = second; second.prev = head;
    second.next = third; third.prev = second;

    Node current = head;
    while(current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.print("null");
  }
}

medium

A. 30 -> 20 -> 10 -> null

B. null -> 10 -> 20 -> 30

C. 10 -> 20 -> 30 -> null

D. 10 -> 20 -> null

Solution

1. Step 1: Understand list creation and linking

   Nodes 10, 20, 30 are linked forward: 10.next=20, 20.next=30.

2. Step 2: Trace the print loop

   Starting at head (10), print data then move to next until null: prints 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option C

4. Quick Check:

   Forward traversal prints nodes in insertion order [OK]

Hint: Follow next pointers from head to null [OK]

Common Mistakes:

• Printing in reverse order by mistake
• Missing last node in output
• Confusing prev and next pointers

4. Identify the error in the following code snippet that tries to create a doubly linked list with nodes 1 and 2:

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

public class Main {
  public static void main(String[] args) {
    Node head = new Node(1);
    Node second = new Node(2);
    head.next = second;
    // Missing line here
    System.out.println(head.next.data);
  }
}

medium

A. Missing assignment of second.prev to head

B. Node constructor is missing initialization

C. head.next should be assigned to null

D. Cannot print data without a loop

Solution

1. Step 1: Check linking between nodes

   head.next is assigned second, but second.prev is not set to head.

2. Step 2: Identify missing backward link

   For doubly linked list, second.prev must point back to head to maintain two-way links.

3. Final Answer:

   Missing assignment of second.prev to head -> Option A

4. Quick Check:

   Both next and prev must be linked [OK]

Hint: Check both next and prev pointers after linking nodes [OK]

Common Mistakes:

• Forgetting to link prev pointer
• Assuming next pointer is enough
• Ignoring bidirectional links in doubly linked list

5. You want to create a doubly linked list from an array of integers [5, 10, 15] in Java. Which approach correctly initializes the list with proper next and prev links?

hard

A. Create nodes in a loop, link each node's next to the previous node, and set previous node's prev to current node.

B. Create nodes in a loop, link each node's prev to the next node, and set next node's next to current node.

C. Create nodes in a loop, link each node's prev to null, and next to null.

D. Create nodes in a loop, link each node's next to the next node, and set next node's prev to current node.

Solution

1. Step 1: Create nodes from array elements

   For each integer, create a new node with data set to that integer.

2. Step 2: Link nodes forward and backward

   Set current node's next to next node, and next node's prev to current node to maintain doubly linked structure.

3. Final Answer:

   Create nodes in a loop, link each node's next to the next node, and set next node's prev to current node. -> Option D

4. Quick Check:

   Proper doubly linked list needs next and prev links set correctly [OK]

Hint: Link next forward and prev backward in loop [OK]

Common Mistakes:

• Mixing up next and prev pointers
• Not setting prev pointer at all
• Setting prev pointer incorrectly to next node