Doubly Linked List Structure and Node Design in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
    tail *Node
}

func (dll *DoublyLinkedList) InsertEnd(val int) {
    newNode := &Node{value: val}
    if dll.head == nil {
        dll.head = newNode
        dll.tail = newNode
        return
    }
    dll.tail.next = newNode
    newNode.prev = dll.tail
    dll.tail = newNode
}

func (dll *DoublyLinkedList) PrintForward() {
    current := dll.head
    for current != nil {
        fmt.Printf("%d", current.value)
        if current.next != nil {
            fmt.Printf(" <-> ")
        }
        current = current.next
    }
    fmt.Println()
}

func main() {
    dll := DoublyLinkedList{}
    dll.InsertEnd(10)
    dll.InsertEnd(20)
    dll.InsertEnd(30)
    dll.PrintForward()
}

A 30 -> 20 -> 10

B 30 <-> 20 <-> 10

C 10 -> 20 -> 30

D 10 <-> 20 <-> 30

💡 Hint

Think about how nodes are linked when inserted at the end and how PrintForward prints the list.

The InsertEnd method adds nodes at the tail, so the list grows as 10, then 20, then 30. PrintForward prints from head to tail with <-> between nodes.

❓ Predict Output

intermediate

Value of Tail Node After Insertions

After inserting nodes with values 5, 15, and 25 at the beginning of the doubly linked list, what is the value of the tail node?

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
    tail *Node
}

func (dll *DoublyLinkedList) InsertBeginning(val int) {
    newNode := &Node{value: val}
    if dll.head == nil {
        dll.head = newNode
        dll.tail = newNode
        return
    }
    newNode.next = dll.head
    dll.head.prev = newNode
    dll.head = newNode
}

func main() {
    dll := DoublyLinkedList{}
    dll.InsertBeginning(5)
    dll.InsertBeginning(15)
    dll.InsertBeginning(25)
    fmt.Println(dll.tail.value)
}

A 5

B 15

C 25

D 0

💡 Hint

Inserting at the beginning shifts the head but tail remains the first inserted node.

Inserting at the beginning adds new nodes before the current head. The tail remains the first inserted node, which is 5.

🔧 Debug

advanced

Identify the Bug in Node Removal Method

What error will occur when running this RemoveNode method on a doubly linked list if the node to remove is the tail?

DSA Go

func (dll *DoublyLinkedList) RemoveNode(node *Node) {
    if node.prev != nil {
        node.prev.next = node.next
    } else {
        dll.head = node.next
    }
    if node.next != nil {
        node.next.prev = node.prev
    } else {
        dll.tail = node.prev
    }
    node = nil
}

A No error; node is removed correctly

B Runtime error due to nil pointer dereference

C The tail pointer is not updated correctly, causing stale tail

D The node variable is not removed from memory causing memory leak

💡 Hint

Check how tail and head pointers are updated when removing nodes at ends.

The method correctly updates head and tail pointers when removing nodes at ends. Setting node = nil only changes local pointer, no error occurs.

❓ Predict Output

advanced

Output After Reversing Doubly Linked List

What is the printed state of the doubly linked list after reversing it? Initial list is 1 <-> 2 <-> 3.

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
    head *Node
    tail *Node
}

func (dll *DoublyLinkedList) Reverse() {
    current := dll.head
    var temp *Node
    for current != nil {
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    }
    if temp != nil {
        dll.head = temp.prev
    }
}

func (dll *DoublyLinkedList) PrintForward() {
    current := dll.head
    for current != nil {
        fmt.Printf("%d", current.value)
        if current.next != nil {
            fmt.Printf(" <-> ")
        }
        current = current.next
    }
    fmt.Println()
}

func main() {
    dll := DoublyLinkedList{}
    dll.head = &Node{value: 1}
    node2 := &Node{value: 2}
    node3 := &Node{value: 3}
    dll.head.next = node2
    node2.prev = dll.head
    node2.next = node3
    node3.prev = node2
    dll.tail = node3
    dll.PrintForward()
    dll.Reverse()
    dll.PrintForward()
}

A 3 -> 2 -> 1

B 1 <-> 2 <-> 3

C 3 <-> 2 <-> 1

D 1 -> 2 -> 3

💡 Hint

Reversing swaps next and prev pointers and updates head to old tail.

The Reverse method swaps next and prev for each node and sets head to old tail, so the list prints reversed order.

🧠 Conceptual

expert

Memory Management in Doubly Linked List Node Deletion

In Go, when a node is removed from a doubly linked list by updating pointers and setting the node variable to nil inside the removal function, what happens to the memory allocated for that node?

A Memory is immediately freed because node is set to nil

B Memory is freed only if no other references to the node exist, handled by Go's garbage collector

C Memory leaks occur because Go does not free memory automatically

D Memory is freed only when the program ends

💡 Hint

Think about how Go manages memory and garbage collection.

Go uses garbage collection. Setting node = nil removes one reference, but memory is freed only when no references remain.

Practice

1. What is the main purpose of the prev pointer in a doubly linked list node?

easy

A. To point to the previous node in the list

B. To point to the next node in the list

C. To store the data value of the node

D. To indicate the end of the list

Solution

1. Step 1: Understand the role of pointers in doubly linked list nodes

   Each node in a doubly linked list has two pointers: one to the next node and one to the previous node.

2. Step 2: Identify the function of the prev pointer

   The prev pointer specifically points to the node that comes before the current node in the list.

