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;
}
}
}