Insert at End of Doubly Linked List in DSA Java - Execution Trace

Concept Flow - Insert at End of Doubly Linked List

Create new node

↓

Is list empty?

↓

head = new

↓

Traverse to last node

↓

last.next = new

↓

new.prev = last

↓

Done

Create a new node, check if list is empty, if yes set head to new node; else traverse to last node and link new node at end.

Execution Sample

DSA Java

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

// Insert at end method
void insertEnd(int data) {
  Node newNode = new Node(data);

This code creates a new node and prepares to insert it at the end of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	Empty	newNode: data=10, prev=null, next=null	∅ (empty list)
2	Check if list is empty	Empty	head == null → True	∅ (empty list)
3	Set head = newNode	1 node	head → newNode	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
4	Create new node with data=20	1 node	newNode: data=20, prev=null, next=null	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
5	Check if list is empty	1 node	head == null → False	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
6	Start at head to traverse	1 node	current → head (data=10)	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head/current
7	Traverse to last node (current.next == null)	1 node	current.next == null → True (stop)	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head/current
8	Link newNode at end: current.next = newNode	2 nodes	current.next → newNode	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head newNode
9	Set newNode.prev = current	2 nodes	newNode.prev → current	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head newNode
10	Create new node with data=30	2 nodes	newNode: data=30, prev=null, next=null	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
11	Check if list is empty	2 nodes	head == null → False	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
12	Start at head to traverse	2 nodes	current → head (data=10)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head/current
13	Traverse: current.next != null? Yes (move current)	2 nodes	current → current.next (data=20)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
14	Traverse: current.next != null? No (stop)	2 nodes	current.next == null → True	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:──┼ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
15	Link newNode at end: current.next = newNode	3 nodes	current.next → newNode	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:──┼←── │ prev:∅ │ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head current newNode
16	Set newNode.prev = current	3 nodes	newNode.prev → current	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:──┼←── │ prev:──┼ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head current newNode
17	End of insertion	3 nodes	List updated with new node at end	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:──┼←── │ prev:──┼ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head node2 new tail

💡 Traversal stops when current.next is null, indicating last node reached.

Variable Tracker

Variable	Start	After Step 3	After Step 8	After Step 9	After Step 15	After Step 16	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
newNode	null	null	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)
current	null	null	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)
List Size	0	1	2	2	3	3	3

Key Moments - 3 Insights

Why do we check if the list is empty before traversing?

Because if the list is empty (head == null), we directly set head to newNode (see step 2 and 3). Traversing would cause errors if list is empty.

Why do we stop traversal when current.next is null, not current itself?

Because current.next == null means current is the last node. We want to insert after last node, so we stop at last node (see step 7 and 14).

Why do we set newNode.prev = current after linking current.next = newNode?

To maintain backward links in doubly linked list. After linking forward pointer, we link backward pointer (see steps 8 and 9).

Visual Quiz - 3 Questions

Look at the execution table at step 9, what is the prev pointer of the new node?

A Points to the last node (data=10)

B Points to null

C Points to head

D Points to itself

💡 Hint

Check 'Pointer Changes' and 'Visual State' columns at step 9 in execution_table.

At which step does the list first have two nodes?

A Step 3

B Step 8

C Step 15

D Step 16

💡 Hint

Look at 'Nodes in List' column in execution_table to find when it changes to 2 nodes.

If the list was empty, which step sets the head pointer to the new node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Refer to 'Pointer Changes' at step 3 where head is assigned.

Concept Snapshot

Insert at End of Doubly Linked List:
- Create new node with data
- If list empty, head = new node
- Else traverse to last node
- Set last.next = new node
- Set new node.prev = last
- New node's next = null (tail)

Full Transcript

To insert at the end of a doubly linked list, first create a new node with the given data. Check if the list is empty by seeing if head is null. If empty, set head to the new node. If not empty, start at head and move through nodes until you find the last node (where next is null). Then set the last node's next pointer to the new node, and set the new node's prev pointer back to the last node. The new node's next pointer is null, marking it as the new tail. This process maintains both forward and backward links in the list.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To reverse the list

B. To remove the first node

C. To add a new element after the last node

D. To find the middle node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected both forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option C

4. Quick Check:

   Insert at end = Add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion at end reverses the list
