Circular linked list

In a circular linked list, the address field of last node contains the address of the first node i.e. last and first nodes are adjacent to each other. Thus the linked list is made circular by linking start and end nodes. There are two types of circular linked list:

  • Singly circular Linked List
  • Doubly circular Linked List

Singly Circular Linked List

The following diagram demonstrates a singly circular linked list.
cll_inserted

Implementation

/*
 * Node Declaration
 */
struct node
{
    int info;
    struct node *next;
}*last;
/*
 * Class Declaration
 */
class circular_llist
{
    public:
        void create_node(int value);
        void add_begin(int value);
        void add_after(int value, int position);
        void delete_element(int value);
        void search_element(int value);
        void display_list();
        circular_llist()
        {
            last = NULL;           
        }
};
/*
 * Create Circular Link List
 */
void circular_llist::create_node(int value)
{
    struct node *temp;
    temp = new(struct node);
    temp->info = value;
    if (last == NULL)
    {
        last = temp;
        temp->next = last;   
    }
    else
    {
        temp->next = last->next; 
        last->next = temp;
        last = temp;
    }
}
/*
 * Insertion of element at beginning 
 */
void circular_llist::add_begin(int value)
{
    if (last == NULL)
    {
        cout<<"First Create the list."<<endl;        
        return;     
    }     
    struct node *temp;     
    temp = new(struct node);     
    temp->info = value;
    temp->next = last->next;
    last->next = temp;
}
/*
 * Insertion of element at a particular place 
 */
void circular_llist::add_after(int value, int pos)
{
    if (last == NULL)
    {
        cout<<"First Create the list."<<endl;        
        return;     
    }  
    struct node *temp, *s;
    s = last->next;
    for (int i = 0;i < pos-1;i++) 
    {     
        s = s->next;
        if (s == last->next)
        {
            cout<<"There are less than ";
            cout<<pos<<" in the list"<<endl;      
            return;       
        }
     }
    temp = new(struct node);
    temp->next = s->next;
    temp->info = value;
    s->next = temp;
    /*Element inserted at the end*/
    if (s == last)
    { 
        last=temp;
    }
}

/*
 * Deletion of element from the list
 */
void circular_llist::delete_element(int value)
{
    struct node *temp, *s;
    s = last->next;
      /* If List has only one element*/
    if (last->next == last && last->info == value)  
    {
        temp = last;
        last = NULL;
        free(temp);
        return;
    }
    if (s->info == value)  /*First Element Deletion*/
    {
        temp = s;
        last->next = s->next;
        free(temp);
        return;
    }
    while (s->next != last)
    {
        /*Deletion of Element in between*/
        if (s->next->info == value)    
        {
            temp = s->next;
            s->next = temp->next;
            free(temp);
            cout<<"Element "<<value;
            cout<<" deleted from the list"<<endl; 
            return; 
        } 
        s = s->next;
    }
    /*Deletion of last element*/
    if (s->next->info == value)    
    {
        temp = s->next;
        s->next = last->next;
        free(temp);		
        last = s;
        return;
    }
    cout<<"Element "<<value<<" not found in the list"<<endl; 
}

   /*  * Search element in the list   */
 void circular_llist::search_element(int value) 
{    
    struct node *s;     
    int counter = 0; 
    s = last->next;
    while (s != last)
    {
        counter++;
        if (s->info == value)    
        {
            cout<<"Element "<<value; 
            cout<<" found at position "<<counter<<endl;    
            return; 
        } 
        s = s->next;
    }
    if (s->info == value)    
    {
        counter++;             
        cout<<"Element "<<value;
        cout<<" found at position "<<counter<<endl;
        return;
    }
    cout<<"Element "<<value<<" not found in the list"<<endl;
}

/*
 * Display Circular Link List 
 */
void circular_llist::display_list()
{
    struct node *s;
    if (last == NULL)
    {
        cout<<"List is empty, nothing to display"<<endl; 
        return;
    }  
    s = last->next;
    cout<<"Circular Link List: "<<endl;
    while (s != last)
    {
        cout<info<<"->";
        s = s->next;
    }
    cout<info<<endl;
}
 
/*
 * Update Circular Link List 
 */
void circular_llist::update()
{
    int value, pos, i;
   if (last == NULL)
    {
        cout<<"List is empty, nothing to update"<<endl;
        return;
    }
    cout<<"Enter the node position to be updated: "; 
    cin>>pos;
    cout<<"Enter the new value: "; 
    cin>>value;
    struct node *s;
    s = last->next;
    for (i = 0;i < pos - 1;i++)
    {
        if (s == last)
        {
            cout<<"There are less than "<<pos<<" elements.";
            cout<<endl; 
            return;  
        } 
        s = s->next;
    }
    s->info = value;  
    cout<<"Node Updated"<<endl;
} 

Doubly Circular Linked List

The following diagram demonstrates a doubly circular linked list.
RDLLImplementation

/*
 * Node Declaration
 */
struct node
{
    int info;
    struct node *next;
    struct node *prev;
}*start, *last;
int counter = 0;
/*
 * Class Declaration
 */
class double_clist
{
    public:
        node *create_node(int);
        void insert_begin();
        void insert_last();
        void insert_pos();
        void delete_pos();
        void search();
        void update();
        void display();
        double_clist()
        {
            start = NULL;
            last = NULL;			
        }
};
/*
 *MEMORY ALLOCATED FOR NODE DYNAMICALLY
 */
