Doubly Linked List Structure and Node Design in DSA Go

Mental Model

A doubly linked list is a chain of nodes where each node knows both its neighbor before and after it. This lets us move forward and backward easily.

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

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

Dry Run Walkthrough

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

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

Step 1: Create node 1 with prev=null and next=null

null ← [1] → null

Why: Start with the first node which has no neighbors yet

Step 2: Create node 2 and link it after node 1

null ← [1] ↔ [2] → null

Why: Link node 2 after node 1, so node 1's next points to 2 and node 2's prev points to 1

Step 3: Create node 3 and link it after node 2

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

Why: Link node 3 after node 2, completing the chain with correct prev and next pointers

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.Print(curr.value)
		if curr.next != nil {
			fmt.Print(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println()
}

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 }

handle empty list by setting head and tail to new node

dll.tail.next = newNode

link current tail's next to new node

newNode.prev = dll.tail

link new node's prev to current tail

dll.tail = newNode

update tail pointer to new node

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(1) because appending only changes pointers at the tail without traversal

Space: O(n) because each node stores two pointers and a value for n nodes

vs Alternative: Compared to singly linked list, doubly linked list uses more space but allows backward traversal and easier node removal

Edge Cases

empty list

head and tail are nil, append sets both to new node

DSA Go

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

single node list

append links new node after tail and updates tail

DSA Go

dll.tail.next = newNode

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list because each node links both ways.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer when appending
Fix: Always set newNode.prev = current tail to maintain backward link

Mistake: Not updating the tail pointer after adding a new node
Fix: Set tail = newNode after linking to keep tail accurate

Summary

It creates a chain of nodes where each node points to both previous and next nodes.

Use it when you want to move forward and backward through a list efficiently.

The key is each node has two pointers, allowing easy two-way navigation.

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