Circular vs Linear Linked List Key Difference in DSA Go - Trade-offs & Analysis

Mental Model

A linear linked list ends with a node pointing to nothing, while a circular linked list loops back to the start, forming a circle.

Analogy: Think of a line of people holding hands (linear) versus a circle of people holding hands where the last person holds the first person's hand (circular).

Linear: 1 -> 2 -> 3 -> null
Circular: 1 -> 2 -> 3 -> (back to 1)

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, show difference between linear and circular

Goal: Understand how the last node points in linear vs circular linked list

Step 1: Create linear linked list nodes 1, 2, 3 with last node pointing to null

1 -> 2 -> 3 -> null

Why: Linear list ends with null to mark the end

Step 2: Create circular linked list nodes 1, 2, 3 with last node pointing back to first node

1 -> 2 -> 3 -> (back to 1)

Why: Circular list loops back to start to form a circle

Step 3: Traverse linear list until node points to null

Traverse: 1 -> 2 -> 3 -> null (stop)

Why: Traversal ends at null in linear list

Step 4: Traverse circular list stopping after visiting all nodes once

Traverse: 1 -> 2 -> 3 -> (back to 1, stop to avoid infinite loop)

Why: Traversal must stop manually to avoid infinite loop in circular list

Result:

Linear: 1 -> 2 -> 3 -> null
Circular: 1 -> 2 -> 3 -> (back to 1)

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

// createLinearList creates a linear linked list 1->2->3->null
func createLinearList() *Node {
	n1 := &Node{value: 1}
	n2 := &Node{value: 2}
	n3 := &Node{value: 3}
	n1.next = n2 // link 1 to 2
	n2.next = n3 // link 2 to 3
	n3.next = nil // end of list
	return n1
}

// createCircularList creates a circular linked list 1->2->3->(back to 1)
func createCircularList() *Node {
	n1 := &Node{value: 1}
	n2 := &Node{value: 2}
	n3 := &Node{value: 3}
	n1.next = n2 // link 1 to 2
	n2.next = n3 // link 2 to 3
	n3.next = n1 // link 3 back to 1
	return n1
}

// printLinearList prints nodes until nil
func printLinearList(head *Node) {
	curr := head
	for curr != nil {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next // advance to next node
	}
	fmt.Println("null")
}

// printCircularList prints nodes once in circular list
func printCircularList(head *Node) {
	if head == nil {
		fmt.Println("null")
		return
	}
	curr := head
	for {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next // advance to next node
		if curr == head {
			break // stop after full circle
		}
	}
	fmt.Printf("(back to %d)\n", head.value)
}

func main() {
	linear := createLinearList()
	circular := createCircularList()

	fmt.Println("Linear Linked List:")
	printLinearList(linear)

	fmt.Println("Circular Linked List:")
	printCircularList(circular)
}

curr = curr.next // advance to next node

advance curr to next node to traverse list

if curr == head { break // stop after full circle }

stop traversal after one full circle to avoid infinite loop

Output

Linear Linked List:

1 -> 2 -> 3 -> null

Circular Linked List:

1 -> 2 -> 3 -> (back to 1)

Complexity Analysis

Time: O(n) because we visit each node once during traversal

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

vs Alternative: Circular lists require careful stopping condition to avoid infinite loops, unlike linear lists which end at null

Edge Cases

empty list (head is nil)

print functions handle nil head and print 'null' without error

DSA Go

if head == nil { fmt.Println("null") return }

single node list

linear list ends at null; circular list points back to itself

DSA Go

n1.next = nil // linear end or n1.next = n1 // circular loop

When to Use This Pattern

When you see a linked list problem where the last node points back to the first node, recognize it as a circular linked list and handle traversal carefully to avoid infinite loops.

Common Mistakes

Mistake: Traversing a circular linked list without a stopping condition causes infinite loop
Fix: Add a check to stop traversal when the pointer returns to the head node

Summary

Linear linked list ends with a null pointer; circular linked list loops back to the start node.

Use circular linked lists when you want to cycle through elements repeatedly without end.

The key insight is that circular lists have no null end, so traversal must detect the loop to stop.

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