Doubly Linked List Structure and Node Design in DSA Java - Execution Trace

Concept Flow - Doubly Linked List Structure and Node Design

Create Node with data

↓

Node has 3 parts: prev, data, next

↓

Link node.prev to previous node

↓

Link node.next to next node

↓

Node connected both ways

↓

Traverse forward or backward using next/prev pointers

Shows how a doubly linked list node is created with links to both previous and next nodes, enabling two-way traversal.

Execution Sample

DSA Java

class Node {
  int data;
  Node prev;
  Node next;

  Node(int data) {
    this.data = data;
  }
}

Defines a doubly linked list node with data and pointers to previous and next nodes.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node with data=10	Node(10)	prev=null, next=null	null <- [10] -> null
2	Create node with data=20	Node(10), Node(20)	prev=null, next=null	null <- [10] -> null null <- [20] -> null
3	Link node(20) prev to node(10)	Node(10), Node(20)	node(20).prev = node(10)	null <- [10] -> null null <- [20] -> null
4	Link node(10) next to node(20)	Node(10), Node(20)	node(10).next = node(20)	null <- [10] <-> [20] -> null
5	Traverse forward from node(10)	Node(10), Node(20)	current = node(10) -> node(20)	[10] <-> [20]
6	Traverse backward from node(20)	Node(10), Node(20)	current = node(20) -> node(10)	[10] <-> [20]
7	End of demonstration	Node(10), Node(20)	No pointer changes	[10] <-> [20]

💡 Demonstration ends after creating two nodes and linking them bidirectionally.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
node(10).prev	null	null	null	null	null	null	null	null
node(10).next	null	null	null	null	node(20)	node(20)	node(20)	node(20)
node(20).prev	null	null	null	node(10)	node(10)	node(10)	node(10)	node(10)
node(20).next	null	null	null	null	null	null	null	null
current (forward traverse)	null	node(10)	node(10)	node(10)	node(10)	node(20)	node(20)	node(20)
current (backward traverse)	null	null	null	null	null	null	node(10)	node(10)

Key Moments - 3 Insights

Why does each node have both prev and next pointers?

Because the doubly linked list allows moving forward and backward. The prev pointer links to the previous node, and the next pointer links to the next node, as shown in steps 3 and 4 of the execution_table.

What is the visual difference between a singly linked list node and a doubly linked list node?

A singly linked list node has only one pointer (next), while a doubly linked list node has two pointers (prev and next). This is shown in the visual state where nodes are connected with arrows in both directions.

Why does the traversal start from node(10) and move to node(20) using next pointer?

Because node(10).next points to node(20), allowing forward traversal. This is shown in step 5 where current moves from node(10) to node(20).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what pointer change happens?

A node(20).next is set to node(10)

B node(10).prev is set to node(20)

C node(10).next is set to node(20)

D node(20).prev is set to null

💡 Hint

Check the Pointer Changes column at step 4 in the execution_table.

At which step does node(20).prev get assigned to node(10)?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the Pointer Changes column for node(20).prev in the execution_table.

If node(10).next was not linked to node(20), what would happen during forward traversal?

A Traversal would stop at node(10)

B Traversal would continue to node(20)

C Traversal would go backward

D Traversal would skip node(20)

💡 Hint

Refer to the variable_tracker for node(10).next and the forward traversal steps.

Concept Snapshot

Doubly Linked List Node:
- Has three parts: prev, data, next
- prev points to previous node or null
- next points to next node or null
- Enables two-way traversal
- Nodes linked by setting prev and next pointers

Full Transcript

A doubly linked list node stores data and two pointers: one to the previous node and one to the next node. This allows moving forward and backward through the list. We create nodes with data, then link their prev and next pointers to connect them. Traversal uses these pointers to move through the list in either direction. The execution steps show creating two nodes, linking them, and traversing forward and backward.

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