Circular vs Linear Linked List Key Difference in DSA Go - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

Key difference between Circular and Linear Linked Lists

Which statement correctly describes the main difference between a circular linked list and a linear linked list?

A In a circular linked list, the last node points back to the first node, while in a linear linked list, the last node points to null.

B In a linear linked list, the last node points back to the first node, while in a circular linked list, the last node points to null.

C Both circular and linear linked lists have their last node pointing to null.

D Both circular and linear linked lists have their last node pointing back to the first node.

💡 Hint

Think about how the last node connects in each type of linked list.

A circular linked list connects the last node back to the first node, forming a circle. A linear linked list ends with a node pointing to null.

❓ Predict Output

intermediate

Output of traversing a circular linked list

What will be the output of traversing this circular linked list starting from head and printing 5 nodes?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1 // circular link

    current := n1
    for i := 0; i < 5; i++ {
        fmt.Print(current.value, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

A 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> null

B 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> null

C 1 -> 2 -> 3 -> 1 -> 2 -> null

D 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> null

💡 Hint

Remember the loop repeats after the last node points back to the first.

The circular linked list loops back after node 3 to node 1. Printing 5 nodes starting from 1 gives: 1, 2, 3, 1, 2.

🔧 Debug

advanced

Identify the bug in linear linked list traversal

What error will this Go code produce when traversing a linear linked list?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n1.next = n2
    n2.next = n3
    n3.next = nil

    current := n1
    for current != nil {
        fmt.Print(current.value, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

A Runtime error: nil pointer dereference

B No error, output: 1 -> 2 -> 3 -> null

C Syntax error: missing import fmt

D Infinite loop

💡 Hint

Check how the loop ends when current is nil.

The code correctly traverses the linear linked list until current is nil, then stops. No errors occur.

❓ Predict Output

advanced

Output after inserting node in circular linked list

What is the printed output after inserting a new node with value 4 after node with value 3 in this circular linked list?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1 // circular

    newNode := &Node{value: 4}
    newNode.next = n3.next
    n3.next = newNode

    current := n1
    for i := 0; i < 6; i++ {
        fmt.Print(current.value, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

A 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> null

B 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> null

C 1 -> 2 -> 3 -> 4 -> 1 -> 4 -> null

D 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> null

💡 Hint

Check how the new node links after node 3 and the circular nature.

After insertion, the list is 1 -> 2 -> 3 -> 4 -> back to 1. Printing 6 nodes gives 1,2,3,4,1,2.

🧠 Conceptual

expert

Memory usage difference between circular and linear linked lists

Which statement about memory usage difference between circular and linear linked lists is true?

A Circular linked lists use less memory because they do not need a null pointer at the end.

B Linear linked lists use more memory because they store an extra pointer to the tail node.

C Circular linked lists use more memory because they store an extra pointer to the head node.

D Both use the same amount of memory per node; the difference is only in the last node's next pointer value.

💡 Hint

Consider what each node stores in both types of lists.

Each node in both lists stores one pointer to the next node. The difference is the last node's next pointer points to null or head, but memory per node is the same.

Practice

1. What is the main difference between a circular linked list and a linear linked list?

easy

A. Circular linked lists do not have a head node.

B. In a linear linked list, the last node points back to the first node, forming a circle.

C. Both circular and linear linked lists have their last node pointing to null.

D. In a circular linked list, the last node points back to the first node, forming a circle.

Solution

1. Step 1: Understand the last node pointer in linear linked list

   In a linear linked list, the last node points to null, indicating the end of the list.

2. Step 2: Understand the last node pointer in circular linked list

   In a circular linked list, the last node points back to the first node, creating a loop or circle.

3. Final Answer:

   In a circular linked list, the last node points back to the first node, forming a circle. -> Option D

4. Quick Check:

   Last node points to first node = Circular linked list [OK]

Hint: Last node points to first node only in circular lists [OK]

Common Mistakes:

• Confusing last node pointer in linear and circular lists
• Thinking circular lists end with null
• Assuming circular lists have no head node

2. Which of the following is the correct way to check if a linked list is circular in Go?

easy

A. if last.next == nil { return true } else if last.next == head { return false }

B. if head == nil { return true } else if last.next == nil { return true }

C. if head == nil { return false } else if head.next == nil { return false } else if last.next == head { return true }

D. if head.next == nil { return true } else if last.next == nil { return false }

Solution

1. Step 1: Check if list is empty or has one node

   If head is nil or head.next is nil, list cannot be circular, so return false.

2. Step 2: Check if last node points back to head

   If last.next equals head, the list is circular, so return true.

3. Final Answer:

   if head == nil { return false } else if head.next == nil { return false } else if last.next == head { return true } -> Option C

4. Quick Check:

   Last node points to head means circular [OK]

Hint: Check last.next == head to confirm circular list [OK]

Common Mistakes:

• Returning true when list is empty
• Checking last.next == nil for circularity
• Confusing conditions for circular check

3. Consider the following Go code snippet for a circular linked list:

type Node struct {
    data int
    next *Node
}

func printList(head *Node) {
    if head == nil {
        fmt.Println("Empty list")
        return
    }
    current := head
    for {
        fmt.Print(current.data, " -> ")
        current = current.next
        if current == head {
            break
        }
    }
    fmt.Println("null")
}

func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1
    printList(n1)
}

What will be the output?

medium

A. 1 -> 2 -> 3 -> null

B. 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ... (infinite loop)

C. Empty list

D. 1 -> 2 -> 3

Solution

1. Step 1: Understand the circular linked list structure

   Nodes 1, 2, 3 are linked circularly: last node points back to first node.

2. Step 2: Trace the printList function loop

   Loop prints current.data and moves to next node until current equals head again, then breaks.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Loop stops when current == head, so no infinite loop [OK]

Hint: Loop breaks when current returns to head in circular list [OK]

Common Mistakes:

• Assuming infinite loop without break
• Printing 'Empty list' incorrectly
• Missing 'null' at end of output

4. The following Go code tries to detect if a linked list is circular but has a bug:

func isCircular(head *Node) bool {
    current := head
    for current != nil {
        if current.next == head {
            return true
        }
        current = current.next
    }
    return false
}

What is the bug in this code?

medium

A. It may cause infinite loop if list has a cycle not pointing to head.

B. It does not handle empty list (head == nil) case.

C. It incorrectly returns true for linear lists.

D. It uses wrong comparison operator for pointers.

Solution

1. Step 1: Analyze the loop condition and pointer movement

   The loop moves current until current is nil, checking if current.next == head.

2. Step 2: Identify the bug with cycles not pointing to head

   If the list has a cycle but not pointing to head, current will never be nil, causing infinite loop.

3. Final Answer:

   It may cause infinite loop if list has a cycle not pointing to head. -> Option A

4. Quick Check:

   Cycle detection needs more robust method than this [OK]

Hint: Cycle not pointing to head causes infinite loop here [OK]

Common Mistakes:

• Ignoring infinite loop possibility
• Assuming only head cycles exist
• Not checking for nil head

5. You have a linked list where the last node points back to the third node (not the head). Which statement is true about this list?

hard

A. It is a linear linked list because the last node does not point to head.

B. It is neither circular nor linear linked list.

C. It is a circular linked list because it has a cycle.

D. It is a doubly linked list.

Solution

1. Step 1: Recall definition of circular linked list

   A circular linked list specifically has its last node pointing back to the head (first node), forming a complete circle.

2. Step 2: Analyze the given list

   The last node points to the third node, creating a cycle but not pointing to head, so not circular. Linear lists end with null (no cycle). Thus, neither.

3. Final Answer:

   It is neither circular nor linear linked list. -> Option B

4. Quick Check:

   Circular requires last -> head specifically [OK]

Hint: Circular LL requires last -> head; other cycles != circular LL [OK]

Common Mistakes:

• Thinking any cycle makes it circular LL
• Confusing with doubly linked list
• Thinking it's linear despite cycle