# Doubly Linked List in C/C++

0
5

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