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

Circular vs Linear Linked List Key Difference

📖 Scenario: Imagine you are managing a playlist of songs. You want to understand how the playlist behaves differently if it loops back to the first song after the last one (circular) versus if it stops at the last song (linear).

🎯 Goal: You will create two linked lists: one linear and one circular. Then, you will see how traversing each list behaves differently.

📋 What You'll Learn

Create a linear linked list with three nodes containing values 10, 20, and 30

Create a circular linked list with three nodes containing values 10, 20, and 30

Traverse each list and collect the values to show the difference in traversal

Print the collected values for both lists

💡 Why This Matters

🌍 Real World

Circular linked lists are used in applications like music playlists, where the list loops continuously. Linear linked lists are used in simple queues or stacks where the end is a stopping point.

💼 Career

Understanding linked lists and their types is fundamental for software developers, especially when working with data structures, memory management, and algorithms.

1

Create a linear linked list with three nodes

Create a class called Node with an int data and a Node next property. Then create three nodes with values 10, 20, and 30. Link them linearly so that the last node's next is null.

DSA C#

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

Hint

Think of each node as a box holding a number and a pointer to the next box. For a linear list, the last box points to nothing (null).

2

Create a circular linked list with three nodes

Using the same Node class, create three new nodes with values 10, 20, and 30. Link them so that the last node's next points back to the first node, making the list circular.

DSA C#

// Create three new nodes for circular list and link last node to first
// Your code here

Hint

For a circular list, the last node points back to the first node, creating a loop.

3

Traverse both lists and collect their values

Traverse the linear list starting from node1 and collect the data values in a list called linearValues. Then traverse the circular list starting from cnode1 and collect the data values in a list called circularValues. For the circular list, stop after collecting three values to avoid infinite loop.

DSA C#

// Traverse linear list and collect values in linearValues
// Traverse circular list and collect values in circularValues
// Your code here

Hint

For the linear list, stop when current is null. For the circular list, stop after 3 nodes to avoid endless loop.

4

Print the collected values for both lists

Print the linearValues list and the circularValues list to show the difference in traversal.

DSA C#

// Print linearValues and circularValues
// Your code here

Hint

Use Console.WriteLine and string.Join to print the lists nicely.

Practice

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

easy

A. A linear linked list always has a fixed size.

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

C. A circular linked list cannot be traversed completely.

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

Solution

1. Step 1: Understand the structure of a circular linked list

   In a circular linked list, the last node's next pointer points back to the first node, creating a loop.

2. Step 2: Understand the structure of a linear linked list

   In a linear linked list, the last node's next pointer is null, so it does not loop back.

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:

   Circular list loops last node to first [OK]

Hint: Circular loops back; linear ends with null [OK]

Common Mistakes:

• Confusing which list loops back
• Thinking linear lists form a circle
• Believing circular lists cannot be fully traversed

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

easy

A. if (head.Next == head) { /* circular list */ }

B. if (head == null) { /* circular list */ }

C. if (head.Next == null) { /* linear list */ }

D. if (head.Next == tail) { /* circular list */ }

Solution

1. Step 1: Understand the pointer in a circular linked list

   In a circular linked list with one node, the node's next points to itself.

2. Step 2: Check the condition for circularity

   If head.Next == head, it means the list loops back to the start, confirming circularity.

3. Final Answer:

   if (head.Next == head) { /* circular list */ } -> Option A

4. Quick Check:

   Node points to itself means circular [OK]

Hint: Check if next points to head for circular [OK]

Common Mistakes:

• Checking null to detect circularity
• Confusing tail pointer with circular check
• Assuming head null means circular

3. Consider the following C# code for a circular linked list traversal:

Node current = head;
do {
    Console.Write(current.Data + " -> ");
    current = current.Next;
} while (current != head);
Console.WriteLine("null");

What will be the output if the list contains nodes with data 1, 2, 3 in that order?

medium

A. 1 -> 2 -> 3

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

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

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

Solution

1. Step 1: Understand the traversal condition

   The loop prints nodes until current equals head again, so it prints each node once.

2. Step 2: Trace the output for nodes 1, 2, 3

   It prints 1, then 2, then 3, then stops because current becomes head again.

3. Final Answer:

   1 -> 2 -> 3 -> Option A

4. Quick Check:

   Loop stops when current == head [OK]

Hint: Loop until back to head prints all nodes once [OK]

Common Mistakes:

• Thinking it loops infinitely
• Missing the stopping condition
• Assuming null is printed inside the loop

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

bool IsCircular(Node head) {
    Node temp = head;
    while (temp != null) {
        if (temp.Next == head) return true;
        temp = temp.Next;
    }
    return false;
}

What is the bug in this code?

medium

A. It does not handle empty lists (head == null).

B. It only detects circular lists where last node points to head, missing other loops.

C. It causes infinite loop for circular lists.

D. It incorrectly returns true for linear lists.

Solution

1. Step 1: Analyze the detection logic

   The code checks if any node's next points exactly to head to decide circularity.

2. Step 2: Identify limitation of this approach

   Some circular lists may loop back to a node other than head, so this code misses those cases.

3. Final Answer:

   It only detects circular lists where last node points to head, missing other loops. -> Option B

4. Quick Check:

   Only checks next == head misses other loops [OK]

Hint: Check all loops, not just next == head [OK]

Common Mistakes:

• Assuming all circular lists point last node to head
• Ignoring possibility of loops elsewhere
• Thinking code causes infinite loop

5. You have a circular linked list where the last node points back to the first node. You want to convert it into a linear linked list. Which of the following C# code snippets correctly performs this conversion?

hard

A. Node temp = head;
while (temp != null) {
temp = temp.Next;
}
temp.Next = null;

B. Node temp = head;
while (temp.Next != null) {
temp = temp.Next;
}
temp.Next = head;

C. Node temp = head;
while (temp.Next != head) {
temp = temp.Next;
}
temp.Next = null;

D. head = null;

Solution

1. Step 1: Locate the last node in the circular list

   Traverse nodes until you find the node whose next points back to head.

2. Step 2: Break the circular link

   Set that node's next pointer to null to make the list linear.

3. Final Answer:

   Node temp = head; while (temp.Next != head) { temp = temp.Next; } temp.Next = null; -> Option C

4. Quick Check:

   Find last node pointing to head, then set next to null [OK]

Hint: Find node pointing to head, set next to null [OK]

Common Mistakes:

• Setting head to null removes entire list
• Looping until next is null in circular list causes infinite loop
• Setting next to head instead of null