• Assuming insertion at end finds middle node

2. Which of the following is the correct way to update the 'next' pointer of the last node when inserting a new node at the end in Java?

easy

A. last.next = newNode;

B. newNode.next = last;

C. last.prev = newNode;

D. newNode.prev = null;

Solution

1. Step 1: Identify the last node's next pointer

   The last node's 'next' pointer should point to the new node being inserted.

2. Step 2: Correct assignment for insertion

   Assigning 'last.next = newNode;' correctly links the last node to the new node.

3. Final Answer:

   last.next = newNode; -> Option A

4. Quick Check:

   Last node's next points to new node [OK]

Hint: Last node's next must point to new node [OK]

Common Mistakes:

• Assigning newNode.next to last instead of last.next to newNode
• Changing last.prev instead of last.next
• Setting newNode.prev to null incorrectly

3. What will be the output of the following code snippet after inserting 40 at the end of the doubly linked list?

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

class DoublyLinkedList {
  Node head;
  void insertEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node last = head;
    while (last.next != null) last = last.next;
    last.next = newNode;
    newNode.prev = last;
  }
  void printList() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " <-> ");
      temp = temp.next;
    }
    System.out.println("null");
  }
}

public class Main {
  public static void main(String[] args) {
    DoublyLinkedList dll = new DoublyLinkedList();
    dll.insertEnd(10);
    dll.insertEnd(20);
    dll.insertEnd(30);
    dll.insertEnd(40);
    dll.printList();
  }
}

medium

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

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

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

D. null

Solution

1. Step 1: Trace insertions in order

   Nodes 10, 20, 30, then 40 are inserted at the end, so list grows as 10 <-> 20 <-> 30 <-> 40.

2. Step 2: Print list traversal

   Print starts at head (10) and moves forward printing each node's data followed by ' <-> ', ending with 'null'.

3. Final Answer:

   10 <-> 20 <-> 30 <-> 40 <-> null -> Option A

4. Quick Check:

   Insertion at end appends nodes in order [OK]

Hint: Insertion order matches printed list [OK]

Common Mistakes:

• Assuming new node is added at start
• Forgetting to update newNode.prev
• Printing list incorrectly or missing null

4. Identify the error in the following insertEnd method for a doubly linked list:

void insertEnd(int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
  } else {
    Node last = head;
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.next = last;
  }
}

medium

A. last.next should be set to head

B. The while loop condition should be last.prev != null

C. head should be updated to newNode when list is empty

D. newNode.next should be set to null, not last

Solution

1. Step 1: Analyze pointer assignments after loop

   After finding last node, last.next is set to newNode correctly, but newNode.next is wrongly set to last (previous node).

2. Step 2: Correct pointer for newNode.next

   Since newNode is last, its next should be null, and newNode.prev should point to last.

3. Final Answer:

   newNode.next should be set to null, not last -> Option D

4. Quick Check:

   Last node's next = newNode; newNode.next = null [OK]

Hint: Last node's next points newNode; newNode.next is null [OK]

Common Mistakes:

• Setting newNode.next to last instead of null
• Not updating newNode.prev to last
• Incorrect loop condition in while

5. Given a doubly linked list with nodes 5 <-> 15 <-> 25, write the sequence of pointer updates needed to insert a new node with value 35 at the end. Which of the following correctly describes the steps?

hard

A. Set newNode.prev and newNode.next to null, head to newNode

B. Set newNode.prev to last node, last.next to newNode, newNode.next to null

C. Set newNode.next to last node, last.prev to newNode, newNode.prev to null

D. Set last.next to null, newNode.prev to null, newNode.next to last

Solution

1. Step 1: Identify last node and new node pointers

   The last node is 25; newNode is 35. For insertion at end, newNode.prev must point to last node, and last.next must point to newNode.

2. Step 2: Set newNode.next to null

   Since newNode is now last, its next pointer must be null to mark list end.

3. Final Answer:

   Set newNode.prev to last node, last.next to newNode, newNode.next to null -> Option B

4. Quick Check:

   Insert at end updates prev and next pointers correctly [OK]

Hint: New node prev = last; last next = new node; new node next = null [OK]

Common Mistakes:

• Swapping prev and next pointers incorrectly
• Not setting newNode.next to null
• Changing head pointer unnecessarily