Circular vs Linear Linked List Key Difference in DSA Go - Build Both Approaches

Understanding Circular vs Linear Linked List Key Difference

📖 Scenario: Imagine you are organizing a small music playlist. You want to understand how songs can be connected in two ways: one where the playlist ends after the last song, and another where the playlist loops back to the first song, playing endlessly.

🎯 Goal: You will create two simple linked lists in Go: one linear (ends after last song) and one circular (loops back to first song). You will see the key difference by printing their structure.

📋 What You'll Learn

Create a linear linked list with three songs named exactly: "Song1", "Song2", "Song3"

Create a circular linked list with the same three songs

Use a struct called Node with fields data string and next *Node

Print the linear linked list nodes in order ending with nil

Print the circular linked list nodes in order stopping after one full loop

💡 Why This Matters

🌍 Real World

Circular linked lists are used in music players, round-robin schedulers, and games where looping through items repeatedly is needed. Linear linked lists are used in simple queues and stacks where a clear start and end exist.

💼 Career

Understanding linked list types is fundamental for software developers working on data structures, memory management, and system design. It helps in choosing the right structure for efficient data traversal and manipulation.

1

Create a linear linked list with three songs

Create a struct called Node with fields data string and next *Node. Then create three nodes named song1, song2, and song3 with data exactly "Song1", "Song2", and "Song3" respectively. Link them linearly so that song1.next = &song2 and song2.next = &song3. The last node song3.next should be nil.

DSA Go

// Define Node struct and create three nodes linked linearly
// Your code here

Hint

Start by defining the Node struct. Then create three nodes with the exact song names. Link them by setting the next pointers. The last node's next must be nil to mark the end.

2

Create a circular linked list with the same three songs

Create three new nodes named cSong1, cSong2, and cSong3 with data exactly "Song1", "Song2", and "Song3" respectively. Link them circularly so that cSong1.next = &cSong2, cSong2.next = &cSong3, and cSong3.next = &cSong1.

DSA Go

package main

import "fmt"

type Node struct {
	data string
	next *Node
}

func main() {
	song1 := Node{data: "Song1"}
	song2 := Node{data: "Song2"}
	song3 := Node{data: "Song3"}

	song1.next = &song2
	song2.next = &song3
	song3.next = nil

// Create circular linked list nodes and link them
// Your code here
}

Hint

Create three new nodes for the circular list. Link the last node's next back to the first node to form a loop.

3

Write functions to print linear and circular linked lists

Write a function printLinear that takes a pointer to Node and prints each node's data followed by " -> ", ending with "nil". Write another function printCircular that takes a pointer to Node and prints each node's data followed by " -> ", stopping after printing the first node again to avoid infinite loop.

DSA Go

package main

import "fmt"

type Node struct {
	data string
	next *Node
}

func main() {
	song1 := Node{data: "Song1"}
	song2 := Node{data: "Song2"}
	song3 := Node{data: "Song3"}

	song1.next = &song2
	song2.next = &song3
	song3.next = nil

	cSong1 := Node{data: "Song1"}
	cSong2 := Node{data: "Song2"}
	cSong3 := Node{data: "Song3"}

	cSong1.next = &cSong2
	cSong2.next = &cSong3
	cSong3.next = &cSong1

// Define printLinear and printCircular functions below
// Your code here
}

Hint

Use a loop to print nodes for the linear list until nil. For the circular list, print nodes until you reach the starting node again to avoid infinite printing.

4

Print both linked lists to see the difference

Call printLinear with the address of song1 to print the linear linked list. Then call printCircular with the address of cSong1 to print the circular linked list.

DSA Go

package main

import "fmt"

type Node struct {
	data string
	next *Node
}

func printLinear(head *Node) {
	current := head
	for current != nil {
		fmt.Print(current.data, " -> ")
		current = current.next
	}
	fmt.Println("nil")
}

func printCircular(head *Node) {
	if head == nil {
		return
	}
	current := head
	for {
		fmt.Print(current.data, " -> ")
		current = current.next
		if current == head {
			break
		}
	}
	fmt.Println("(back to start)")
}

func main() {
	song1 := Node{data: "Song1"}
	song2 := Node{data: "Song2"}
	song3 := Node{data: "Song3"}

	song1.next = &song2
	song2.next = &song3
	song3.next = nil

	cSong1 := Node{data: "Song1"}
	cSong2 := Node{data: "Song2"}
	cSong3 := Node{data: "Song3"}

	cSong1.next = &cSong2
	cSong2.next = &cSong3
	cSong3.next = &cSong1

// Call printLinear and printCircular functions below
// Your code here
}

Hint

Call printLinear(&song1) to print the linear list and printCircular(&cSong1) to print the circular 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