Insert at Specific Position in Doubly Linked List in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting at position 3

What is the printed state of the doubly linked list after inserting value 99 at position 3?

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
}

func (dll *DoublyLinkedList) InsertAtPosition(data int, pos int) {
    newNode := &Node{data: data}
    if pos == 1 {
        newNode.next = dll.head
        if dll.head != nil {
            dll.head.prev = newNode
        }
        dll.head = newNode
        return
    }
    current := dll.head
    for i := 1; current != nil && i < pos-1; i++ {
        current = current.next
    }
    if current == nil {
        return
    }
    newNode.next = current.next
    if current.next != nil {
        current.next.prev = newNode
    }
    current.next = newNode
    newNode.prev = current
}

func (dll *DoublyLinkedList) PrintList() {
    current := dll.head
    for current != nil {
        fmt.Print(current.data)
        if current.next != nil {
            fmt.Print(" <-> ")
        }
        current = current.next
    }
    fmt.Println()
}

func main() {
    dll := &DoublyLinkedList{}
    dll.InsertAtPosition(10, 1)
    dll.InsertAtPosition(20, 2)
    dll.InsertAtPosition(30, 3)
    dll.InsertAtPosition(40, 4)
    dll.InsertAtPosition(99, 3)
    dll.PrintList()
}

A 10 <-> 20 <-> 30 <-> 99 <-> 40

B 10 <-> 20 <-> 99 <-> 30 <-> 40

C 10 <-> 99 <-> 20 <-> 30 <-> 40

D 99 <-> 10 <-> 20 <-> 30 <-> 40

💡 Hint

Remember that position 3 means the new node goes after the second node.

The new node with value 99 is inserted after the node with value 20 (position 2), so it becomes the third node.

❓ Predict Output

intermediate

Output after inserting at head position

What is the printed state of the doubly linked list after inserting value 5 at position 1 (head)?

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
}

func (dll *DoublyLinkedList) InsertAtPosition(data int, pos int) {
    newNode := &Node{data: data}
    if pos == 1 {
        newNode.next = dll.head
        if dll.head != nil {
            dll.head.prev = newNode
        }
        dll.head = newNode
        return
    }
    current := dll.head
    for i := 1; current != nil && i < pos-1; i++ {
        current = current.next
    }
    if current == nil {
        return
    }
    newNode.next = current.next
    if current.next != nil {
        current.next.prev = newNode
    }
    current.next = newNode
    newNode.prev = current
}

func (dll *DoublyLinkedList) PrintList() {
    current := dll.head
    for current != nil {
        fmt.Print(current.data)
        if current.next != nil {
            fmt.Print(" <-> ")
        }
        current = current.next
    }
    fmt.Println()
}

func main() {
    dll := &DoublyLinkedList{}
    dll.InsertAtPosition(10, 1)
    dll.InsertAtPosition(20, 2)
    dll.InsertAtPosition(30, 3)
    dll.InsertAtPosition(5, 1)
    dll.PrintList()
}

A 10 <-> 5 <-> 20 <-> 30

B 10 <-> 20 <-> 30 <-> 5

C 5 <-> 10 <-> 20 <-> 30

D 5 <-> 20 <-> 10 <-> 30

💡 Hint

Inserting at position 1 means the new node becomes the new head.

The new node with value 5 is inserted at the head, pushing the existing nodes forward.

🔧 Debug

advanced

Identify the bug causing incorrect insertion at tail

The following code tries to insert a node at position 5 in a list of 4 nodes but fails to insert correctly. What is the bug?

DSA Go

func (dll *DoublyLinkedList) InsertAtPosition(data int, pos int) {
    newNode := &Node{data: data}
    if pos == 1 {
        newNode.next = dll.head
        if dll.head != nil {
            dll.head.prev = newNode
        }
        dll.head = newNode
        return
    }
    current := dll.head
    for i := 1; current != nil && i < pos-1; i++ {
        current = current.next
    }
    if current == nil {
        return
    }
    newNode.next = current.next
    if current.next != nil {
        current.next.prev = newNode
    }
    current.next = newNode
    newNode.prev = current
}

A The loop condition should be i <= pos-1 instead of i < pos-1.

B The newNode.prev is not set correctly before insertion.

C The head pointer is not updated when inserting at tail.

