Doubly linked list

Doubly linked list is a complex type of linked list in which a node contains a pointer to the
previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node
consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer
to the previous node (previous pointer). A sample node in a doubly linked list is shown in the
figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is
shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. }

The prev part of the first node and the next part of the last node will always contain null
indicating end in each direction.
In a singly linked list, we could traverse only in one direction, because each node contains
address of the next node and it doesn't have any record of its previous nodes. However,
doubly linked list overcome this limitation of singly linked list. Due to the fact that, each
node of the list contains the address of its previous node, we can find all the details about the
previous node as well by using the previous address stored inside the previous part of each
node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image. Generally,
doubly linked list consumes more space for every node and therefore, causes more expansive
basic operations such as insertion and deletion. However, we can easily manipulate the
elements of the list since the list maintains pointers in both the directions (forward and
backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head
pointer points to the starting address 1. Since this is the first element being added to the list
therefore the prev of the list contains null. The next node of the list resides at address 4
therefore the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next
part.
Operations on doubly linked list

Node Creation

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. };
7. struct node *head;

All the remaining operations regarding doubly linked list are described in the following table.

SN Operation Description

1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.
3 Insertion after specified Adding the node into the linked list after the specified node.
node

4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node Removing the node which is present just after the node containing the
having given data given data.

7 Searching Comparing each node data with the item to be searched and return the
location of the item in the list if the item found else return null.

8 Traversing Visiting each node of the list at least once in order to perform some
specific operation like searching, sorting, display, etc.

INSERT FRONT
Inserting a new node in a doubly linked list is very similar to inserting new node in linked
list. There is a little extra work required to maintain the link of the previous node. A node
can be inserted in a Doubly Linked List in four ways:
• At the front of the DLL.
• In between two nodes
• After a given node.
• Before a given node.
• At the end of the DLL.
Add a node at the front in a Doubly Linked List:
The new node is always added before the head of the given Linked List. The task can be
performed by using the following 5 steps:
1. Firstly, allocate a new node (say new_node).
2. Now put the required data in the new node.
3. Make the next of new_node point to the current head of the doubly linked list.
4. Make the previous of the current head point to new_node.
5. Lastly, point head to new_node.
Illustration:
See the below illustration where E is being inserted at the beginning of the doubly linked
list.
Add a node in between two nodes:
It is further classified into the following two parts:
Add a node after a given node in a Doubly Linked List:
We are given a pointer to a node as prev_node, and the new node is inserted after the given
node. This can be done using the following 6 steps:
1. Firstly create a new node (say new_node).
2. Now insert the data in the new node.
3. Point the next of new_node to the next of prev_node.
4. Point the next of prev_node to new_node.
5. Point the previous of new_node to prev_node.
6. Change the pointer of the new node’s previous pointer to new_node.
Illustration:
See the below illustration where ‘E‘ is being inserted after ‘B‘.

Add a node at the end in a Doubly Linked List:

The new node is always added after the last node of the given Linked List. This can be
done using the following 7 steps:
1. Create a new node (say new_node).
2. Put the value in the new node.
3. Make the next pointer of new_node as null.
4. If the list is empty, make new_node as the head.
5. Otherwise, travel to the end of the linked list.
6. Now make the next pointer of last node point to new_node.
7. Change the previous pointer of new_node to the last node of the list.
Illustration:
See the below illustration where ‘D‘ is inserted at the end of the linked list.

Deletion at beginning

Deletion in doubly linked list at the beginning is the simplest operation. We just need to copy
the head pointer to pointer ptr and shift the head pointer to its next.
 1. Ptr = head;
2. head = head → next;

now make the prev of this new head node point to NULL. This will be done by using the
following statements.

1. head → prev = NULL

Now free the pointer ptr by using the free function.

1. free(ptr)

Algorithm

o STEP 1: IF HEAD = NULL

WRITE UNDERFLOWGOTO STEP 6
o STEP 2: SET PTR = HEAD
o STEP 3: SET HEAD = HEAD → NEXT
o STEP 4: SET HEAD → PREV = NULL
o STEP 5: FREE PTR
o STEP 6: EXIT

