Circular Doubly Linked List (CDLL) Introduction and Program

Circular Doubly Linked List(सर्कुलर डबली लिंक्ड लिस्ट ) :- 

It is similar to Doubly Linked List but In the circular doubly linked list the next part of last node of the list contains the address of the first node and the back part of first node of the list contains the address of the last node and forms a circular chain which travels backward and forward direction in list.

यह डबली लिंक्ड लिस्ट के समान ही होती है परन्तु सर्कुलर डबली लिंक्ड लिस्ट में लास्ट नोड के नेक्स्ट पार्ट पर फर्स्ट नोड का एड्रेस एवं फर्स्ट नोड के बैक पार्ट पर लास्ट नोड का एड्रेस रखा जाता है जिससे एक सर्कुलर चैन बनती है जिसमे फॉरवर्ड एवं बैकवर्ड ट्रेवर्सिंग की जा सकती है।  

CDLL Program:-

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int info;
    struct node *next;
    struct node *back;
};
typedef struct node n;

n* create_node(int);
void add_node();
void insert_at_first();
void insert_at_end();
void insert_at_position();
void delete_node_position();
void sort_list();
void update();
void search();
void display_from_beg();
void display_in_rev();

n *new, *ptr, *back;
n *first = NULL, *last = NULL;
int number = 0;

void main()
{
    int ch;

    printf("\n linked list\n");
    printf("1.insert at beginning \n 2.insert at end\n 3.insert at position\n4.sort linked list\n 5.delete node at position\n 6.updatenodeinfoue\n7.search element \n8.displaylist from beginning\n9.display list from end\n10.exit ");

    while (1)
    {

        printf("\n enter your choice:");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1 :
            insert_at_first();
            break;
        case 2 :
            insert_at_end();
            break;
        case 3 :
            insert_at_position();
            break;
        case 4 :
            sort_list();
            break;
        case 5 :
            delete_node_position();
            break;
        case 6 :
            update();
            break;
        case 7 :
            search();
            break;
        case 8 :
            display_from_beg();
            break;
        case 9 :
            display_in_rev();
            break;
        case 10 :
            exit(0);
        case 11 :
            add_node();
            break;
        default:
            printf("\nininfoid choice");            
        }
    }
}
/*
 *MEMORY ALLOCATED FOR NODE DYNAMICALLY
 */
n* create_node(int info)
{
    number++;
    new = (n *)malloc(sizeof(n));
    new->info = info;
    new->next = NULL;
    new->back = NULL;
    return new;
}
/*
 *ADDS NEW NODE
 */
void add_node()
{

    int info;

    printf("\nenter the infoue you would like to add:");
    scanf("%d", &info);
    new = create_node(info);

    if (first == last && first == NULL)
    {

        first = last = new;
        first->next = last->next = NULL;
        first->back = last->back = NULL;
    }
    else
    {
        last->next = new;
        new->back = last;
        last = new;
        last->next = first;
        first->back = last;
    }
}
/*
 *INSERTS ELEMENT AT FIRST
 */
void insert_at_first()
{

    int info;

    printf("\nenter the infoue to be inserted at first:");
    scanf("%d",&info);
    new = create_node(info);

    if (first == last && first == NULL)
    {
        printf("\ninitially it is empty linked list later insertion is done");
        first = last = new;
        first->next = last->next = NULL;
        first->back = last->back = NULL;
    }
    else
    {
        new->next = first;
        first->back = new;
        first = new;
        first->back = last;
        last->next = first;
        printf("\n the infoue is inserted at begining");
    }
}
/*
 *INSERTS ELEMNET AT END
 */
void insert_at_end()
{

    int info;

    printf("\nenter the infoue that has to be inserted at last:");
    scanf("%d", &info);
    new = create_node(info);

    if (first == last && first == NULL)
    {
        printf("\ninitially the list is empty and now new node is inserted but at first");
        first = last = new;
        first->next = last->next = NULL;
        first->back = last->back = NULL;
    }
    else
    {
        last->next = new;
        new->back = last;
        last = new;
        first->back = last;
        last->next = first;
    }
}
/*
 *INSERTS THE ELEMENT AT GIVEN POSITION
 */
