Circular Linked Lists

Circular Linked Lists

A circular linked list is a variation of a linked list in which the last node points back to the first node, creating a circular structure. This type of linked list can be singly or doubly linked. In this lesson, we will explore the structure of circular linked lists, their advantages, and how to implement them in C++.

Structure of Circular Linked Lists

In a circular linked list, each node contains two parts: data and a pointer (or reference) to the next node. The last node's pointer points back to the first node, rather than pointing to null as in a standard linked list. This creates a loop in the list.

Here is a simple structure for a node in a circular linked list:

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

Types of Circular Linked Lists

Singly Circular Linked List

In a singly circular linked list, each node points to the next node in the sequence. The last node's next pointer points to the first node. Below is an example of a singly circular linked list with three nodes:

Node* head = new Node();
head->data = 1;
Node* second = new Node();
second->data = 2;
Node* third = new Node();
third->data = 3;
head->next = second;
second->next = third;
third->next = head; // points back to head

Doubly Circular Linked List

A doubly circular linked list has nodes that contain two pointers: one pointing to the next node and one pointing to the previous node. This allows traversal in both directions. The last node’s next pointer points to the first node, and the first node’s previous pointer points to the last node.

struct Node {
    int data;
    Node* next;
    Node* prev;
};
Node* head = new Node();
head->data = 1;
Node* second = new Node();
second->data = 2;
Node* third = new Node();
third->data = 3;
head->next = second;
second->next = third;
third->next = head;
head->prev = third;
third->prev = second;
second->prev = head;

Advantages of Circular Linked Lists

• Continuous traversal: You can traverse the list from any node without needing to reset to the head.
• Efficient use of memory: There is no need for a null pointer in the last node, which can save memory in certain applications.
• Useful for applications: Circular linked lists are often used in applications like round-robin scheduling, where each process is given an equal share of the CPU time.

Implementing a Circular Linked List in C++

Let’s implement a basic circular linked list in C++. We will create functions to insert nodes and display the list.

Node Structure

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

Class Definition

class CircularLinkedList {
private:
    Node* head;
public:
    CircularLinkedList();
    void insert(int data);
    void display();
};

Constructor

The constructor initializes the head pointer to null.

CircularLinkedList::CircularLinkedList() {
    head = nullptr;
}

Insert Function

The insert function adds a new node to the circular linked list. If the list is empty, the new node becomes the head. Otherwise, we traverse to the last node and insert the new node.

void CircularLinkedList::insert(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    if (head == nullptr) {
        head = newNode;
        newNode->next = head;
    } else {
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }
}

Display Function

The display function prints all the elements in the circular linked list. It starts from the head and traverses until it reaches the head again.

void CircularLinkedList::display() {
    if (head == nullptr) return;
    Node* temp = head;
    do {
        std::cout << temp->data << " ";
        temp = temp->next;
    } while (temp != head);
}

Example of Using Circular Linked List

Now, let us see how to use the CircularLinkedList class.

int main() {
    CircularLinkedList cll;
    cll.insert(1);
    cll.insert(2);
    cll.insert(3);
    cll.display();
    return 0;
}

Common Mistakes

Complexity of Circular Linked Lists

The time complexity for insertion and display operations in a circular linked list is O(n), where n is the number of nodes. This is because you may need to traverse the entire list to find the correct position for insertion or to display all nodes.

Summary

• A circular linked list connects the last node back to the first node.
• It can be singly or doubly linked.
• Advantages include continuous traversal and efficient memory use.
• Insertion and display operations have a time complexity of O(n).

Check your understanding

1. What is the main difference between a singly linked list and a circular linked list?
2. How do you insert a new node into a circular linked list?
3. What are some advantages of using a circular linked list?
4. What is the time complexity of the display operation in a circular linked list?