Why Doubly Linked List Structure and Node Design in DSA Go?

The Big Idea

What if you could travel a list forwards and backwards without ever getting lost or stuck?

The Scenario

Imagine you have a long chain of paper clips linked together. You want to add or remove clips from anywhere in the chain, but you can only move forward from the first clip to the last. If you want to go backward, you have to start over from the beginning.

The Problem

Using a simple chain like this, going backward is slow and frustrating because you must start from the front every time. Adding or removing clips in the middle means you have to find the right spot by moving step-by-step from the start, which wastes time and can cause mistakes.

The Solution

A doubly linked list is like a chain where each paper clip knows both its next and previous clip. This lets you move forward or backward easily. Adding or removing clips anywhere becomes quick and safe because you can jump directly to the right spot and update links in both directions.

Before vs After

✗ Before

type Node struct {
    value int
    next *Node
}

// To go backward, you must start from head and move forward until you find the node before current.

✓ After

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

// Each node knows its previous and next, so you can move both ways easily.

What It Enables

It enables fast and flexible navigation and updates in both directions of a list, making data management smoother and more efficient.

Real Life Example

Think of a music playlist where you can skip forward or backward between songs instantly, add new songs anywhere, or remove songs without restarting the list.

Key Takeaways

Doubly linked lists let you move forward and backward easily.

Each node stores links to both next and previous nodes.

This design makes adding and removing elements anywhere faster and safer.

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