Create and Initialize Doubly Linked List in DSA Go - Execution Trace

Concept Flow - Create and Initialize Doubly Linked List

Allocate new node

↓

Set node.data = value

↓

Set node.prev = nil

↓

Set node.next = nil

↓

Set head = node

↓

List initialized with one node

The flow shows creating a new node, setting its data and pointers to nil, then assigning it as the head of the list.

Execution Sample

DSA Go

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

head := &Node{data: 10, prev: nil, next: nil}

This code creates a doubly linked list with one node containing data 10.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Allocate new node	None	None	List is empty
2	Set node.data = 10	Node(10)	node.data=10	10 <-> nil
3	Set node.prev = nil	Node(10)	node.prev=nil	nil <- 10
4	Set node.next = nil	Node(10)	node.next=nil	10 -> nil
5	Set head = node	Node(10)	head points to node	head -> 10 <-> nil
6	List initialized	Node(10)	head points to node	head -> 10 <-> nil

💡 List has one node; initialization complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
node.data	undefined	undefined	10	10	10	10	10
node.prev	undefined	undefined	undefined	nil	nil	nil	nil
node.next	undefined	undefined	undefined	undefined	nil	nil	nil
head	nil	nil	nil	nil	nil	node	node

Key Moments - 2 Insights

Why do we set node.prev and node.next to nil when creating the first node?

Because the first node has no neighbors, both pointers must be nil to show it is alone. See execution_table rows 3 and 4.

What does the head pointer represent after initialization?

Head points to the first node in the list. After step 5, head points to the new node as shown in execution_table row 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of node.prev?

A 10

B nil

C undefined

D head

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the head pointer start pointing to the new node?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Pointer Changes' column for head in execution_table.

If we skip setting node.next to nil, what would the visual state show at step 4?

A 10 -> garbage or unknown

B 10 <-> nil

C nil <- 10

D head -> 10 <-> nil

💡 Hint

Without setting node.next, the pointer could point anywhere; see execution_table step 4.

Concept Snapshot

Create a node struct with data, prev, next pointers
Set data to value, prev and next to nil
Assign head pointer to this node
Result: list with one node, no neighbors
Pointers show nil at ends
Ready for further insertions

Full Transcript

To create and initialize a doubly linked list, first allocate a new node. Set its data field to the desired value. Since this is the first node, set both prev and next pointers to nil to indicate no neighbors. Then assign the head pointer to this new node. The list now contains one node with data and no links to other nodes. This setup is the foundation for adding more nodes later.

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