Deletion in doubly linked list at the end

Deletion of the last node in a doubly linked list needs traversing the list in order to reach the
last node of the list and then make pointer adjustments at that position.

In order to delete the last node of the list, we need to follow the following steps.

o If the list is already empty then the condition head == NULL will become true and
therefore the operation can not be carried on.
 o If there is only one node in the list then the condition head → next == NULL become
true. In this case, we just need to assign the head of the list to NULL and free head in
order to completely delete the list.
o Otherwise, just traverse the list to reach the last node of the list. This will be done by
using the following statements.

1. ptr = head;
2. if(ptr->next != NULL)
3. {
4. ptr = ptr -> next;
5. }
o The ptr would point to the last node of the ist at the end of the for loop. Just make the
next pointer of the previous node of ptr to NULL.

1. ptr → prev → next = NULL

free the pointer as this the node which is to be deleted.

1. free(ptr)
o Step 1: IF HEAD = NULL

Write UNDERFLOW
Go to Step 7
[END OF IF]

o Step 2: SET TEMP = HEAD

o Step 3: REPEAT STEP 4 WHILE TEMP->NEXT != NULL
o Step 4: SET TEMP = TEMP->NEXT

[END OF LOOP]

o Step 5: SET TEMP ->PREV-> NEXT = NULL

o Step 6: FREE TEMP
o Step 7: EXIT
Deletion in doubly linked list after the specified node

In order to delete the node after the specified data, we need to perform the following steps.

o Copy the head pointer into a temporary pointer temp.

1. temp = head
o Traverse the list until we find the desired data value.

1. while(temp -> data != val)

2. temp = temp -> next;
o Check if this is the last node of the list. If it is so then we can't perform deletion.

1. if(temp -> next == NULL)

2. {
3. return;
4. }
o Check if the node which is to be deleted, is the last node of the list, if it so then we
have to make the next pointer of this node point to null so that it can be the new last
node of the list.

1. if(temp -> next -> next == NULL)

2. {
3. temp ->next = NULL;
4. }
o Otherwise, make the pointer ptr point to the node which is to be deleted. Make the
next of temp point to the next of ptr. Make the previous of next node of ptr point to
temp. free the ptr.

1. ptr = temp -> next;

2. temp -> next = ptr -> next;
3. ptr -> next -> prev = temp;
 4. free(ptr);

Algorithm

o Step 1: IF HEAD = NULL

Write UNDERFLOW Go to Step 9 [END OF IF]

o Step 2: SET TEMP = HEAD

o Step 3: Repeat Step 4 while TEMP -> DATA != ITEM
o Step 4: SET TEMP = TEMP -> NEXT

[END OF LOOP]

o Step 5: SET PTR = TEMP -> NEXT

o Step 6: SET TEMP -> NEXT = PTR -> NEXT
o Step 7: SET PTR -> NEXT -> PREV = TEMP
o Step 8: FREE PTR
o Step 9: EXIT

// In the given program8 llink = prev rlink = next