D The code does not handle insertion at position beyond list length, so insertion at tail fails.

💡 Hint

Check what happens when pos is exactly one more than the current list length.

If pos is beyond the current list length + 1, current becomes nil and insertion is skipped. The code does not allow insertion at tail if pos is exactly list length + 1.

❓ Predict Output

advanced

Output after multiple insertions at various positions

What is the printed state of the doubly linked list after these insertions? Insert 1 at pos 1 Insert 2 at pos 2 Insert 3 at pos 2 Insert 4 at pos 4 Insert 5 at pos 3

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
}

func (dll *DoublyLinkedList) InsertAtPosition(data int, pos int) {
    newNode := &Node{data: data}
    if pos == 1 {
        newNode.next = dll.head
        if dll.head != nil {
            dll.head.prev = newNode
        }
        dll.head = newNode
        return
    }
    current := dll.head
    for i := 1; current != nil && i < pos-1; i++ {
        current = current.next
    }
    if current == nil {
        return
    }
    newNode.next = current.next
    if current.next != nil {
        current.next.prev = newNode
    }
    current.next = newNode
    newNode.prev = current
}

func (dll *DoublyLinkedList) PrintList() {
    current := dll.head
    for current != nil {
        fmt.Print(current.data)
        if current.next != nil {
            fmt.Print(" <-> ")
        }
        current = current.next
    }
    fmt.Println()
}

func main() {
    dll := &DoublyLinkedList{}
    dll.InsertAtPosition(1, 1)
    dll.InsertAtPosition(2, 2)
    dll.InsertAtPosition(3, 2)
    dll.InsertAtPosition(4, 4)
    dll.InsertAtPosition(5, 3)
    dll.PrintList()
}

A 1 <-> 3 <-> 2 <-> 5 <-> 4

B 1 <-> 2 <-> 5 <-> 3 <-> 4

C 1 <-> 2 <-> 3 <-> 5 <-> 4

D 1 <-> 3 <-> 5 <-> 2 <-> 4

💡 Hint

Trace each insertion step carefully, updating the list each time.

After all insertions, the list is: 1 (pos1), 3 (pos2), 2 (pos3), 5 (pos4), 4 (pos5).

🧠 Conceptual

expert

Why is updating both prev and next pointers important in doubly linked list insertion?

When inserting a new node at a specific position in a doubly linked list, why must we update both the prev and next pointers of the involved nodes?

A To maintain the bidirectional links so traversal in both directions works correctly.

B Only the next pointer is important; prev pointers are optional and can be ignored.

C Updating prev pointers is only needed when inserting at the head, not in the middle or tail.

D Because Go requires explicit pointer updates to avoid garbage collection issues.

💡 Hint

Think about how you move forward and backward in the list.

Doubly linked lists allow moving forward and backward. If prev or next pointers are not updated correctly, traversal in one direction will break.

Practice

1. What does inserting a node at a specific position in a doubly linked list involve?

easy

A. Only changing the head pointer of the list

B. Adjusting the previous and next pointers of neighboring nodes to include the new node

C. Replacing the node at that position without changing pointers

D. Appending the node at the end regardless of position

Solution

1. Step 1: Understand doubly linked list structure

   Each node has pointers to both previous and next nodes, so insertion requires updating these pointers.

2. Step 2: Insert node at specific position

   To insert, update the previous node's next pointer and the next node's previous pointer to point to the new node.

3. Final Answer:

   Adjusting the previous and next pointers of neighboring nodes to include the new node -> Option B

4. Quick Check:

   Pointer updates = A [OK]

Hint: Remember both previous and next pointers must be updated [OK]

Common Mistakes:

• Only updating one pointer and ignoring the other
• Not handling edge cases like insertion at head or tail
• Replacing node data instead of inserting new node

2. Which of the following Go code snippets correctly declares a doubly linked list node struct for insertion?

easy

A. type Node struct { data int; prev *Node; next *Node }

B. type Node struct { data int; next *Node }

C. type Node struct { data int; prev int; next int }

D. type Node struct { data int; prev Node; next Node }

Solution

1. Step 1: Check struct fields for doubly linked list

   A doubly linked list node must have pointers to previous and next nodes, both of type *Node.

