Circular vs Linear Linked List Key Difference in DSA Go - Visual Comparison

Concept Flow - Circular vs Linear Linked List Key Difference

Create new node

↓

Is list empty?

Yes→Set head = new node

↓

For Linear: node.next = nil

↓

Traverse to last node

↓

For Circular: node.next = head

↓

Set last node.next = new node

↓

Done

Shows how new nodes are added differently in linear and circular linked lists, focusing on the last node's next pointer.

Execution Sample

DSA Go

// Go code snippet demonstrating insertion

type Node struct {
    Value int
    Next  *Node
}

// Linear Singly Linked List insertion at end
func InsertLinear(head **Node, val int) {
    node := &Node{Value: val}
    if *head == nil {
        *head = node
        node.Next = nil
        return
    }
    curr := *head
    for curr.Next != nil {
        curr = curr.Next
    }
    curr.Next = node
    node.Next = nil
}

// Circular Singly Linked List insertion at end
func InsertCircular(head **Node, val int) {
    node := &Node{Value: val}
    if *head == nil {
        *head = node
        node.Next = node  // points to head (self)
        return
    }
    curr := *head
    for curr.Next != *head {
        curr = curr.Next
    }
    curr.Next = node
    node.Next = *head
}

// Usage:
var headL, headC *Node
InsertLinear(&headL, 1)  // Step 1-2
InsertLinear(&headL, 2)  // Step 3-4
// headL -> 1 -> 2 -> nil

InsertCircular(&headC, 1)  // Step 1-2
InsertCircular(&headC, 2)  // Step 3-4
// headC -> 1 -> 2 -> headC

Adds two nodes to both linear and circular linked lists and shows the difference in the last node's next pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node with value 1	None	None	List is empty
2	Add node to empty list	1	head -> node1	node1(value=1) -> nil (Linear) node1(value=1) -> head (Circular)
3	Create node with value 2	1	None	node1(value=1) present
4	Add node to list	2	node1.next -> node2	node1(value=1) -> node2(value=2) -> nil (Linear) node1(value=1) -> node2(value=2) -> head (Circular)
5	Check last node's next pointer	2	None	Linear last node.next = nil Circular last node.next = head
6	End	2	No changes	Stop: last node.next points nil (Linear) or head (Circular)

💡 Stop after adding two nodes and observing last node's next pointer difference

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
head	nil	node1	node1	node1
node1.next	nil	nil (Linear) / head (Circular)	node2	node2
node2.next	nil	nil	nil (Linear) / head (Circular)	nil (Linear) / head (Circular)

Key Moments - 3 Insights

Why does the last node's next pointer differ between linear and circular linked lists?

In the execution_table at step 4 and 5, linear lists set last node.next to nil to mark the end, while circular lists set last node.next to head to form a loop.

What happens when adding the first node to an empty list?

Step 2 shows head points to the new node, and for circular lists, the node's next points back to head, creating a self-loop.

How do we know when to stop traversing in each list type?

In linear lists, traversal stops when node.next is nil (step 5), but in circular lists, traversal must check if next is head to avoid infinite loops.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does node1.next point to in a circular linked list?

A nil

B node2

C head

D node1

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 4 for circular list

At which step does the last node's next pointer become nil in a linear linked list?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Visual State' column describing last node.next in linear list at step 4

If we add a third node to the circular linked list, what will the last node's next pointer be?

A head

B nil

C node2

D node3

💡 Hint

Recall from the concept_flow and execution_table that circular lists link last node back to head

Concept Snapshot

Circular vs Linear Linked List Key Difference:
- Linear list last node.next = nil (end of list)
- Circular list last node.next = head (forms a loop)
- Adding first node sets head and next accordingly
- Traversal stops at nil (linear) or when next is head (circular)
- Circular lists allow continuous cycling through nodes

Full Transcript

This visual execution compares circular and linear linked lists by adding two nodes. Initially, the list is empty. Adding the first node sets the head pointer. In linear lists, the last node's next pointer is nil, marking the end. In circular lists, the last node's next points back to head, creating a loop. Traversal in linear lists stops at nil, while in circular lists it stops when the next node is head to avoid infinite loops. This key difference affects how we add nodes and traverse the list.

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