Circular Linked List with C++ Implementation

Circular Singly Linked List is a form of Singly Linked List and is connected in circular form. The last node has the link to the first node to form the circle. So, It is possible to traverse the circular list starting from any node. However, reversing the list is not simple.

See Circular Doubly Linked List for bidirectional communication.

1. Representation

• Node: A node consists of the data element and the pointer to the Next node
• Element: The actual data
• Next: Pointer to the next node
• Last: Pointer to the last node of the linked list. This is required to perform the insert operation at the front in O(1) time. The Head pointer is not required since the last node contains the pointer to the head node.
• Circular: Note the last node points to the first node and forms the circle.

Applications

• Circular Singly Linked List is useful for applications that require circular / loop operations.
• Music Player can use to play the songs in a loop.
• Round Robin CPU scheduling is another application that uses Circular Linked List.
• Multi-player gaming applications can use a circular list to keep the players.

2. Insertion on Circular Linked List

An element can be inserted into the linked list in any of the following three methods.

1. InsertFront – at the beginning of the List
2. InsertBack – at the end of the List
3. InsertAfter – after the specific Node

2.1. Insert Front

In a circular list, the last node is connected to the first node. So, we Insert the new node after the last node which is considered the front node.

Algorithm

1. Create the new node
2. Check if the list is empty. If true, make the new node the last and point itself to form the one-node circle.
3. Connect the new node at the front.

Code

Node* CircularList::insert_front(int element)
{
    // Step 1. Create the new node
    Node* new_node = new Node();
    new_node->element = element;

    // Step 2. Check if the list is empty. If true, make the new node
    // as last and point itself to form the one node circle.
    if (last == NULL) {
        new_node->next = new_node;
        last = new_node;
        return new_node;
    }
    
    // Step 3. Connect the new node at front.
    // The last->next is the front node of circular linked list
    new_node->next = last->next;
    last->next = new_node;
    
    return new_node;
}

2.2. Insert Back

This is similar to Insert Front where we Insert the new node after the last node. In addition, change the “Last” pointer to the new node so that it is on the backside.

Algorithm

1. Create the new node
2. Check if the list is empty. If true, make the new node the last and point itself to form the one-node circle.
3. Link the new node after the last node
4. Make the new node the last node

Code

Node* CircularList::insert_back(int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;
    
    // Step 2. Check if the list is empty. If true, make the new node
    // as last and point itself to form the one node circle.
    if (last == NULL) {
        new_node->next = new_node;
        last = new_node;
        return new_node;
    }
    
    // Step 3. Link the new node after the last node
    new_node->next = last->next;
    last->next = new_node;

    // Step 4. Make the new node as last node
    last = new_node;
    
    return new_node;
}

2.3. Insert After

Here, we Insert the new node (20) after the specific node (10).

Algorithm

1. Create the new node
2. Link the new node after the given node

Code

Node* CircularList::insert_after(Node* prev, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node after the given node
    new_node->next = prev->next;
    prev->next = new_node;

    return new_node;
}

3. Deletion on Circular Linked List

An element can be deleted from the circular linked list in any of the following methods.

1. Delete Front – Delete from the beginning of the List
2. Delete After – Delete after the specific node
3. Remove – Search the specific element and remove the node

3.1. Delete Front

Link the last node (30) directly with the second node (20), so that the first node (10) can be removed from the list.

Algorithm

1. Check if the list is empty. If true, return.
2. Check if the list has only a single node. If true, delete the node, reset the last to NULL, and return.
3. Otherwise, store the reference to the front node as the target.
4. Disconnect the front node by directly connecting the last node and the next node.
5. Delete the target node

Code

Node* CircularList::delete_front()
{
    // Step 1. Check if the list is empty. If true, return.
    if (last == NULL) {
        return NULL;
    }

    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the last to NULL, and return.
    if (last->next == last) {
        delete last;
        last = NULL;
        return NULL;
    }

    // Step 3. Otherwise, store the reference to front node as target
    Node* target = last->next;
    
    // Step 4. Disconnect the front node by directly connecting the last node and the next node.
    last->next = last->next->next;
    
    // Step 5. Delete the target node
    delete target;

    return last->next;
}

3.2. Delete After

Delete a node after the node (20). Disconnect the target node (30) by directly linking its previous and next node. In this case, both the previous and next nodes are the same.

Algorithm

