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 see how the playlist behaves differently if it loops back to the start after the last song (circular) or just ends (linear).

🎯 Goal: You will create two linked lists: one linear and one circular. You will then print their elements to see the key difference in how they behave.

📋 What You'll Learn

Create a linear linked list with nodes containing values 1, 2, 3

Create a circular linked list with nodes containing values 1, 2, 3

Traverse and print the linear linked list nodes

Traverse and print the circular linked list nodes stopping after one full cycle

💡 Why This Matters

🌍 Real World

Circular linked lists are used in applications like music playlists, round-robin scheduling, and buffering where looping back to the start is needed.

💼 Career

Understanding linked list types helps in system programming, game development, and designing efficient data structures for real-time applications.

1

Create a linear linked list with nodes 1, 2, 3

Create a struct called Node with an int data and a Node* next. Then create three nodes with values 1, 2, and 3 linked linearly (last node's next is NULL). Store the head node in a variable called linear_head.

DSA C

#include 
#include 

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

int main() {
    // Create three nodes and link them linearly
    // Your code here
    return 0;
}

Hint

Remember to allocate memory for each node using malloc and link them by setting the next pointer.

2

Create a circular linked list with nodes 1, 2, 3

Using the same Node struct, create three nodes with values 1, 2, and 3 linked circularly (last node's next points back to the first node). Store the head node in a variable called circular_head.

DSA C

#include 
#include 

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

int main() {
    struct Node* linear_head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));

    linear_head->data = 1;
    linear_head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // Create circular linked list nodes and link them circularly
    // Your code here
    return 0;
}

Hint

Make sure the last node's next points back to the first node to form a circle.

3

Traverse and print the linear linked list

Use a struct Node* pointer called current to traverse the linear linked list starting from linear_head. Use a while loop that continues while current != NULL. Inside the loop, print the data of the current node followed by ->, then move current to the next node.

DSA C

#include 
#include 

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

int main() {
    struct Node* linear_head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));

    linear_head->data = 1;
    linear_head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    struct Node* circular_head = malloc(sizeof(struct Node));
    struct Node* c_second = malloc(sizeof(struct Node));
    struct Node* c_third = malloc(sizeof(struct Node));

    circular_head->data = 1;
    circular_head->next = c_second;

    c_second->data = 2;
    c_second->next = c_third;

    c_third->data = 3;
    c_third->next = circular_head;

    // Traverse and print linear linked list
    // Your code here
    return 0;
}

Hint

Use a while loop to go through each node until you reach NULL.

4

Traverse and print the circular linked list once

Use a struct Node* pointer called current to traverse the circular linked list starting from circular_head. Use a do-while loop to print the data of each node followed by ->. Stop the loop when current points back to circular_head after the first iteration. Finally, print (back to head) to show the circular link.

DSA C

#include 
#include 

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

int main() {
    struct Node* linear_head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));

    linear_head->data = 1;
    linear_head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    struct Node* circular_head = malloc(sizeof(struct Node));
    struct Node* c_second = malloc(sizeof(struct Node));
    struct Node* c_third = malloc(sizeof(struct Node));

    circular_head->data = 1;
    circular_head->next = c_second;

    c_second->data = 2;
    c_second->next = c_third;

    c_third->data = 3;
    c_third->next = circular_head;

    struct Node* current = linear_head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    // Traverse and print circular linked list once
    // Your code here
    return 0;
}

Hint

Use a do-while loop to ensure the circular list prints all nodes once and stops when it reaches the head again.

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