Circular Doubly linked List Operation – Data Structures in C Program

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

struct node{
    int data;
    struct node* rlink, *llink;
};

typedef struct node* NODE;

NODE createNode(){
    NODE temp = (NODE)malloc(sizeof(struct node));
    temp->llink = NULL;
    temp->rlink = NULL;
    printf("Enter Data>> ");
    scanf("%d",&temp->data);
    return temp;
}

void display(NODE head){
    if (head->data==0){
        printf("List Empty\n");
        return;
    }
    NODE temp = head->rlink;
    for(int i=0;i<head->data;i++){
        printf("%d  ",temp->data);
        temp = temp->rlink;
    }
}

NODE insAtFront(NODE head){
    NODE newNode = createNode();
    newNode->rlink = head->rlink;
    newNode->llink = head;
    head->rlink->llink = newNode;
    head->rlink = newNode;
    head->data++;
    return head;
}

NODE insAtEnd(NODE head){
    NODE newNode = createNode();
    newNode->rlink = head;
    newNode->llink = head->llink;
    head->llink->rlink = newNode;
    head->llink = newNode;
    head->data++;
    return head;
}

NODE insAtPos(NODE head){
    int pos;
    printf("Enter Position to insert>> ");
    scanf("%d",&pos);
    if (pos<1||pos>head->data+1){
        printf("Invalid Position\n");
        return head;
    }
    if (pos==1) return insAtFront(head);
    else if (pos==head->data+1) return insAtEnd(head);
    NODE temp = head->rlink;
    for(int i=0;i<pos-1;i++){
        temp = temp->rlink;
    }
    NODE newNode = createNode();
    newNode->rlink = temp;
    newNode->llink = temp->llink;
    temp->llink->rlink = newNode;
    temp->llink = newNode;
    head->data++;
    return head;
}

void search(NODE head){
    int key;
    if (head->data==0){
        printf("List Empty\n");
        return;
    }
    printf("Enter key>> ");
    scanf("%d",&key);
    NODE temp = head->rlink;
    for(int i=0;i<head->data;i++){
        if (temp->data==key){
            printf("Key FOUND\n");
            return;
        }
        temp = temp->rlink;
    }
    printf("Key Not Found\n");
}

NODE delAtFront(NODE head){
    if (head->data==0){
        printf("List Empty\n");
        return head;
    }
    NODE temp = head->rlink;
    head->rlink = temp->rlink;
    temp->rlink->llink = head;
    free(temp);
    head->data--;
    return head;
}

NODE delAtEnd(NODE head){
    if (head->data==0){
        printf("List Empty\n");
        return head;
    }
    NODE temp = head->llink;
    head->llink = temp->llink;
    temp->llink->rlink = head;
    head->data--;
    return head;
}

NODE delAtPos(NODE head){
    if (head->data==0){
        printf("List Empty\n");
        return head;
    }
    int pos;
    printf("Enter Position to insert>> ");
    scanf("%d",&pos);
    if (pos<1||pos>head->data){
        printf("Invalid Position\n");
        return head;
    }
    NODE temp = head->rlink;
    for(int i=0; i<pos-1;i++){
        temp=temp->rlink;
    }
    temp->rlink->llink = temp->llink;
    temp->llink->rlink = temp->rlink;
    free(temp);
    head->data--;
    return head; 
}

NODE reverse(NODE head){
    if (head->data<2){
        return head;
    }
    NODE t = head->rlink;
    NODE temp, cur=NULL, ptr;
    for(int i=0;i<head->data;i++){
        temp = t;
        t = t->rlink;
        temp->rlink = cur;
        if(cur==NULL){
            ptr = temp;
        }
        cur = temp;
        cur->llink = t;
    }
    head->llink = ptr;
    head->rlink = cur;
    cur->llink = head;
    ptr->rlink = head;
    return head;
}

NODE orderedInput(NODE head){
    int i;
    if (head->data==0) return insAtFront(head);
    NODE newNode = createNode();
    NODE temp = head->rlink;
    for(i=0;i<head->data&&(newNode->data)>(temp->data);i++){
        temp = temp->rlink;
    }
    newNode->rlink = temp;
    newNode->llink = temp->llink;
    temp->llink->rlink = newNode;
    temp->llink = newNode;
    head->data++;
    return head;    
}


void main(){
    int choice;
    NODE head = (NODE)malloc(sizeof(struct node));
    head->llink = head->rlink = head;
    head->data = 0; //to store the number of nodes present
    while(1){
        printf("\n----Circular Doubly Linked List Operations----\n");
        printf("1.Display\n2.Insert at Front\n3.Insert at Position\n4.Insert at End\n5.Search\n6.Delete at Front\n7.Delete at Position\n8.Delete At End\n9.Reverse\n10.Ordered Input\n11.Copylist\n");
        printf("Select Option>> ");
        scanf("%d",&choice);
        switch(choice){
            case 1: display(head); break;
            case 2: head = insAtFront(head); break;
            case 3: head = insAtPos(head); break;
            case 4: head = insAtEnd(head); break;
            case 5: search(head); break;
            case 6: head = delAtFront(head); break;
            case 7: head = delAtPos(head); break;
            case 8: head = delAtEnd(head); break;
            case 9: head = reverse(head);break;
            case 10: head = orderedInput(head);break;
            //case 11: copyAndDisplay(head);break;
            
        }     
    }
}