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

Circular vs Linear Linked List Key Difference

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

🎯 Goal: You will create two linked lists in C++: one linear and one circular. You will see how the last song points differently in each list, showing the key difference between linear and circular linked lists.

📋 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

Show how the last node points to nullptr in the linear list

Show how the last node points back to the first node in the circular list

Print the values of both lists to demonstrate their structure

💡 Why This Matters

🌍 Real World

Circular linked lists are used in music playlists, round-robin scheduling, 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 helps in software development roles involving data structure design, memory management, and algorithm optimization.

1

Create a linear linked list with three nodes

Create a struct called Node with an int data and a Node* next. Then create three nodes named node1, node2, and node3 with values 10, 20, and 30 respectively. Link them linearly so that node1.next points to node2, node2.next points to node3, and node3.next is nullptr.

DSA C++

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

Hint

Remember to define the Node struct first, then create nodes with the given values and link them one after another. The last node's next should be nullptr.

2

Create a circular linked list with three nodes

Using the same Node struct, create three new nodes named cnode1, cnode2, and cnode3 with values 10, 20, and 30 respectively. Link them so that cnode1.next points to cnode2, cnode2.next points to cnode3, and cnode3.next points back to cnode1 to form a circle.

DSA C++

#include 

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

int main() {
    Node node1{10, nullptr};
    Node node2{20, nullptr};
    Node node3{30, nullptr};

    node1.next = &node2;
    node2.next = &node3;
    node3.next = nullptr;

    // Create circular linked list nodes
    // Your code here

    return 0;
}

Hint

Link the circular nodes so the last node points back to the first node, making a loop.

3

Write functions to print linear and circular linked lists

Write a function printLinearList that takes a Node* and prints the data values until it reaches nullptr. Also write a function printCircularList that takes a Node* and prints the data values until it loops back to the starting node. Use these functions to print node1 and cnode1.

DSA C++

#include 

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

// Write printLinearList and printCircularList functions here

int main() {
    Node node1{10, nullptr};
    Node node2{20, nullptr};
    Node node3{30, nullptr};

    node1.next = &node2;
    node2.next = &node3;
    node3.next = nullptr;

    Node cnode1{10, nullptr};
    Node cnode2{20, nullptr};
    Node cnode3{30, nullptr};

    cnode1.next = &cnode2;
    cnode2.next = &cnode3;
    cnode3.next = &cnode1;

    // Call print functions for both lists
    // Your code here

    return 0;
}

Hint

Use a while loop for the linear list until nullptr. Use a do-while loop for the circular list to stop when you reach the starting node again.

4

Print the lists to show the key difference

Run the program to print the linear linked list starting from node1 and the circular linked list starting from cnode1. The output should show the linear list ending with null and the circular list looping back to the start.

DSA C++

#include 

// Full code from previous step

// Run the program to see output
// Your code here

Hint

Check the console output carefully. The linear list ends with null, and the circular list ends by looping back to the start.

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, while in a linear linked list, the last node points to null.

B. A circular linked list stores data in a circle shape, while a linear linked list stores data in a straight line.

C. Circular linked lists can only store numbers, while linear linked lists can store any data type.

D. Linear linked lists have nodes connected randomly, while circular linked lists have nodes connected sequentially.

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, indicating the end.

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, forming a circle with no null end.

3. Final Answer:

   In a circular linked list, the last node points back to the first node, while in a linear linked list, the last node points to null. -> Option A

4. Quick Check:

   Last node points to first node = circular linked list [OK]

Hint: Last node points to null in linear, to head in circular [OK]

Common Mistakes:

• Thinking circular lists store data in a circle shape physically
• Confusing data types allowed in each list
• Assuming linear lists have random connections

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

easy

A. while (head != nullptr) head = head->next; return true;

B. if (head->next == nullptr) return true;

C. if (head == nullptr) return false;

D. Node* temp = head; while (temp != nullptr && temp->next != head) temp = temp->next; return (temp != nullptr && temp->next == head);

Solution

1. Step 1: Understand the logic to detect circular linked list

   We traverse nodes until we find a node whose next points back to head or reach null.

2. Step 2: Analyze the given code snippets

   Node* temp = head; while (temp != nullptr && temp->next != head) temp = temp->next; return (temp != nullptr && temp->next == head); correctly traverses nodes and checks if the next pointer points to head, indicating circularity.

3. Final Answer:

   Node* temp = head; while (temp != nullptr && temp->next != head) temp = temp->next; return (temp != nullptr && temp->next == head); -> Option D

4. Quick Check:

   Traverse until next points to head = circular check [OK]

Hint: Traverse until next points to head to confirm circular [OK]

Common Mistakes:

• Checking only if head is null
• Assuming next == nullptr means circular
• Infinite loop by not checking null condition

3. What will be the output of the following C++ code snippet?

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

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = head; // circular link

Node* temp = head;
int count = 0;
while (temp != nullptr && count < 4) {
  std::cout << temp->data << " ";
  temp = temp->next;
  count++;
}

medium

A. 1 2 1 2

B. 1 2 3 4

C. 1 2

D. 1 2 1 2 1

Solution

1. Step 1: Understand the linked list structure

   Node 1 points to Node 2, and Node 2 points back to Node 1, making it circular.

2. Step 2: Trace the loop output

   The loop prints data 4 times: 1, 2, 1, 2, then stops because count reaches 4.

3. Final Answer:

   1 2 1 2 -> Option A

4. Quick Check:

   Print 4 nodes in circular list = 1 2 1 2 [OK]

Hint: Count limits output in circular list traversal [OK]

Common Mistakes:

• Assuming next nullptr ends loop
• Expecting 3 or 4 as data values
• Not limiting loop count causing infinite print

4. Identify the error in the following code that attempts to create a circular linked list:

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

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = nullptr; // supposed to be circular

medium

A. The head node should not be initialized with nullptr.

B. The last node's next pointer should point to head, not nullptr.

C. The data values 10 and 20 are invalid for circular lists.

D. The Node struct is missing a previous pointer.

Solution

1. Step 1: Review the code's intention

   The code tries to create a circular linked list but sets the last node's next to nullptr.

2. Step 2: Identify the correct pointer for circular list

   In a circular linked list, the last node's next must point back to the head node, not nullptr.

3. Final Answer:

   The last node's next pointer should point to head, not nullptr. -> Option B

4. Quick Check:

   Last node next = head for circular list [OK]

Hint: Last node next must link to head in circular list [OK]

Common Mistakes:

• Leaving last node next as nullptr
• Confusing circular with doubly linked list
• Thinking data values affect circularity

5. You have a circular linked list where each node contains an integer. Write a C++ function to count the number of nodes in the list without using extra memory. What is the key difference in traversal compared to a linear linked list?

hard

A. Traverse until the current node is null.

B. Traverse until the current node's next is null.

C. Traverse until the current node returns to the head node.

D. Traverse until a fixed number of nodes is reached.

Solution

1. Step 1: Understand traversal in linear linked list

   In a linear linked list, traversal stops when the current node is null (end of list).

2. Step 2: Understand traversal in circular linked list

   In a circular linked list, traversal stops when the current node comes back to the head node, completing the circle.

3. Final Answer:

   Traverse until the current node returns to the head node. -> Option C

4. Quick Check:

   Stop when node loops back to head in circular list [OK]

Hint: Stop traversal when node equals head in circular list [OK]

Common Mistakes:

• Stopping traversal at null in circular list
• Using fixed count without knowing list size
• Confusing next pointer null check with circular condition