2. Step 2: Validate Go syntax

   type Node struct { data int; prev *Node; next *Node } correctly uses pointers (*Node) for prev and next fields, matching doubly linked list requirements.

3. Final Answer:

   type Node struct { data int; prev *Node; next *Node } -> Option A

4. Quick Check:

   Pointers for prev and next = A [OK]

Hint: Use *Node type for prev and next pointers in struct [OK]

Common Mistakes:

• Using non-pointer types for prev and next
• Omitting prev pointer for doubly linked list
• Using incorrect field types like int for pointers

3. What will be the output of the doubly linked list after inserting a node with value 25 at position 3 in the list 10 <-> 20 <-> 30 <-> 40?

medium

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

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

C. 25 <-> 10 <-> 20 <-> 30 <-> 40

D. 10 <-> 20 <-> 30 <-> 40 <-> 25

Solution

1. Step 1: Identify position 3 in the list

   Positions: 1=10, 2=20, 3=30, 4=40. Inserting at position 3 means before node with value 30.

2. Step 2: Insert node with value 25 at position 3

   New node 25 goes between 20 and 30, updating pointers accordingly.

3. Final Answer:

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

4. Quick Check:

   Insert before 3rd node = D [OK]

Hint: Insert before node currently at that position [OK]

Common Mistakes:

• Inserting after the node at position instead of before
• Appending at end instead of correct position
• Confusing position indexing starting at 0

4. Given the following Go code snippet for insertion, what is the error?

func InsertAtPosition(head *Node, data int, pos int) *Node {
    newNode := &Node{data: data}
    if pos == 1 {
        newNode.next = head
        head.prev = newNode
        head = newNode
        return head
    }
    temp := head
    for i := 1; i < pos-1; i++ {
        temp = temp.next
    }
    newNode.next = temp.next
    temp.next.prev = newNode
    temp.next = newNode
    newNode.prev = temp
    return head
}

medium

A. Incorrect assignment of newNode.prev

B. Missing creation of newNode

C. No check if temp or temp.next is nil before accessing pointers

D. Returning newNode instead of head

Solution

1. Step 1: Analyze pointer usage in loop and insertion

   The loop moves temp to position before insertion. If pos is beyond list length, temp or temp.next can be nil.

2. Step 2: Identify missing nil checks

   Accessing temp.next.prev without checking if temp.next is nil can cause runtime panic.

3. Final Answer:

   No check if temp or temp.next is nil before accessing pointers -> Option C

4. Quick Check:

   Missing nil checks cause runtime errors [OK]

Hint: Always check for nil before accessing next or prev pointers [OK]

Common Mistakes:

• Ignoring nil pointer checks causing crashes
• Incorrect pointer assignments order
• Returning wrong node pointer

5. You have a doubly linked list: 5 <-> 15 <-> 25 <-> 35. You want to insert a node with value 20 at position 3. After insertion, what will be the correct order of nodes and how should pointers be updated?

hard

A. 5 <-> 20 <-> 15 <-> 25 <-> 35; update 5.next to 20, 20.prev to 5, 20.next to 15, 15.prev to 20

B. 5 <-> 15 <-> 25 <-> 20 <-> 35; update 25.next to 20, 20.prev to 25, 20.next to 35, 35.prev to 20

C. 20 <-> 5 <-> 15 <-> 25 <-> 35; update head to 20, 20.next to 5, 5.prev to 20

D. 5 <-> 15 <-> 20 <-> 25 <-> 35; update 15.next to 20, 20.prev to 15, 20.next to 25, 25.prev to 20

Solution

1. Step 1: Determine correct insertion position

   Position 3 means node with value 20 goes between nodes 15 (pos 2) and 25 (pos 3).

2. Step 2: Update pointers for insertion

   Set 15.next to new node 20, 20.prev to 15, 20.next to 25, and 25.prev to 20 to maintain list integrity.

3. Final Answer:

   5 <-> 15 <-> 20 <-> 25 <-> 35; update 15.next to 20, 20.prev to 15, 20.next to 25, 25.prev to 20 -> Option D

4. Quick Check:

   Insert between 15 and 25 with pointer updates = C [OK]

Hint: Insert between nodes and update four pointers correctly [OK]

Common Mistakes:

• Swapping nodes or inserting at wrong position
• Forgetting to update prev pointers
• Incorrectly updating next pointers causing broken links