Insert at End of Doubly Linked List in DSA Go - Time & Space Complexity

Time Complexity: Insert at End of Doubly Linked List

O(1)

Understanding Time Complexity

We want to understand how the time to insert a new item at the end of a doubly linked list changes as the list grows.

How does the number of steps needed grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// InsertAtEnd adds a new node with value at the end of the list
func (dll *DoublyLinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if dll.tail == nil {
        dll.head = newNode
        dll.tail = newNode
        return
    }
    dll.tail.next = newNode
    newNode.prev = dll.tail
    dll.tail = newNode
}
    

This code adds a new node to the end of a doubly linked list by updating pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Pointer updates to add the new node.
• How many times: Exactly once per insertion, no loops or traversals.

How Execution Grows With Input

Each insertion takes the same small number of steps, no matter how long the list is.

Input Size (n)	Approx. Operations
10	5 steps
100	5 steps
1000	5 steps

Pattern observation: The number of steps stays the same as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means inserting at the end takes a constant amount of time, no matter how big the list is.

Common Mistake

[X] Wrong: "Inserting at the end takes longer as the list grows because we have to find the end each time."

[OK] Correct: Because we keep a direct pointer to the tail node, we do not need to search; insertion is always quick.

Interview Connect

Knowing this helps you explain why doubly linked lists are useful for quick insertions at both ends, a common interview topic.

Self-Check

"What if we did not keep a tail pointer? How would the time complexity change?"

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