node* double_clist::create_node(int value)
{
    counter++;  
    struct node *temp;
    temp = new(struct node);
    temp->info = value;
    temp->next = NULL;
    temp->prev = NULL;
    return temp;
}
/*
 *INSERTS ELEMENT AT BEGINNING
 */
void double_clist::insert_begin()
{
    int value;
    cout<<endl<<"Enter the element to be inserted: ";     cin>>value;
    struct node *temp;
    temp = create_node(value);
    if (start == last && start == NULL)
    {    
        cout<<"Element inserted in empty list"<<endl;         start = last = temp;         start->next = last->next = NULL;
        start->prev = last->prev = NULL;
    }
    else
    {
        temp->next = start;
        start->prev = temp;
        start = temp;
        start->prev = last;
        last->next = start;
        cout<<"Element inserted"<<endl;
    }
}
 
/*
 *INSERTS ELEMNET AT LAST
 */
void double_clist::insert_last()
{
    int value;    
    cout<<endl<<"Enter the element to be inserted: ";     cin>>value; 
    struct node *temp;
    temp = create_node(value);
    if (start == last && start == NULL)
    {
        cout<<"Element inserted in empty list"<<endl;         start = last = temp;         start->next = last->next = NULL;    
        start->prev = last->prev = NULL;
    }
    else
    {
        last->next = temp;
        temp->prev = last;
        last = temp;
        start->prev = last;
        last->next = start;
    }
}
/*
 *INSERTS ELEMENT AT POSITION
 */
void double_clist::insert_pos()
{    
    int value, pos, i;
    cout<<endl<<"Enter the element to be inserted: ";     cin>>value;
    cout<<endl<<"Enter the postion of element inserted: ";     cin>>pos;
    struct node *temp, *s, *ptr;
    temp = create_node(value);
    if (start == last && start == NULL)
    {
        if (pos == 1)
        {
            start = last = temp;
            start->next = last->next = NULL;    
            start->prev = last->prev = NULL;
        }
        else
        {
            cout<<"Position out of range"<<endl;
            counter--;
            return;
        }
    }  
    else
    {
        if (counter < pos)
        {
             cout<<"Position out of range"<<endl;
             counter--;
             return;   		
        }
        s = start;		
        for (i = 1;i <= counter;i++)         {             ptr = s;             s = s->next;
            if (i == pos - 1)
            {
                ptr->next = temp;
                temp->prev = ptr;
                temp->next = s;
                s->prev = temp;
                cout<<"Element inserted"<<endl;
                break;
            }
        }
    }
}

/*
 * Delete Node at Particular Position
 */
void double_clist::delete_pos()
{    
    int pos, i;
    node *ptr, *s;
    if (start == last && start == NULL)
    {
        cout<<"List is empty, nothing to delete"<<endl;
        return;
    }
    cout<<endl<<"Enter the postion of element to be deleted: ";     cin>>pos;
    if (counter < pos)
    {
        cout<<"Position out of range"<<endl;         return;     }     s = start;     if(pos == 1)     {         counter-;         last->next = s->next;
        s->next->prev = last;
        start = s->next;
        free(s);
        cout<<"Element Deleted"<<endl;
        return;	   
    }
    for (i = 0;i < pos - 1;i++ )     {           s = s->next;
        ptr = s->prev;    	  
    }    
    ptr->next = s->next;
    s->next->prev = ptr;
    if (pos == counter)
    {
        last = ptr; 	   
    }
    counter--;
    free(s);
    cout<<"Element Deleted"<<endl;
}
/*
 * Update value of a particular node 
 */
void double_clist::update()
{
    int value, i, pos;
    if (start == last && start == NULL)
    {
        cout<<"The List is empty, nothing to update"<<endl;
        return; 
    }
    cout<<endl<<"Enter the postion of node to be updated: ";     cin>>pos;
    cout<<"Enter the new value: ";     cin>>value;
    struct node *s;
    if (counter < pos)
    {
        cout<<"Position out of range"<<endl;         return;     }     s = start;       if (pos == 1)     {        s->info = value;
       cout<<"Node Updated"<<endl;
       return;   
    }
    for (i=0;i < pos - 1;i++)     {         s = s->next; 		 
    }
    s->info = value;
    cout<<"Node Updated"<<endl;
}
/*
 * Search Element in the list
 */
void double_clist::search()
{
    int pos = 0, value, i;
    bool flag = false;
    struct node *s;
    if (start == last && start == NULL)
    {
        cout<<"The List is empty, nothing to search"<<endl;
        return;
    }
    cout<<endl<<"Enter the value to be searched: ";     cin>>value;
    s = start;
    for (i = 0;i < counter;i++)     {         pos++;         if (s->info == value)
        {
            cout<<"Element "<<value<<" found at position: "<<pos<<endl;             flag = true;         }             s = s->next;
    }
    if (!flag)
        cout<<"Element not found in the list"<<endl;   
}
/*
 * Display Elements of the List 
 */
void double_clist::display()
{
    int i;
    struct node *s;
    if (start == last && start == NULL)
    {
        cout<<"The List is empty, nothing to display"<<endl;
        return;
    }
    s = start;
    for (i = 0;i < counter-1;i++)
    {	
        cout<info<<"";
        s = s->next; 
    }
    cout<info<<endl;
}