Doubly Linked List Structure and Node Design in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has two links: one to the next node and one to the previous node. This allows moving forward and backward through the list.

beginner

What fields does a node in a doubly linked list usually have?

A node usually has three fields: the data it holds, a pointer to the next node, and a pointer to the previous node.

intermediate

Why do doubly linked lists have a previous pointer?

The previous pointer allows moving backward in the list, making operations like reverse traversal and deletion easier compared to singly linked lists.

beginner

Show the Go struct for a doubly linked list node holding an integer value.

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

beginner

What is the main difference between singly and doubly linked lists in terms of node structure?

Singly linked list nodes have only one pointer to the next node, while doubly linked list nodes have two pointers: one to the next node and one to the previous node.

Which pointer in a doubly linked list node points to the previous node?

A prev

B next

C data

D head

The 'prev' pointer in a doubly linked list node points to the previous node.

What is the benefit of having a 'prev' pointer in a doubly linked list?

A Saves memory

B Allows backward traversal

C Simplifies node data

D Prevents loops

The 'prev' pointer allows moving backward through the list.

In Go, how do you declare a pointer to a Node struct named 'next' inside the Node struct?

A next Node*

B *next Node

C Node *next

D next *Node

The correct syntax is 'next *Node' to declare a pointer named 'next' to a Node.

Which of these is NOT a field in a typical doubly linked list node?

A head

B prev

C next

D data

'head' is usually a pointer to the first node in the list, not a field inside a node.

What does the 'next' pointer in a doubly linked list node do?

A Stores the node's data

B Points to the previous node

C Points to the next node

D Points to the list's tail

The 'next' pointer points to the next node in the list.

Describe the structure of a doubly linked list node and explain why it has two pointers.

Think about how you can move through the list in both directions.

Write the Go struct definition for a doubly linked list node that stores an integer.

Remember to use pointers for prev and next fields.

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