Create and Initialize Doubly Linked List in DSA Go

Mental Model

A doubly linked list is a chain of nodes where each node knows the node before and after it, allowing easy movement in both directions.

Analogy: Imagine a train where each carriage is connected to the one before and after it, so you can walk forward or backward through the train easily.

null ← [head] ↔ [node1] ↔ [node2] ↔ [node3] → null

Dry Run Walkthrough

Input: Create a doubly linked list with values 1, 2, 3 in order

Goal: Build the list so each node points to the next and previous nodes correctly

Step 1: Create the first node with value 1 and set it as head

null ← [1] → null

Why: We need a starting point for the list

Step 2: Create second node with value 2, link it after first node

null ← [1] ↔ [2] → null

Why: Add second node and connect it both ways

Step 3: Create third node with value 3, link it after second node

null ← [1] ↔ [2] ↔ [3] → null

Why: Add third node and complete the chain

Result:

null ← [1] ↔ [2] ↔ [3] → null

Annotated Code

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) Append(value int) {
	newNode := &Node{value: value}
	if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	// Link newNode after tail
	dll.tail.next = newNode
	newNode.prev = dll.tail
	// Update tail to newNode
	dll.tail = newNode
}

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

func main() {
	dll := DoublyLinkedList{}
	dll.Append(1)
	dll.Append(2)
	dll.Append(3)
	dll.PrintForward()
}

if dll.head == nil { dll.head = newNode dll.tail = newNode return }

Initialize head and tail when list is empty

dll.tail.next = newNode newNode.prev = dll.tail

Link new node after current tail both ways

dll.tail = newNode

Update tail pointer to new node

curr := dll.head for curr != nil { fmt.Printf("%d", curr.value) if curr.next != nil { fmt.Print(" -> ") } curr = curr.next }

Traverse list forward to print values

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) to create and print n nodes because each node is processed once

Space: O(n) because we store n nodes in memory

vs Alternative: Compared to singly linked list, doubly linked list uses more memory but allows backward traversal

Edge Cases

Empty list when appending first node

Head and tail both point to the new node

DSA Go

if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list to keep track of both previous and next nodes.

Common Mistakes

Mistake: Not updating the previous pointer of the new node
Fix: Set newNode.prev = dll.tail before updating tail

Mistake: Not updating the tail pointer after adding a new node
Fix: Assign dll.tail = newNode after linking

Summary

Creates a doubly linked list where each node links to the previous and next nodes.

Use when you want to traverse a list in both directions easily.

Remember to update both next and prev pointers and keep track of head and tail.

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