1. Initialize the target with the reference to the target node
2. Check if the list has only a single node and return if true because the delete after is not applicable.
3. Disconnect the target node by directly linking its previous and next node.
4. Check if the target node is the last node. If true, move the last pointer to the previous node.
5. Delete the target node.

Code

bool CircularList::delete_after(Node* prev)
{
    // Step 1. Initialize target with the reference to the target node
    Node* target = prev->next;

    // Step 2. Check if the list has only a single node and return if true
    // because the delete after is not applicable.
    if (prev == target) {
        return false;
    }

    // Step 3. Disconnect the target node by directly linking its
    // previous and next node.
    prev->next = target->next;

    // Step 4. Check if the target node is the last node. If true,
    // move the last pointer to the previous node
    if (target == last) {
        last = prev;
    }

    // Step 4. Delete the target node
    delete target;

    return true;
}

3.3. Remove

Remove the node by the specific element (20). Traverse the list to search the given element and delete the node. This can take O(n) time to search the element.

Algorithm

1. Check if the list is empty and return if true.
2. Check if the list contains a only node. If true, check if the element matches and delete the node.
3. Otherwise, Iterate the linked list from start to end, and search if the element is found.
4. If found, set the node as the target node and disconnect it by directly linking its previous and next node.
5. Check if the target node is the last node. If true, move the last pointer to the previous node.
6. Delete the target node.

Code

bool CircularList::remove(int element)
{
    // Step 1. Check if the list is empty and return if true.
    if (last == NULL) {
        return false;
    }

    // Step 2. Check if the list contains only node
    if (last == last->next) {
        if (last->element == element) {
            delete last;
            last = NULL;
            return true;
        }
        return false;
    }

    // Step 3. Iterate the linked list from start to end,
    // and search if the element is found.
    for (Node* node = last; node->next != last; node = node->next) {

        if (node->next->element == element) {
            // Step 4. If found, set the node as target node and disconnect
            // it by directly linking its previous and next node.
            Node* target = node->next;
            node->next = node->next->next;

            // Step 5. Check if the target node is the last node. If true,
            // move the last pointer to the previous node
            if (target == last) {
                last = node;
            }

            // Step 6. Delete the target node
            delete target;
            return true;
        }
    }

    return false;
}

4. Search on Circular Linked List

The list is traversed from start to end to search for an element in the Linked List. The last node of the circular list always points to the Head. This must be checked to identify the end of the list.

Algorithm

1. Check if the list is empty
2. Iterate the linked list from start to end and search element
3. Return the node if found, NULL otherwise.

Code

Node* CircularList::search(int element)
{
    // Check if the list is empty
    if (last == NULL) {
        return NULL;
    }

    // Iterate the linked list from start to end and search element
    Node* node = last->next;
    do {
        if (node->element == element) {
            return node; // Found element
        }
        node = node->next;
    } while (node != last->next);

    return NULL; // Not found
}

5. The Complete Example in C++

/**
 * C++ example to demonstrate the circular linked list
 */
#include <iostream>
using namespace std;

// Linked list node representation
struct Node
{
    int element;
    Node* next;
};

/**
 * Circular linked list implementation
 */
class CircularList
{
    // The last node of the list
    // The last->next contains the address of head node
    Node* last;

public:
    // Constructor
    CircularList() : last(NULL) {}

    // Insert an element in front of the list
    // Returns the new node inserted
    Node* insert_front(int element);

    // Insert an element at the end of the list
    // Returns the new node inserted
    Node* insert_back(int element);

    // Insert an element after the given node
    // Returns the new node inserted
    Node* insert_after(Node* prev, int element);
    
    // Delete the front element
    // Returns the next node if available, NULL otherwise.
    Node* delete_front();
    
    // Delete the node after the given node
    // Returns true on success, false otherwise.
    bool delete_after(Node* prev);

    // Search and delete the given element
    // Returns true on success, false otherwise.
    bool remove(int element);
    
    // Search an element from the list
    // Returns the matching node if found, NULL otherwise.
    Node* search(int element);
    
    // Traverse the list and print the elements
    void traverse(const std::string& msg);
};

Node* CircularList::insert_front(int element)
{
    // Step 1. Create the new node
    Node* new_node = new Node();
    new_node->element = element;

    // Step 2. Check if the list is empty. If true, make the new node
    // as last and point itself to form the one node circle.
    if (last == NULL) {
        new_node->next = new_node;
        last = new_node;
        return new_node;
    }
    
    // Step 3. Connect the new node at front.
    // The last->next is the front node of circular linked list
    new_node->next = last->next;
    last->next = new_node;
    
    return new_node;
}

