In this tutorial, we are going to learn the Linked List Types and their implementation.

There is additional pointer to the previous node so we can go in both directions i.e. forward and backward.

Node Representation:

``````
struct node
{
int data;
struct node *pre, *next;
}
``````

### Operations on Doubly Linked List

• Insert
• Insert At Start
• Insert At End
• Insert By Position
• Insert By Data
• Delete
• Delete At Start
• Delete At End
• Delete By Position
• Delete By Data
• Traverse/Display : Traversing means visiting every node of the linked list at once.

#### Insert Operation:

##### Insert At Start:

We are using two pointer

1. Starting pointer(st) (also called head) and
2. End pointer(end) (point to end node of doubly linked list)
• Allocate memory for new node using malloc()
• Store data in the node
• If starting pointer is null(i.e. Linked List is empty) then point starting pointer to new node
• If Linked List is not null then point new node of next pointer to starting pointer, pre of starting pointer to new node and starting pointer to new node like mentioned in code below.
``````void insert_at_start()
{
struct node *new;
new=(node *)malloc(sizeof(struct node));

if(new==NULL)  //error while allocating memory using malloc
{
printf("\nError:\nOverflow\n\n");
return 0;
}

printf("\nEnter Data:  ");
scanf("%d",&new->data);

if(st==NULL) //st is starting pointer
{
st=new;
end=new;
new->pre=NULL;
new->nxt=NULL;
}
else
{
new->pre=NULL;
new->nxt=st;
st->pre=new;
st=new;
}
}``````
##### Insert At End:

This operation is similar to insert at start operation because we have used two pointers st (point at start) and end(point at end) pointer.

``````void insert_at_end()
{
struct node *new;
new=(node *)malloc(sizeof(struct node));

if(new==NULL)  //error while allocating memory using malloc
{
printf("\nError:\nOverflow\n\n");
return 0;
}

printf("\nEnter Data:  ");
scanf("%d",&new->data);

if(st==NULL)
{
st=new;
end=new;
new->pre=NULL;
new->nxt=NULL;
}
else
{
end->nxt=new;
new->nxt=NULL;
new->pre=end;
end=new;
}
}``````
##### Insert By Data
``````void insert_by_data()
{
struct node *new;
new=(node *)malloc(sizeof(struct node));

if(new==NULL)  //error while allocating memory using malloc
{
printf("\nError:\nOverflow\n\n");
return 0;
}

int data;
printf("\nEnter data at which you want to insert:");
scanf("%d",&data);

if(st==NULL)
{
printf("\nLisked List is empty.\n");
return 0;
}

if(st->data==data)  // if data found at start of DLL
{
insert_at_start();
return 0;
}

t=st;

while(t->data!=data && t!=NULL)
{
t=t->nxt;
}
if(t->data==data)  // if match found in DLL
{

printf("\nEnter Data to insert:  ");
scanf("%d",new->data);

new->nxt=t;
new->pre=t->pre;
t->pre->nxt=new;
t->pre=new;
}
else
}
``````
##### Insert At Location
``````void insert_at_location()
{
struct node *new,*t;

int loc,counter=1,temp;

printf("\nEnter Location at which you want to insert new data:");
scanf("%d",&loc);

t=st;

if(loc==1)   //if location is 1 then insert data at 1st position
{
insert_at_start();
return 0;
}

new=(struct node *)malloc(sizeof(struct node));

if(new==NULL)
{
printf("\nOverflow\n");
return 0;
}

while(counter!=loc && t->nxt!=NULL)
{
counter++;
t=t->nxt;
}

if(counter==loc) //if location found
{
printf("\nEnter Data to insert:  ");
scanf("%d",&new->data);

new->nxt=t;
new->pre=t->pre;
t->pre->nxt=new;
t->pre=new;
}
else
}

``````

#### Delete Operation

##### Delete At Start
• Store first node in a temporary struct node pointer
• If there is only one node in Doubly Linked List, then make st and end pointer to null and free the node.
• If there are more than 1 nodes in DLL(Doubly Linked List) then point the start pointer to next of start pointer and make pre of starting pointer NULL.
• Free the temporary node.
``````void delete_at_start()
{

if(st==NULL)
{
printf("\n\nError:\nUnderflow\n");
return 0;
}

struct node *t;

t=st;
if(st->nxt==NULL)
{
printf("\nDeleted Data : ",t->data);

st=NULL;
end=NULL;
free(t);
}
else
{
printf("\nDeleted Data : ",t->data);

st=st->nxt;
st->pre=NULL;
free(t);
}
}``````
##### Delete At End

Its similar to delete at start operation. Check the code below.

``````void delete_at_end()
{

if(st==NULL)
{
printf("\n\nError:\nUnderflow\n");
return 0;
}

struct node *t;
t=end;
if(st->nxt==NULL)
{
printf("\nDeleted Data : ",t->data);

st=NULL;
end=NULL;
free(t);
}
else
{
printf("\nDeleted Data : ",t->data);

end=end->pre;
end->nxt=NULL;
free(t);
}
}

``````
##### Delete By Data

Procedure is same like we used in insert by data operation. First find the data from the linked list and then perform delete operation as mentioned below.

``````void delete_by_data()
{

if(st==NULL)
{
printf("\n\nError:\nUnderflow\n");
return 0;
}

struct node *t,*temp;
t=st;

int data;
printf("\nEnter data at which you want to Delete:");
scanf("%d",&data);

if(st->data==data)
{
delete_at_start();
return 0;
}

while(t->data!=data && t->nxt!=NULL)
{
t=t->nxt;
}
temp=t;
t=st;

while(t->nxt!=NULL)
{
t=t->nxt;
}
if(t->data == data)  // if data is present in the last node
{
delete_at_end();
return 0;
}
if(temp->data == data)
{
printf("\nDeleted Data : ",t->data);

t->pre->nxt = t->nxt;
t->nxt->pre = t->pre;
}
else

}
``````
##### Delete At Location
``````void delete_at_location()
{

if(st==NULL)
{
printf("\n\nError:\nUnderflow\n");
return 0;
}

struct node *t;
t=st;

int loc,counter=1,temp;
printf("\nEnter Location:");
scanf("%d",&loc);

if(loc==1)
{
delete_at_start();
return 0;
}

while(counter!=loc && t->nxt!=NULL)
{
counter++;
t=t->nxt;
}
temp=counter;
counter=1;
t=st;
while(t->nxt!=NULL)
{
counter++;
t=t->nxt;
}
if(counter==loc)
{

delete_at_end();
return 0;
}
if(temp==loc)
{
printf("\nDeleted Data : ",t->data);

t->pre->nxt = t->nxt;
t->nxt->pre = t->pre;
}
else
}

``````

#### Traverse/Display

• If Doubly Linked List is empty then print/return DLL is empty.
• Visit from start to end of the linked list and print the data.
``````void display()
{
if(st==NULL)
{
return 0;
}

struct node *t;

t=st;
while(t!=NULL)
{
printf("%d: Data\n",i,t->data);
i++;
t=t->nxt;
}
}

//Task: display data from end of the DLL to start of the Doubly Linked  List.``````

For singly Circular linked list, the `next` pointer of last node points to the first node i.e head(or starting pointer).
In the doubly circular linked list, `prev` pointer of the first node points to the last node and `next` pointer of last node points to the first node.