3. Final Answer:

   To point to the previous node in the list -> Option A

4. Quick Check:

   prev pointer = previous node [OK]

Hint: Prev pointer always links backward to previous node [OK]

Common Mistakes:

• Confusing prev with next pointer
• Thinking prev stores data
• Assuming prev marks list end

2. Which of the following is the correct way to define a doubly linked list node struct in Go?

easy

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

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

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

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

Solution

1. Step 1: Recall Go struct pointer usage for linked nodes

   In Go, linked list nodes use pointers to other nodes to link them, so next and prev must be pointers to Node.

2. Step 2: Check each option for correct pointer types

   type Node struct { data int; next *Node; prev *Node } uses *Node for both next and prev, which is correct. type Node struct { data int; next Node; prev Node } uses non-pointer types, which is incorrect. type Node struct { data int; next *int; prev *int } uses pointers to int, which is wrong. type Node struct { data int; next *Node; prev int } mixes pointer and int, which is invalid.

3. Final Answer:

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

4. Quick Check:

   Pointers to Node = correct struct [OK]

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

Common Mistakes:

• Using non-pointer types for next or prev
• Using wrong pointer types like *int
• Mixing pointer and non-pointer fields

3. Given the following Go code for a doubly linked list node insertion, what will be the printed list after inserting nodes with values 1, 2, and 3 at the end?

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

func printList(head *Node) {
  for head != nil {
    fmt.Print(head.data, " ")
    head = head.next
  }
  fmt.Println()
}

func main() {
  var head *Node
  head = &Node{data: 1}
  second := &Node{data: 2}
  third := &Node{data: 3}

  head.next = second
  second.prev = head
  second.next = third
  third.prev = second

  printList(head)
}

medium

A. 1 3 2

B. 1 2 3

C. 3 2 1

D. 2 1 3

Solution

1. Step 1: Understand the node linking order

   The nodes are linked as 1 -> 2 -> 3 with proper next and prev pointers.

2. Step 2: Trace the printList function

   Starting from head (node with data 1), the function prints 1, moves to next (2), prints 2, moves to next (3), prints 3, then stops at nil.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Traversal from head prints 1 2 3 [OK]

Hint: Traverse from head using next pointers to print list [OK]

Common Mistakes:

• Confusing prev and next pointers during traversal
• Printing in reverse order mistakenly
• Not linking nodes correctly

4. Identify the error in the following Go code snippet for inserting a new node at the beginning of a doubly linked list:

func insertAtBeginning(head *Node, data int) *Node {
  newNode := &Node{data: data}
  newNode.next = head
  head.prev = newNode
  return newNode
}

medium

A. Missing check if head is nil before setting head.prev

B. newNode.prev should point to head

C. Function should not return *Node

D. newNode.next should be nil

Solution

1. Step 1: Analyze the code for edge cases

   The code sets head.prev = newNode without checking if head is nil, which causes a runtime error if the list is empty.

2. Step 2: Identify the missing nil check

   Before setting head.prev, the code should check if head != nil to avoid dereferencing nil pointer.

3. Final Answer:

   Missing check if head is nil before setting head.prev -> Option A

4. Quick Check:

   Check for nil head before accessing prev [OK]

Hint: Always check if head is nil before accessing its fields [OK]

Common Mistakes:

• Not checking for nil head causing runtime panic
• Confusing prev and next pointers
• Incorrect return type assumptions

5. You want to implement a function in Go that reverses a doubly linked list by swapping the next and prev pointers of each node. Which of the following code snippets correctly performs this reversal?

hard

A. func reverse(head *Node) *Node {
current := head
var temp *Node
for current != nil {
temp = current.next
current.next = current.prev
current.prev = temp
current = current.prev
}
if temp != nil {
head = temp.prev
}
return head
}

B. func reverse(head *Node) *Node {
current := head
for current != nil {
current.next, current.prev = current.prev, current.next
current = current.next
}
return head
}

C. func reverse(head *Node) *Node {
current := head
var prev *Node
for current != nil {
prev = current.prev
current.prev = current.next
current.next = prev
current = current.next
}
return prev
}

D. func reverse(head *Node) *Node {
current := head
var temp *Node
for current != nil {
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
}
if temp != nil {
head = temp.prev
}
return head
}

Solution

1. Step 1: Understand the reversal logic for doubly linked list

   Reversing means swapping next and prev pointers for each node, then moving to the original next node (which becomes prev after swap).

2. Step 2: Analyze each code snippet for correctness

   func reverse(head *Node) *Node { current := head var temp *Node for current != nil { temp = current.prev current.prev = current.next current.next = temp current = current.prev } if temp != nil { head = temp.prev } return head } correctly swaps pointers and moves current to current.prev (original next). It updates head to the last processed node. func reverse(head *Node) *Node { current := head var temp *Node for current != nil { temp = current.next current.next = current.prev current.prev = temp current = current.prev } if temp != nil { head = temp.prev } return head } swaps pointers but moves current incorrectly and updates head wrongly.

3. Final Answer:

   func reverse(head *Node) *Node { current := head var temp *Node for current != nil { temp = current.prev current.prev = current.next current.next = temp current = current.prev } if temp != nil { head = temp.prev } return head } -> Option D

4. Quick Check:

   Swap next and prev, move current to original next [OK]

Hint: Swap next and prev, move to original next (now prev) [OK]

Common Mistakes:

• Not updating head to new first node
• Moving current pointer incorrectly after swap
• Returning wrong node as head