Circular vs Linear Linked List Key Difference in DSA C - Why the Distinction Matters

The Big Idea

Discover how linking the end back to the start can save you from endless manual restarts!

The Scenario

Imagine you have a list of friends' phone numbers written on paper. You want to call each friend one by one. If you reach the last friend, you stop and have to start over from the first friend manually every time.

The Problem

Manually restarting from the first friend after reaching the last one is slow and easy to forget. You might lose track or repeat calls. This is like a linear list where you must remember to go back to the start.

The Solution

A circular linked list connects the last friend back to the first friend automatically. This way, you can keep calling friends in a loop without stopping or restarting manually.

Before vs After

✗ Before

struct Node {
    int data;
    struct Node* next;
};
// Last node points to NULL
last->next = NULL;

✓ After

struct Node {
    int data;
    struct Node* next;
};
// Last node points back to head
last->next = head;

What It Enables

It enables continuous looping through the list without manual resets, perfect for tasks needing repeated cycles.

Real Life Example

Think of a music playlist that repeats songs endlessly. Circular linked lists help manage this repeating cycle smoothly.

Key Takeaways

Linear lists end with NULL, circular lists loop back to start.

Circular lists allow endless traversal without stopping.

Choosing between them depends on whether you need to repeat the list automatically.

Practice

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

easy

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

B. In a circular linked list, nodes are stored in an array.

C. A linear linked list has no nodes.

D. A linear linked list always has exactly two nodes.

Solution

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

   A linear linked list has nodes connected one after another, and the last node points to null, ending the list.

2. Step 2: Understand the structure of a 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 A

4. Quick Check:

   Circular linked list loops back = In a circular linked list, the last node points back to the first node, forming a circle. [OK]

Hint: Circular lists loop back to start; linear lists end with null [OK]

Common Mistakes:

• Thinking circular lists use arrays
• Believing linear lists have no nodes
• Confusing last node pointers

2. Which of the following is the correct way to check if a circular linked list has reached back to the start node in C?

easy

A. if (current->next == NULL) { /* end */ }

B. if (current->next == head) { /* back to start */ }

C. if (current == NULL) { /* end */ }

D. if (current == head) { /* back to start */ }

Solution

1. Step 1: Understand circular linked list traversal

   In a circular linked list, traversal starts from head and continues until the current pointer returns to head, completing the loop.

2. Step 2: Identify the correct condition to detect reaching start

   if (current == head) checks if we have reached back to the start node after full traversal.

3. Final Answer:

   if (current == head) { /* back to start */ } -> Option D

4. Quick Check:

   current == head = reached back to start [OK]

Hint: Check if current == head to detect back to start [OK]

Common Mistakes:

• Using NULL to detect end in circular list
• Checking current->next == head (detects last node)
• Confusing current and current->next

3. Consider the following C code for traversing a circular linked list starting at head:

struct Node {
  int data;
  struct Node* next;
};

void printList(struct Node* head) {
  struct Node* temp = head;
  if (head != NULL) {
    do {
      printf("%d -> ", temp->data);
      temp = temp->next;
    } while (temp != head);
  }
  printf("NULL\n");
}

If the list has nodes with data 1, 2, 3 linked circularly, what is the output?

medium

A. 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> NULL

B. NULL

C. 1 -> 2 -> 3 -> NULL

D. 1 -> 2 -> 3

Solution

1. Step 1: Understand the traversal loop

   The do-while loop prints the current node's data, then moves to next node, repeating until it reaches back to head.

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

   It prints 1, then 2, then 3, then stops because temp == head again, then prints NULL.

3. Final Answer:

   1 -> 2 -> 3 -> NULL -> Option C

4. Quick Check:

   Prints all nodes once, then NULL [OK]

Hint: do-while prints all nodes once in circular list [OK]

Common Mistakes:

• Expecting infinite loop output
• Missing NULL at end
• Confusing do-while with while loop

4. The following code attempts to traverse a circular linked list but causes an infinite loop. What is the error?

void traverse(struct Node* head) {
  struct Node* temp = head;
  while (temp != NULL) {
    printf("%d -> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\n");
}

medium

A. The printf statement is missing a newline.

B. The loop condition should check if temp equals head, not NULL.

C. The code should use a for loop instead of while.

D. The temp pointer is not initialized.

Solution

1. Step 1: Analyze the loop condition for circular list

   In a circular linked list, temp never becomes NULL because last node points back to head, so while(temp != NULL) never ends.

2. Step 2: Correct the loop condition to stop at head

   We should stop when temp reaches head again to avoid infinite loop.

3. Final Answer:

   The loop condition should check if temp equals head, not NULL. -> Option B

4. Quick Check:

   Stop at head, not NULL, in circular list [OK]

Hint: In circular lists, stop when back at head, not NULL [OK]

Common Mistakes:

• Using NULL to end circular list traversal
• Ignoring infinite loop possibility
• Not initializing temp properly

5. You want to convert a linear linked list into a circular linked list in C. Which code snippet correctly achieves this assuming head is the start node and the list is non-empty?

struct Node* temp = head;
while (temp->next != NULL) {
  temp = temp->next;
}
// What next?

medium

A. temp->next = head; // link last node to head to form circle

B. head = NULL; // reset head to null

C. temp = NULL; // set temp to null to end list

D. temp->next = NULL; // keep list linear

Solution

1. Step 1: Find the last node in the linear list

   The while loop moves temp to the last node where next is NULL.

2. Step 2: Link last node's next to head to form circular list

   Setting temp->next = head connects the last node back to the first node, making the list circular.

3. Final Answer:

   temp->next = head; // link last node to head to form circle -> Option A

4. Quick Check:

   Last node points to head to make circle [OK]

Hint: Link last node's next to head to make circular [OK]

Common Mistakes:

• Setting head to NULL mistakenly
• Leaving last node's next as NULL
• Setting temp to NULL instead of linking