Circular Linked list | Introduction and Basic Operations

05 min read

A circular linked list is a linear linked list that may be a singly linked list or doubly linked list. There is no NULL reference to the end of the list. In fact in the list every node points to the next node and last node points to the first(head) node, thus forming a circle.

Circular linked lists can be implemented using both singly linked list and doubly linked list.

 

Singly Circular Linked Lists

singly circular linked list

Representation

/* Structure for node in Circular Singly Linked Lists */
struct node { 
    int data; 
    struct node* next; // Pointer to next node 
};

 

 

Doubly Circular Linked Lists

doubly circular linked list

Representation

/* Structure for node in Circular Doubly Linked Lists */
struct node { 
    int data; 
    struct node* next; // Pointer to next node 
    struct node* prev; // Pointer to previous node
};

 

Advantages of Circular Linked Lists

  • Traversal can begin from any node in the list. When the started node is visited again, the list is meant to complete one cycle.
  • Used in Queue data structure implementation.
  • Circular Doubly Linked Lists are used for implementation of Fibonacci Heaps.

 

Basic Operations in Circular Linked lists

The following basic operations can be done in both singly and doubly circular linked lists.

  • Insertion − Inserts an element at specified positions in the list.
  • Deletion − Deletes the specified element from the list.
  • Search − Searches an element using the given value.
  • Update − Update an element in the list with the given value.
  • Reverse − Reverses the entire Linked list. 
  • Traverse  −  Displays all the elements in the linked list.

 

Applications of Circular Linked Lists

  • Circular Linked Lists can be used in any application where the entries appear in a circular manner.
  • Circular Linked Lists is the basic idea for the round robin scheduling algorithm.
  • Circular Linked Lists are used majorly in time-sharing applications where the operating system maintains a list of current users and must alternately allow each user to use a small amount of CPU time (one user at a time). The operating system will pick a user, allow him/her use a small amount of CPU time and then move to the next user.
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error