Insert at End of Doubly Linked List in DSA Go

Mental Model

A doubly linked list is a chain of nodes where each node knows its previous and next neighbor. To add a new node at the end, we link it after the last node and update pointers accordingly.

Analogy: Imagine a train where each carriage is connected to the one before and after it. Adding a new carriage at the end means hooking it to the last carriage and making sure both know about each other.

null ← 1 ↔ 2 ↔ 3 -> null
↑head                      ↑tail

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

null ← 1 ↔ 2 ↔ 3 -> null    4 (new node, not linked yet)

Why: We need a new node to insert at the end

Step 2: Set new node's previous pointer to current tail (3)

null ← 1 ↔ 2 ↔ 3 ← 4    4.prev = 3, 4.next = null

Why: New node must know the node before it

Step 3: Set current tail's next pointer to new node

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Why: Old last node must point forward to new node

Step 4: Update tail pointer to new node

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑head                      ↑tail

Why: Tail must always point to the last node

Result:

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
head points to 1, tail points to 4

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	val  int
	prev *Node
	next *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (dll *DoublyLinkedList) InsertAtEnd(value int) {
	newNode := &Node{val: value}
	if dll.head == nil {
		// List empty, new node is head and tail
		dll.head = newNode
		dll.tail = newNode
		return
	}
	// Link new node after tail
	newNode.prev = dll.tail
	dll.tail.next = newNode
	// Update tail pointer
	dll.tail = newNode
}

func (dll *DoublyLinkedList) PrintList() {
	curr := dll.head
	for curr != nil {
		fmt.Printf("%d", curr.val)
		if curr.next != nil {
			fmt.Printf(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	dll := &DoublyLinkedList{}
	dll.InsertAtEnd(1)
	dll.InsertAtEnd(2)
	dll.InsertAtEnd(3)
	dll.InsertAtEnd(4) // Insert value 4 at end
	dll.PrintList()
}

newNode := &Node{val: value}

Create new node with given value

if dll.head == nil {

Check if list is empty to initialize head and tail

newNode.prev = dll.tail

Set new node's previous pointer to current tail

dll.tail.next = newNode

Link current tail's next pointer to new node

dll.tail = newNode

Update tail pointer to new node

Output

1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(1) because we directly access the tail and update pointers without traversal

Space: O(1) because we only create one new node regardless of list size

vs Alternative: Compared to singly linked list without tail pointer, which requires O(n) traversal to insert at end, this method is faster and more efficient

Edge Cases

Empty list

New node becomes both head and tail

DSA Go

if dll.head == nil {

Single element list

New node links after the single node and tail updates

DSA Go

dll.tail.next = newNode

When to Use This Pattern

When you need to add elements at the end of a list efficiently, and the list supports backward and forward links, use the Insert at End of Doubly Linked List pattern to update pointers in constant time.

Common Mistakes

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

Mistake: Not updating the tail pointer to the new node after insertion
Fix: Set dll.tail = newNode to keep tail accurate

Summary

Adds a new node at the end of a doubly linked list by updating pointers.

Use when you want to efficiently append elements to the end of a doubly linked list.

The key is to link the new node after the current tail and then update the tail pointer.

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