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

Concept Flow - Insert at End of Doubly Linked List

Create new node with data

↓

Is list empty?

↓

Set head = new

↓

Traverse to last node

↓

Set last.next = new

↓

Set new.prev = last

↓

Done

Create a new node, check if list is empty, if yes set head to new node. Otherwise, traverse to last node, link new node after it, update pointers.

Execution Sample

DSA Go

func InsertEnd(head *Node, data int) *Node {
  newNode := &Node{data: data}
  if head == nil {
    return newNode
  }
  current := head
  for current.next != nil {
    current = current.next
  }
  current.next = newNode
  newNode.prev = current
  return head
}

This function inserts a new node with given data 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=40	10 <-> 20 <-> 30	newNode created with data=40, prev=null, next=null	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ ∅ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Check if head is nil	10 <-> 20 <-> 30	head is not nil, proceed to traverse	Same as step 1
3	Traverse to last node	10 <-> 20 <-> 30	current moves from 10 to 20	Same as step 1, current at 20
4	Traverse to last node	10 <-> 20 <-> 30	current moves from 20 to 30	Same as step 1, current at 30
5	Set current.next = newNode	10 <-> 20 <-> 30 40	30.next → 40	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ prev:∅ │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
6	Set newNode.prev = current	10 <-> 20 <-> 30 <-> 40	40.prev → 30	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
7	Return head	10 <-> 20 <-> 30 <-> 40	No pointer changes	Final list: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head

💡 Traversal ends when current.next is nil (at node with data 30), new node linked after it.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
newNode	nil	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)
current	nil	nil	Node(10)	Node(20)	Node(30)	Node(30)	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we check current.next != nil instead of current != nil when traversing?

Because we want to stop at the last node, not after it. current.next == nil means current is last node. See execution_table steps 3 and 4 where current moves until current.next is nil.

What happens if the list is empty (head == nil)?

We create a new node and set it as head immediately, no traversal needed. See execution_table step 2 where head is checked for nil.

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

Because in doubly linked list, newNode's prev pointer must point back to the last node to maintain two-way links. See execution_table step 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 4?

A Node with data 20

B Node with data 30

C Node with data 40

D nil

💡 Hint

Check the 'current' variable in variable_tracker after step 4.

At which step does the new node get linked as the next of the last node?

A Step 6

B Step 3

C Step 5

D Step 7

💡 Hint

Look at the 'Pointer Changes' column in execution_table for when 30.next points to 40.

If the list was empty, which step would immediately return the new node as head?

A Step 2

B Step 3

C Step 1

D Step 7

💡 Hint

See the check for head == nil in execution_table step 2.

Concept Snapshot

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

Full Transcript

This visualization shows how to insert a new node at the end of a doubly linked list. We start by creating a new node with the given data. If the list is empty (head is nil), we set the head to this new node immediately. Otherwise, we traverse the list starting from head until we find the last node, which is identified by current.next being nil. Then we link the new node after the last node by setting last node's next pointer to the new node and the new node's prev pointer back to the last node. Finally, we return the head pointer. The pointer diagrams show the list before and after insertion, and the variable tracker follows the positions of head, current, and newNode through each step.

Practice

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

easy

A. To add a new element after the last node

B. To remove the first node

C. To reverse the list

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 forward and backward, allowing traversal in both directions.

2. Step 2: Identify the effect of inserting 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 A

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 reverses the list
• Assuming insertion happens at the start

2. Which of the following Go code snippets correctly updates the 'next' pointer when inserting a new node at the end of a doubly linked list?

easy

A. newNode.next = last

B. newNode.prev = last.next

C. last.next = newNode

D. last.prev = newNode

Solution

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

   When inserting at the end, the last node's next pointer should point to the new node.

2. Step 2: Match correct pointer assignment

   Setting last.next = newNode correctly links the last node to the new node.

3. Final Answer:

   last.next = newNode -> Option C

4. Quick Check:

   last.next points to new node [OK]

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

Common Mistakes:

• Assigning newNode.prev to last.next incorrectly
• Setting newNode.next to last (wrong direction)
• Changing last.prev instead of last.next

3. What will be the printed output of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end in order? Assume the print function shows values from head to tail.

medium

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

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

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

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

Solution

1. Step 1: Insert 10 at end when list is empty

   List becomes: 10 -> null

2. Step 2: Insert 20 at end

   List becomes: 10 <-> 20 -> null

3. Step 3: Insert 30 at end

   List becomes: 10 <-> 20 <-> 30 -> null

4. Final Answer:

   10 <-> 20 <-> 30 <-> null -> Option D

5. Quick Check:

   Insert order preserved from head to tail [OK]

Hint: Insertion at end keeps order as inserted [OK]

Common Mistakes:

• Assuming insertion reverses order
• Printing null at start instead of end
• Mixing node order in output

4. Given the following Go code snippet for inserting at the end of a doubly linked list, what is the error?

func InsertEnd(head *Node, data int) *Node {
    newNode := &Node{data: data}
    if head == nil {
        head = newNode
    } else {
        temp := head
        for temp.next != nil {
            temp = temp.next
        }
        temp.next = newNode
        newNode.prev = temp
    }
    return head
}

medium

A. The newNode's prev pointer is incorrectly assigned

B. The newNode's next pointer is not set to nil

C. The loop condition should be temp.prev != nil

D. The function does not update the head when list is empty

Solution

1. Step 1: Check newNode pointer initialization

   In Go, uninitialized pointers default to nil, but explicitly setting newNode.next = nil is safer.

2. Step 2: Identify missing explicit next pointer assignment

   The code does not set newNode.next = nil, which can cause issues if newNode is reused or inspected.

3. Final Answer:

   The newNode's next pointer is not set to nil -> Option B

4. Quick Check:

   Always set newNode.next = nil at insertion [OK]

Hint: Always set newNode.next = nil when inserting at end [OK]

Common Mistakes:

• Ignoring explicit nil assignment for newNode.next
• Confusing prev and next pointers
• Incorrect loop condition for traversal

5. You have a doubly linked list with nodes 5 <-> 15 <-> 25. You want to insert a new node with value 35 at the end. After insertion, which pointers must be updated to maintain list integrity?

hard

A. Set last node's next to new node, new node's prev to last node, new node's next to nil

B. Set new node's next to last node, last node's prev to new node

C. Set head's prev to new node, new node's next to head

D. Set new node's prev and next to nil only

Solution

1. Step 1: Identify the last node before insertion

   The last node is the one with value 25.

2. Step 2: Update pointers to insert new node at end

   Set last node's next to new node, new node's prev to last node, and new node's next to nil to mark end.

3. Final Answer:

   Set last node's next to new node, new node's prev to last node, new node's next to nil -> Option A

4. Quick Check:

   Last.next = new, new.prev = last, new.next = nil [OK]

Hint: Update last.next, new.prev, and new.next for end insertion [OK]

Common Mistakes:

• Reversing prev and next pointers
• Not setting new node's next to nil
• Changing head pointers incorrectly