Doubly Linked List in C/C++

0
99

Doubly Linked List as an abstract data type

Creating a Node struct

A doubly linked list is similar to simple linked list, the main difference is that a doubly linked list node has one extra pointer pointing to previous node.

struct Node{
    struct Node *prev;
    int data;
    struct Node *next;
}*first=NULL;

Initialising first node and other nodes using an array

void create(int A[],int n){
    struct Node *t,*last;
    int i;
    first = (struct Node*)malloc(sizeof(struct Node));
    first -> data=A[0];
    first->next=first->prev=NULL;
    last=first;
    for(i=1;i<n;i++){
        t=(struct Node*)malloc(sizeof(struct Node));
        t->data=A[i];
        t->next=last->next;
        t->prev=last;
        last->next=t;
        last=t;
}

}

Displaying all the nodes in the doubly linked list

void display(struct Node *p){
    while (p!=NULL)
    {
        printf("%d",p->data);
        p=p->next;
    }
    
}

Length of the doubly linked list

int Length(struct Node *p){
    int count=0;
    while(p!=NULL){
        count++;
        p=p->next;
    }
    return count;
}

Inserting a node in the doubly linked list

void insert(struct Node *p, int key, int pos){
    struct Node *t=(struct Node*)malloc(sizeof(struct Node));
    int i;
    if(pos<0 || pos>Length(p)) return;
    if(pos==0){

        t->prev=NULL;
        t->data=key;
        t->next=first;
        first=t;

    }
    else{
        for(i=0;i<pos-1;i++){
            p=p->next;
            }
            t->data=key;
            t->prev=p;
            t->next=p->next;
            if(p->next)
            p->next->prev=t;
            p->next=t;
            
        }
}

Deleting a node from doubly linked list

int delete(struct Node *p, int pos){
    int x=-1,i;
    if(pos<1 && pos>Length(p)){
        return -1;
    }
     if(pos==1){
            first=p->next;
            free(p);
            if(first)first->prev=NULL;;


        }
        else{
            for(i=0;i<pos-1;i++){
                p=p->next;
            }
            x=p->data;
            p->prev->next = p->next;
           if(p->next) p->next->prev = p->prev;
            free(p); 

        }
        return x;
    
}

Reversing a doubly linked list

void Reverse(struct Node *p){
    struct Node *t;
    while(p){
        t=p->next;
        p->next=p->prev;
        p->prev=t;
        p=p->prev;
        if(p && p->next==NULL){
            first=p;
        }
    }
}
SHARE
Previous articleLinked List In C/C++
Next articleCircular Linked List
Hey! I am one of the 100,000 engineering students in India, with a step forward to support and provide resources to 99,999 other students.

LEAVE A REPLY