void insert_at_position()
{
    int info, pos, len = 0, i;
    n *backnode;

    printf("\n enter the infoue that you would like to insert:");
    scanf("%d", &info);
    printf("\n enter the position where you have to enter:");
    scanf("%d", &pos);
    new = create_node(info);

    if (first == last && first == NULL)
    {
        if (pos == 1)
        {
            first = last = new;
            first->next = last->next = NULL;
            first->back = last->back = NULL;
        }
        else
            printf("\n empty linked list you cant insert at that particular position");
    }
    else
    {
        if (number < pos)
            printf("\n node cant be inserted as position is exceeding the linkedlist length");

        else
        {
            for (ptr = first, i = 1;i <= number;i++)
            {
                backnode = ptr;
                ptr = ptr->next;
                if (i == pos-1)
                {
                    backnode->next = new;
                    new->back = backnode;
                    new->next = ptr;
                    ptr->back = new;
                    printf("\ninserted at position %d succesfully", pos);
                    break;
                }
            }
        }
    }
}
/*
 *SORTING IS DONE OF ONLY NUMBERS NOT LINKS
 */
void sort_list()
{
    n *temp;
    int tempinfo, i, j;

    if (first == last && first == NULL)
        printf("\nlinked list is empty no elements to sort");
    else
    {
        for (ptr = first,i = 0;i < number;ptr = ptr->next,i++)
        {
            for (temp = ptr->next,j=i;j<number;j++)
            {
                if (ptr->info > temp->info)
                {
                    tempinfo = ptr->info;
                    ptr->info = temp->info;
                    temp->info = tempinfo;
                }
            }
        }
        for (ptr = first, i = 0;i < number;ptr = ptr->next,i++)
            printf("\n%d", ptr->info);
    }
}
/*
 *DELETION IS DONE
 */
void delete_node_position()
{
    int pos, count = 0, i;
    n *temp, *backnode;

    printf("\n enter the position which u wanted to delete:");
    scanf("%d", &pos);

    if (first == last && first == NULL)
        printf("\n empty linked list you cant delete");

    else
    {
        if (number < pos)
            printf("\n node cant be deleted at position as it is exceeding the linkedlist length");

        else
        {
            for (ptr = first,i = 1;i <= number;i++)
            {
                backnode = ptr;
                ptr = ptr->next;
                if (pos == 1)
                {
                    number--;
                    last->next = backnode->next;
                    ptr->back = backnode->back;
                    first = ptr;
                    printf("%d is deleted", backnode->info);
                    free(backnode);
                    break;    
                }
                else if (i == pos - 1)
                {
                    number--;
                    backnode->next = ptr->next;
                    ptr->next->back = backnode;
                    printf("%d is deleted", ptr->info);
                    free(ptr);
                    break;
                }
            }
        }
    }
}
/*
 *UPDATION IS DONE FRO GIVEN OLD info
 */
void update()
{
    int oldinfo, newinfo, i, f = 0;
    printf("\n enter the infoue old infoue:");
    scanf("%d", &oldinfo);
    printf("\n enter the infoue new infoue:");
    scanf("%d", &newinfo);
    if (first == last && first == NULL)
        printf("\n list is empty no elemnts for updation");
    else
    {
        for (ptr = first, i = 0;i < number;ptr = ptr->next,i++)
        {
            if (ptr->info == oldinfo)
            {
                ptr->info = newinfo;
                printf("infoue is updated to %d", ptr->info);
                f = 1;
            }
        }
        if (f == 0)
            printf("\n no such old infoue to be get updated");
    }
}
/*
 *SEARCHING USING SINGLE KEY
 */
void search()
{
    int count = 0, key, i, f = 0;

    printf("\nenter the infoue to be searched:");
    scanf("%d", &key);

    if (first == last && first == NULL)
        printf("\nlist is empty no elemnets in list to search");
    else
    {
        for (ptr = first,i = 0;i < number;i++,ptr = ptr->next)
        {
            count++;
            if (ptr->info == key)
            {
                printf("\n the infoue is found at position at %d", count);
                f = 1;
            }
        }
        if (f == 0)
            printf("\n the infoue is not found in linkedlist");
    }
}
/*
 *DISPLAYING IN BEGINNING
 */
void display_from_beg()
{
    int i;
    if (first == last && first == NULL)
        printf("\nlist is empty no elemnts to print");
    else
    {
        printf("\n%d number of nodes are there", number);
        for (ptr = first, i = 0;i < number;i++,ptr = ptr->next)
            printf("\n %d", ptr->info);
    }
}
/*
 * DISPLAYING IN REVERSE
 */
void display_in_rev()
{
    int i;    
    if (first == last && first == NULL)
        printf("\nlist is empty there are no elments");
    else
    {
        for (ptr = last, i = 0;i < number;i++,ptr = ptr->back)
        {
            printf("\n%d", ptr->info);
        }
    }
}