Doubly Linked List Structure and Node Design in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a doubly linked list node with data and pointers.

DSA Go

type Node struct {
	data int
	prev *Node
	[1] *Node
}

Drag options to blanks, or click blank then click option'

Alink

Bprevious

Cnext

Dpointer

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'previous' instead of 'next' for the forward pointer.

Using generic names like 'link' or 'pointer' instead of 'next'.

The 'next' field points to the next node in the doubly linked list.

2fill in blank

medium

Complete the code to initialize a new node with given data.

DSA Go

func NewNode(data int) *Node {
	return &Node{
		data: [1],
		prev: nil,
		next: nil,
	}
}

Drag options to blanks, or click blank then click option'

Adata

B&data

C0

D*data

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of the input data parameter.

Using '&data' or '*data' which are incorrect here.

The 'data' field is set to the input parameter 'data' to store the node's value.

3fill in blank

hard

Fix the error in the method to set the next node pointer.

DSA Go

func (n *Node) SetNext([1] *Node) {
	n.next = node
}

Drag options to blanks, or click blank then click option'

AnewNode

BnextNode

Cn

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using a parameter name different from the variable assigned.

Using 'nextNode' in assignment but not as parameter.

The parameter name should be 'node' to match the assignment 'n.next = node'.

4fill in blank

hard

Fill both blanks to correctly link two nodes in a doubly linked list.

DSA Go

func LinkNodes(first, second *Node) {
	first.[1] = second
	second.[2] = first
}

Drag options to blanks, or click blank then click option'

Anext

Bprev

Clink

Dpointer

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up 'next' and 'prev' fields.

Using incorrect field names like 'link' or 'pointer'.

The first node's 'next' points to the second, and the second node's 'prev' points back to the first.

5fill in blank

hard

Fill all three blanks to create a new node and link it after an existing node.

DSA Go

func InsertAfter(existing *Node, data int) *Node {
	newNode := &Node{data: [1], prev: existing, next: existing.[2]
	if existing.[3] != nil {
		existing.next.prev = newNode
	}
	existing.next = newNode
	return newNode
}

Drag options to blanks, or click blank then click option'

Adata

Bnext

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' when accessing existing node's next pointer.

Not updating the previous pointer of the node after the new node.

The new node's data is set to 'data', its next pointer to existing.next, and the existing node's next pointer is used to update the previous pointer of the next node.

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