Why Create and Initialize Doubly Linked List in DSA Go?

The Big Idea

What if you could add or remove tasks instantly without rewriting your whole list?

The Scenario

Imagine you have a list of tasks written on paper, and you want to add or remove tasks easily from both the start and the end.

Doing this by rewriting the whole list every time is tiring and slow.

The Problem

Manually rewriting or shifting tasks every time you add or remove one wastes time and causes mistakes.

It's hard to keep track of what comes before or after each task without a clear system.

The Solution

A doubly linked list is like a chain where each task knows the one before and after it.

This lets you add or remove tasks quickly from anywhere without rewriting the whole list.

Before vs After

✗ Before

tasks := []string{"task1", "task2", "task3"}
// To add at start, shift all right and insert
tasks = append(tasks, "")
for i := len(tasks) - 1; i > 0; i-- {
    tasks[i] = tasks[i-1]
}
tasks[0] = "newTask"

✓ After

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

head := &Node{data: "task1"}
newNode := &Node{data: "newTask"}
newNode.next = head
head.prev = newNode
head = newNode

What It Enables

You can quickly add or remove items from both ends or the middle without moving everything else.

Real Life Example

Think of a music playlist where you can easily go to the previous or next song, add a new song anywhere, or remove one without stopping the music.

Key Takeaways

Manual list changes are slow and error-prone.

Doubly linked lists let each item know its neighbors for easy updates.

This makes adding or removing items fast and simple.

Practice

1. What is the main purpose of a doubly linked list in data structures?

easy

A. To sort data automatically

B. To store data in a fixed-size array

C. To allow traversal in both forward and backward directions

D. To store data only in a single direction

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes with pointers to both previous and next nodes.

2. Step 2: Identify traversal capability

   This structure allows moving forward and backward through the list easily.

3. Final Answer:

   To allow traversal in both forward and backward directions -> Option C

4. Quick Check:

   Doubly linked list = bidirectional traversal [OK]

Hint: Remember: doubly means two directions [OK]

Common Mistakes:

• Confusing doubly linked list with arrays
• Thinking it sorts data automatically
• Assuming it only moves forward

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

easy

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

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

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

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

Solution

1. Step 1: Check pointer usage for next and prev

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

2. Step 2: Verify data types

   Data is int, and next and prev are pointers to Node, matching type Node struct { data int; next *Node; prev *Node }.

3. Final Answer:

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

4. Quick Check:

   Pointers for next and prev = type Node struct { data int; next *Node; prev *Node } [OK]

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

Common Mistakes:

• Using value types instead of pointers for next/prev
• Using wrong pointer types like *int
• Missing semicolons or commas (Go allows semicolons but usually uses new lines)

3. What will be the output of the following Go code that creates a doubly linked list with nodes 1, 2, 3 and prints forward traversal?

package main
import "fmt"
type Node struct {
  data int
  next *Node
  prev *Node
}
func main() {
  head := &Node{data: 1}
  second := &Node{data: 2}
  third := &Node{data: 3}
  head.next = second
  second.prev = head
  second.next = third
  third.prev = second
  current := head
  for current != nil {
    fmt.Print(current.data)
    if current.next != nil {
      fmt.Print(" -> ")
    }
    current = current.next
  }
  fmt.Println(" -> null")
}

medium

A. 3 -> 2 -> 1 -> null

B. null -> 1 -> 2 -> 3

C. 1 2 3 null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Understand list creation and linking

   Nodes 1, 2, 3 are linked forward: head.next = second, second.next = third.

2. Step 2: Trace forward traversal loop

   Starting at head, prints 1, then 2, then 3, each followed by ' -> ', ending with ' -> null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Forward traversal prints nodes in order [OK]

Hint: Follow next pointers from head to print forward [OK]

Common Mistakes:

• Confusing forward and backward traversal
• Missing arrows in output
• Printing data without separators

4. Identify the error in the following Go code that tries to initialize a doubly linked list node:

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

func main() {
  node := Node{data: 10, next: nil, prev: nil}
  node.next.prev = &node
}

medium

A. prev pointer should not be assigned

B. node.next is nil, so node.next.prev causes a runtime panic

C. Syntax error: missing & before node initialization

D. data field must be a pointer

Solution

1. Step 1: Analyze node initialization

   node.next is set to nil, so node.next does not point to any node.

2. Step 2: Check node.next.prev assignment

   Accessing node.next.prev tries to dereference nil, causing runtime panic (nil pointer dereference).

3. Final Answer:

   node.next is nil, so node.next.prev causes a runtime panic -> Option B

4. Quick Check:

   Dereferencing nil pointer = runtime panic [OK]

Hint: Never access fields of nil pointers [OK]

Common Mistakes:

• Ignoring nil pointer dereference
• Thinking &node is needed for struct literal
• Confusing data type requirements

5. You want to create a doubly linked list in Go with nodes containing values 5, 10, 15, and 20. Which code snippet correctly initializes the list and sets all next and prev pointers properly?

hard

A. head := &Node{data: 5}
second := &Node{data: 10}
third := &Node{data: 15}
fourth := &Node{data: 20}
head.next = second
second.prev = head
second.next = third
third.prev = second
third.next = fourth
fourth.prev = third

B. head := Node{data: 5}
second := Node{data: 10}
third := Node{data: 15}
fourth := Node{data: 20}
head.next = &second
second.prev = &head
second.next = &third
third.prev = &second
third.next = &fourth
fourth.prev = &third

C. head := &Node{data: 5, next: &Node{data: 10, prev: head}}
head.next.next = &Node{data: 15, prev: head.next}
head.next.next.next = &Node{data: 20, prev: head.next.next}

D. head := &Node{data: 5}
head.next = &Node{data: 10, prev: head}
head.next.next = &Node{data: 15, prev: head.next}
head.next.next.next = &Node{data: 20, prev: head.next.next}
head.next.next.next.next = nil

Solution

1. Step 1: Check pointer usage and linking

   head := &Node{data: 5} second := &Node{data: 10} third := &Node{data: 15} fourth := &Node{data: 20} head.next = second second.prev = head second.next = third third.prev = second third.next = fourth fourth.prev = third uses pointers for all nodes and sets next and prev pointers explicitly and correctly.

2. Step 2: Verify all links are consistent

   Each node's next points forward, and prev points backward, matching doubly linked list rules.

3. Final Answer:

   Code snippet in Option A correctly initializes and links all nodes -> Option A

4. Quick Check:

   Proper pointer linking = head := &Node{data: 5} second := &Node{data: 10} third := &Node{data: 15} fourth := &Node{data: 20} head.next = second second.prev = head second.next = third third.prev = second third.next = fourth fourth.prev = third [OK]

Hint: Use pointers and set both next and prev for each node [OK]

Common Mistakes:

• Using value types instead of pointers for nodes
• Not setting prev pointers
• Incorrect nested initialization causing nil prev