Create and Initialize Doubly Linked List in DSA Java - Execution Trace

Concept Flow - Create and Initialize Doubly Linked List

Create new node with data

↓

Is list empty?

↓

Set head and tail

↓

Set tail = newNode

↓

List updated

Start by creating a new node. If the list is empty, set head and tail to this node. Otherwise, link the new node after tail and update tail.

Execution Sample

DSA Java

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

Node head = null, tail = null;
// Insert 10
// Insert 20

This code creates nodes and inserts them into an empty doubly linked list, updating head and tail pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node with data=10	None	None	null
2	List empty? Yes, set head and tail to new node	10	head -> Node(10), tail -> Node(10)	null <- [10] -> null
3	Create node with data=20	10	None	null <- [10] -> null
4	List empty? No, link new node after tail	10 -> 20	Node(20).prev = tail(Node(10)), tail.next = Node(20), tail = Node(20)	null <- [10] <-> [20] -> null
5	End	10 -> 20	head -> Node(10), tail -> Node(20)	null <- [10] <-> [20] -> null

💡 All nodes inserted and pointers updated correctly.

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
head	null	Node(10)	Node(10)	Node(10)
tail	null	Node(10)	Node(20)	Node(20)
newNode	null	Node(10)	Node(20)	Node(20)

Key Moments - 3 Insights

Why do we set both head and tail to the new node when the list is empty?

Because when the list is empty, the new node is the only node, so it is both the start (head) and end (tail) of the list, as shown in step 2 of the execution_table.

Why do we update the new node's prev pointer to the current tail when adding to a non-empty list?

This links the new node back to the previous last node, maintaining the doubly linked structure. See step 4 in execution_table where Node(20).prev = Node(10).

What happens if we forget to update tail.next to the new node?

The list would break forward traversal because the old tail wouldn't point to the new node. Step 4 shows tail.next is updated to maintain the chain.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the visual state of the list?

A null <- [10] <-> [20] -> null

B null <- [10] -> null

C null -> [10] -> null

D [10] -> null

💡 Hint

Refer to the Visual State column at step 2 in execution_table.

At which step does the tail pointer update to the new node with data=20?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check the Pointer Changes column for tail updates in execution_table.

If the list was initially not empty, which pointer must be set on the new node to maintain the doubly linked list?

A newNode.prev = tail

B head.prev = newNode

C newNode.next = head

D tail.next = head

💡 Hint

See step 4 in execution_table where newNode.prev is set to tail.

Concept Snapshot

Create a new node with data.
If list empty: set head and tail to new node.
Else: newNode.prev = tail; tail.next = newNode; tail = newNode.
This keeps doubly linked list structure intact.
Visual: null <- [head] <-> ... <-> [tail] -> null

Full Transcript

To create and initialize a doubly linked list, start by creating a new node with the given data. If the list is empty, set both head and tail pointers to this new node, making it the only node in the list. If the list is not empty, link the new node after the current tail by setting the new node's prev pointer to the tail, the tail's next pointer to the new node, and then update the tail pointer to the new node. This process maintains the doubly linked structure where each node points to both its previous and next nodes. The execution table shows step-by-step how nodes are created and linked, and how pointers are updated. The variable tracker shows how head, tail, and newNode pointers change during the process. Key moments clarify why both head and tail are set when the list is empty, why prev pointer is set on the new node, and the importance of updating tail.next. The visual quiz tests understanding of the list's visual state and pointer updates.

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