8. Develop a menu driven Program in C for the following operations on Doubly Linked
List (DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
struct employee
{
char name[20];
char ssn[11];
char dept[5];
char desig[20];
long long int sal,phno;
struct employee *rlink,*llink;
};
typedef struct employee EMP;
EMP * createe();
EMP * insertnemp(EMP* head);
EMP * insertfront(EMP *head);
EMP * insertrear(EMP *head);
EMP * deletefront(EMP *head);
EMP * deleterear(EMP *head);
void display(EMP *head);
void main()
{
EMP *head=NULL;
int ch;
while(1)
{
printf("\nEnter the choice\n 1: create n employees\n 2: insert front\n 3: insert rear\n 4:
delete front\n 5: delete rear\n 6: display\n 7: exit\n");
scanf("%d", &ch);
switch(ch)
{
case 1: head = insertnemp(head); break;
case 2: head = insertfront(head); break;
case 3: head = insertrear(head); break;
case 4: head = deletefront(head); break;
case 5: head = deleterear(head); break;
case 6: display(head); break;
case 7: exit(0);
}
}
}
EMP *createe()
{
EMP *temp;
temp = (EMP *) malloc(sizeof(EMP));
printf("\nEnter the Name: ");
scanf("%s",temp->name);
fflush(stdin);
printf("\nEnter the SSN: ");
scanf("%s",temp->ssn);
fflush(stdin);
printf("\nEnter the Department: ");
scanf("%s",temp->dept);
fflush(stdin);
 printf("\nEnter the Designation: ");
gets(temp->desig);
fflush(stdin);
printf("\nEnter the Salary: ");
scanf("%ld",&temp->sal);
fflush(stdin);
printf("\nEnter the Phone Number: ");
scanf("%ld",&temp->phno);
fflush(stdin);
temp->rlink=NULL;
temp->llink=NULL;
return temp;
}
EMP * insertnemp(EMP *head)
{
int n,i;
printf("\nEnter number of employees: ");
scanf("%d",&n);
for(i=0;i<n;i++)
head = insertrear(head);
return head;
}
EMP * insertfront(EMP *head)
{
EMP *temp;
temp = createe();
if(head==NULL)
head=temp;
else
{
head->llink=temp;
temp->rlink=head;
head=temp;
}
return head;
}
EMP * insertrear(EMP *head)
{
EMP *temp,*pre;
temp = createe();
if(head==NULL)
head=temp;
else
{
pre=head;
while(pre->rlink!=NULL)
pre=pre->rlink;
pre->rlink=temp;
temp->llink=pre;
}
 return head;
}
EMP * deletefront(EMP *head)
{
struct EMP *pre;
pre=head;
if(pre==NULL)
printf("List is Empty\n");
else
{
head = head->rlink;
head->llink = NULL;
free(pre);
}
return head;
}
EMP * deleterear(EMP *head)
{
EMP *pre,*prev;
pre=head;
if(pre==NULL)
printf("List is Empty\n");
else if(pre->rlink==NULL)
head = NULL;
else
{
while(pre->rlink!=NULL)
{
prev=pre;
pre=pre->rlink;
}
prev->rlink=NULL;
}
free(pre);
return head;
}
void display(EMP *head)
{
EMP *pre;
int count=0;
pre=head;
if(pre==NULL)
printf("List is Empty\n");
else
{
printf(" Contents of the Linked List are\n");
printf("\n Name\tSSN\tDepartment\tDesignation\tSalary\tPhone Number\n");
while(pre!=NULL)
{
 printf("%8s\t%6s\t%5s\t%8s\t%ld\t%ld\n", pre->name,pre->ssn,pre->dept, pre-
>desig,pre->sal,pre->phno);
pre = pre->rlink;
count++;
}
}
printf("\nNumber of employees = %d\n",count);
}

OUTPUT
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
1

Enter the Name: aaaa

Enter the SSN: 1111

Enter the Branch: cs

Enter the Designation: Professor

Enter the Salary: 200000

Enter the Phone Number: 111111

Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
2

Enter the Name: bbbb

Enter the SSN: 2222

Enter the Branch: cs

Enter the Designation: Asst Prof

Enter the Salary: 100000

Enter the Phone Number: 222222

Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
1

Enter the Name: cccc

Enter the SSN: 3333

Enter the Branch: ec

Enter the Designation: Professor

Enter the Salary: 200000

Enter the Phone Number: 333333

Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
5
Contents of the Linked List are
Name SSN Branch Designation Salary Phone Number
cccc 3333 ec Professor 200000 333333
aaaa 1111 cs Professor 200000 111111
bbbb 2222 cs Asst Prof 100000 222222
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
3
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
5
Contents of the Linked List are
 Name SSN Branch Designation Salary Phone Number
aaaa 1111 cs Professor 200000 111111
bbbb 2222 cs Asst Prof 100000 222222
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
4
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
5
Contents of the Linked List are
Name SSN Branch Designation Salary Phone Number
aaaa 1111 cs Professor 200000 111111
Enter the choice
1: insert front
2: insert rear
3: delete front
4: delete rear
5: display
6: exit
6

Process returned 0 (0x0) execution time : 124.607 s

Press any key to continue.