Node* CircularList::insert_back(int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;
    
    // Step 2. Check if the list is empty. If true, make the new node
    // as last and point itself to form the one node circle.
    if (last == NULL) {
        new_node->next = new_node;
        last = new_node;
        return new_node;
    }
    
    // Step 3. Link the new node after the last node
    new_node->next = last->next;
    last->next = new_node;

    // Step 4. Make the new node as last node
    last = new_node;
    
    return new_node;
}

Node* CircularList::insert_after(Node* prev, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node after the given node
    new_node->next = prev->next;
    prev->next = new_node;

    return new_node;
}

Node* CircularList::delete_front()
{
    // Step 1. Check if the list is empty. If true, return.
    if (last == NULL) {
        return NULL;
    }

    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the last to NULL, and return.
    if (last->next == last) {
        delete last;
        last = NULL;
        return NULL;
    }

    // Step 3. Otherwise, store the reference to front node as target
    Node* target = last->next;
    
    // Step 4. Disconnect the front node by directly connecting the last node and the next node.
    last->next = last->next->next;
    
    // Step 5. Delete the target node
    delete target;

    return last->next;
}

bool CircularList::delete_after(Node* prev)
{
    // Step 1. Initialize target with the reference to the target node
    Node* target = prev->next;

    // Step 2. Check if the list has only a single node and return if true
    // because the delete after is not applicable.
    if (prev == target) {
        return false;
    }

    // Step 3. Disconnect the target node by directly linking its
    // previous and next node.
    prev->next = target->next;

    // Step 4. Check if the target node is the last node. If true,
    // move the last pointer to the previous node
    if (target == last) {
        last = prev;
    }

    // Step 4. Delete the target node
    delete target;

    return true;
}

bool CircularList::remove(int element)
{
    // Step 1. Check if the list is empty and return if true.
    if (last == NULL) {
        return false;
    }

    // Step 2. Check if the list contains only node
    if (last == last->next) {
        if (last->element == element) {
            delete last;
            last = NULL;
            return true;
        }
        return false;
    }
    
    // Step 3. Iterate the linked list from start to end,
    // and search if the element is found.
    for (Node* node = last; node->next != last; node = node->next) {
        
        if (node->next->element == element) {
            // Step 4. If found, set the node as target node and disconnect
            // it by directly linking its previous and next node.
            Node* target = node->next;
            node->next = node->next->next;
            
            // Step 5. Check if the target node is the last node. If true,
            // move the last pointer to the previous node
            if (target == last) {
                last = node;
            }

            // Step 6. Delete the target node
            delete target;
            return true;
        }
    }
    
    return false;
}

Node* CircularList::search(int element)
{
    // Check if the list is empty
    if (last == NULL) {
        return NULL;
    }

    // Iterate the linked list from start to end and search element
    Node* node = last->next;
    do {
        if (node->element == element) {
            return node; // Found element
        }
        node = node->next;
    } while (node != last->next);

    return NULL; // Not found
}

// Traverse and print the linked list
void CircularList::traverse(const std::string& msg)
{
    cout << msg << endl;
    if (last == NULL ) {
        cout << "NULL" << endl << endl;
        return;
    }
    
    // Iterate the linked list from start to end
    Node* node = last->next;
    do {
        cout << " --> " << node->element ;
        node = node->next;
    } while (node != last->next);
    cout << " --> " << endl << endl;
}

int main()
{
    // Create a linked list
    CircularList list;
    list.traverse("initial list");

    // Insert elements
    Node* node_10 = list.insert_front(10);
    list.traverse("insert_front(10)");

    list.insert_back(30);
    list.traverse("insert_back(30)");

    list.insert_after(node_10, 20);
    list.traverse("insert_after(node_10, 20)");
    
    // Search an element
    Node* node_20 = list.search(20);
    cout << "search(20) matches node " << node_20->element << endl << endl;

    // Delete elements
    list.delete_front();
    list.traverse("delete_front()");
    
    list.delete_after(node_20);
    list.traverse("delete_after(node_20)");
    
    list.remove(20);
    list.traverse("remove(20)");
}

Output

initial list
NULL

insert_front(10)
 --> 10 --> 

insert_back(30)
 --> 10 --> 30 --> 

insert_after(node_10, 20)
 --> 10 --> 20 --> 30 --> 

search(20) matches node 20

delete_front()
 --> 20 --> 30 --> 

delete_after(node_20)
 --> 20 --> 

remove(20)
NULL