Array Vs Linked List

Array Linked list

An array is a collection of elements of a A linked list is a collection of objects known

similar data type. as a node where node consists of two parts,
i.e., data and address.
Array elements store in a contiguous memory Linked list elements can be stored anywhere
location. in the memory or randomly stored.

Array elements are independent of each other. Linked list elements are dependent on each
other. As each node contains the address of
the next node so to access the next node, we
need to access its previous node.
Array takes more time while performing any Linked list takes less time while performing
operation like insertion, deletion, etc. any operation like insertion, deletion, etc.
Accessing any element in an array is faster as Accessing an element in a linked list is
the element in an array can be directly slower as it starts traversing from the first
accessed through the index. element of the linked list.

Memory utilization is inefficient in the array. Memory utilization is efficient in the case of
For example, if the size of the array is 6, and a linked list as the memory can be allocated
array consists of 3 elements only then the rest or deallocated at the run time according to
of the space will be unused. our requirement.

Types of Linked Lists

Basically we can put linked lists into the following four items:
1. Singly Linked List
2. Circular Linked List
3. Doubly Linked List
4. Circular Doubly Linked List

Singly Linked List

Linked list is a collection of nodes or data elements logically connected to each other.
Whenever there is a need to add a new element to the list, a new node is created and
appended at the end of the list.
Representation of Singly Linked List
Linked list is a collection of data elements stored in such a manner that each element
points at the next element in the list. The elements of a linked list are also referred as
nodes. Each node has two parts: data and next. The data part contains the data element
while the next part contains the address of the next node. The next part of the last
node of the list contains a NULL value indicating the end of the list. The beginning of
the list is indicated with the help of a special pointer called head/ first/ start. Similarly,
the end of the list is indicated by a pointer called last/end.

LINKED LIST IMPLEMENTATION

The implementation of a linked list involves two tasks:

1. Declaring the list node
2. Defining the linked list operations
1. Linked List Node Declaration
Since a linked list node contains two parts, data and next, a structure construct is best
suited for it. The following structure declaration defines a link list node.

struct node
{
int data;
struct node *next;
};

The above structure declaration defines a new data type called node that represents a
linked list node. The node structure contains two members, data for storing integer
data values and next for storing address of the next node.
The statement, struct node *next, indicates that the pointer next points at same
structure type i.e. node.
2. Linked List Operations
The typical operations performed on a linked list are:
1. Insert
 2. Deletion
3. Search
4. Print
1. Insert: The insertion into a singly linked list can be performed at different
positions. Based on the position of the new node being inserted, the insertion is
categorized into the following categories.
1.1 Insertion at beginning
1.2 Insert at the end of the list
1.3 Insertion after specified node

1.1 Insert at beginning

The steps to insert a node at beginning is given below

 Allocate memory for new node.

 Store data.

 Change next of new node to point to head.

 Change head to point to recently created node

Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
ptr->next = head
head = ptr
Print"Node inserted"
EndIf
Stop
1.2 Insertion at end of the list
The steps to insert a node at beginning is given below

 Allocate memory for new node

 Store data

 Traverse to last node

 Change next of last node to recently created node

 Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
If(head = NULL) then
ptr -> next = NULL
head = ptr
Print “Node inserted”
Else
temp = head
While (temp -> next != NULL) do
temp = temp -> next
EndWhile
temp->next = ptr
ptr->next = NULL
Print “Node inserted”
EndIf
EndIf
Stop

1.3 Insertion after specified node-

 Allocate memory and store data for new node
  Traverse to node just before the required position of new node
 Store the address of next node(next to the new node) in the next part of
new node.
 Change next pointer of the previous node to hold the address of new node.

Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
Input loc
temp=head
For i=1 to loc-1 do
temp = temp->next
If(temp = NULL) then
Print "can't insert”
Return
EndIf
EndFor
ptr ->next = temp ->next
temp ->next = ptr
Print “Node inserted"
EndIf
Stop

2.Delete
The Deletion of a node from a singly linked list can be performed at different
positions. Based on the position of the node being deleted, the operation is
categorized into the following categories.

2.1 Delete at beginning

2.2 Deletion at the end of the list
2.3 Deletion specified node
2.1 Deletion at beginning
 Copy head to ptr
 Point head to the second node
 Free the memory pointed by ptr.

Algorithm

If (head = NULL) then

Print “Empty List”
Else
ptr= head
head= ptr -> next
ReturnNode(ptr)
Print “Node deleted from beginning”
Endif
Stop

2.2 Deletion at the end of the list

 Store second last node address in ptr1 and address of last node in
ptr
 Change next of ptr1 to NULL
 Free(ptr)
Algorithm
If (head= NULL) then
Print “Empty List”
Else
If(head->next=NULL) then
ReturnNode (head)
head=NULL
Print “Only node of the list deleted”
Else
ptr = head
While (ptr -> next!= NULL) do
ptr1 = ptr
ptr = ptr -> next
EndWhile
ptr1 -> next = NULL
ReturnNode (ptr)
Print “Deleted node from last”
EndIf
EndIf
Stop
2.3 Deletion specified node-
 Traverse till the node that need to be deleted. Such that at each
movement the address of the previous and current node is stored in
separate pointers.
  Change next pointer of the previous node (previous to the specified
node) to hold the address of next node of the specified node to
exclude the specified node from the chain.

Algorithm
Input location
ptr = head
For i = 1 to loc-1 do
ptr1 = ptr
ptr= ptr->next;
If(ptr= NULL) then
Print “Cant delete”
Return
EndIf
EndFor
ptr1->Next= ptr->next
ReturnNode(ptr)
Print "Deleted node",loc
Stop

3. Search
You can search an element on a linked list using a loop using the following steps. We
are finding item on a linked list.
  Copy head to temp, initialize flag =0 and i =1

 Run a loop until the temp is NULL because the last element points
to NULL.

 In each iteration, check if the key of the node is equal to item. If it

the key matches the item set the flag to 1 and break from the loop,
otherwise increase the i by 1 and move the temp to next node.

 After Iteration check the flag, if flag is 1- element found at i

otherwise element not found.

Linked List : 10 20 30 NULL

Key : 20

Diagram to search 20 is given below

Linked List : 10 20 30 NULL

Key : 100

Diagram for search not found is given below for the link list
Another Example is given below
Algorithm:
i=1
flag =0
temp = head
If (temp= NULL) then
` Print “List is Empty”
Else
Input item
While (temp != NULL) do
If (temp → data = item) then
print “Item found at location”,i
flag =1
Break
EndIf
i=i+1
temp= temp->next
EndWhile
If (flag=0) then
Print “Element not found”
EndIf
EndIf
Stop

4.Print

The print operation prints or displays the linked list elements on the screen. To print
the elements, the linked list is traversed from start till end using NEXT pointers.

Algorithm
ptr = head
If (ptr= NULL) then
Print “Nothing to print”
Else
Print "\nprinting values . . . . .”
While (ptr!= NULL) do
Print ptr→ data
ptr = ptr → next
EndWhile
EndIf
Stop

Operations on Singly link list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
 struct node *next;
};
struct node *head = NULL;

void begInsert ();

void lastInsert ();
void randomInsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\nChoose one option from the following list ...");
printf("\n1.Insert in beginning \n2.Insert at last\n3.Insert at any random
location\n4.Delete from Beginning\n5.Delete from last\n6.Specify location of the
node you want to delete\n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?");
scanf("%d",&choice);
switch(choice)
{
case 1:
begInsert();
break;
case 2:
lastInsert();
break;
case 3:
randomInsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
 exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void begInsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

}
void lastInsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
 while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
}
}
void randomInsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=1;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n can't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
 else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the beginning ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\n list is empty");
}
else if(head -> next == NULL)
{
free(head);
head = NULL;
printf("\nOnly node of the list deleted ...\n");
}

else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node which you want to delete \n");
scanf("%d",&loc);
ptr=head;

for(i=1;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
 {
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc);
}
void search()
{
struct node *ptr;
int item,i=1,flag=0;
temp = head;
if(temp == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (temp!=NULL)
{
if(temp->data == item)
{
printf("item found at location %d ",i);
flag=1;
break;
}
i++;
temp = temp -> next;
}
if(flag==0)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
 {
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n %d",ptr->data);
ptr = ptr -> next;
}
}
}

Applications of linked list in computer science:

1. Implementation of stacks and queues
2. Implementation of graphs: Adjacency list representation of graphs is the
most popular which uses a linked list to store adjacent vertices.
3. Memory Management
4. Maintaining a directory of names
5. Performing arithmetic operations on long integers
6. Manipulation of polynomials by storing constants in the node of the linked list
7. Representing sparse matrices
 Circular Linked List
In a circular Singly linked list, the last node of the list contains a pointer to the first
node of the list. We traverse a circular linked list until we reach the same node where
we started. The circular linked list has no beginning and no ending. There is no null
value present in the next part of any of the nodes.

Logical Representation of Circular Linked List

Circular LINKED LIST IMPLEMENTATION

The implementation of a circular linked list involves two tasks:

1. Declaring the Circular Linked List node
2. Defining the circular linked list operations
1. Circular Linked List Node Declaration
Since a linked list node contains two parts, data and next, a structure construct is best
suited for it. The following structure declaration defines a link list node.

struct node
{
int data;
struct node *next;
};

The above structure declaration defines a new data type called node that represents a
Circular linked list node. The node structure contains two members, data for storing
integer data values and next for storing address of the next node.
The statement, struct node *next, indicates that the pointer next points at same
structure type i.e. node.

2. Operations on Circular linked list

1.Insert
2.Delete
3. Search
4. Print
1. Insert: The insertion into a Circular linked list can be performed at different
positions. Based on the position of the new node being inserted, the insertion is
categorized into the following categories.
1.1 Insertion at beginning
1.2 Insert at the end of the list
1.3 Insertion after specified node

1.1 Insertion at beginning-

Adding a node into circular singly linked list at the beginning.

 Allocate memory for new node.

 Store data.

 Change next of new node to point to head.

 point next of the last node to new node .

 Change head to point to recently created node.

Insert at the beginning

Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
If(head = NULL) then
head = ptr
ptr -> next = head
Else
temp = head;
While(temp->next != head) do
temp = temp->next
EndWhile
ptr->next = head
temp -> next = ptr
head = ptr
EndIf
Print “Node inserted”
EndIf
Stop

1.2 Insertion at end-

Adding a node into circular singly linked list at the end.

 Create a new node.

 Traverse to last node and store the address of new node in the next
part of last node.

 Store the first node address into the next part of new node.

Algorithm
 ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
If(head = NULL) then
head = ptr
ptr -> next = head
Else
temp = head
While (temp -> next !=head) do
temp = temp -> next
EndWhile
temp->next = ptr
ptr->next = head
EndIf
Print “Node inserted”
EndIf
Stop

1.3 Insertion after specific location-

 Make a new node and set the data.

 Move to specified position(after which new node has to be added) in the
circular linked list called it temp.
 Now link the next pointer of new node with the node pointed by the next
pointer of temp node.
 After that join the next pointer of temp node with the newly created node
which means that the next pointer of temp node will point to new node.
Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
Input loc
temp=head
For i=1 to loc-1 do

temp = temp->next;
If(temp = NULL) then
Print " can't insert”
Return
EndIf
EndFor
ptr ->next = temp ->next
temp ->next = ptr
Print “Node inserted"
EndIf
Stop

2. Deletion
The Deletion of a node from a Circular linked list can be performed at different
positions. Based on the position of the node being deleted, the operation is
categorized into the following categories.
2.1 Delete at beginning
2.2 Deletion at the end of the list
2.3 Deletion specified node

2.1 Deletion at beginning

Removing the node from circular linked list at the beginning.

In order to delete a node in circular linked list, we need to make a few pointer
adjustments.
There are three scenarios of deleting a node from circular singly linked list at
beginning.
Scenario 1: (The list is Empty)
If the list is empty then the condition head == NULL will become true, in this case,
we just need to print “Empty list” on the screen and make exit.
Scenario 2: (The list contains single node)
If the list contains single node then, the condition head → next == head will become
true. In this case, we need to do make the head pointer free and head=NULL.
Scenario 3: (The list contains more than one node)
If the list contains more than one node then, in that case, we need to traverse the list
by using the pointer ptr to reach the last node of the list.
At the end of the loop, the pointer ptr point to the last node of the list. Since, the last
node of the list points to the head node of the list. Therefore this will be changed as
now, the last node of the list will point to the next of the head node.
Now, free the head pointer by using the free() method
Make the node pointed by the next of the last node, the new head of the list.

Algorithm
If (head = NULL) then
Print “Empty List”
Else
If(head->next == head) then
ReturnNode(head)
head = NULL;
Print "node deleted”
Else
ptr = head;
While (ptr -> next != head) do
ptr = ptr -> next
EndWhile
ptr->next = head->next
ReturnNode(head)
head = ptr->next
print "node deleted”
EndIf
EndIf
Stop
2.2 Deletion at End
Removing the node from circular singly linked list at the end.
There are three scenarios of deleting a node in circular singly linked list at the end.
Scenario 1 (the list is empty)
If the list is empty then the condition head == NULL will become true, in this case,
we just need to print underflow on the screen and make exit.
Scenario 2(the list contains single element)
If the list contains single node then, the condition head → next == head will become
true. In this case, we need to make the head pointer free and do head=NULL.
Scenario 3(the list contains more than one element)
If the list contains more than one element, then in order to delete the last element, we
need to reach the last node. We also need to keep track of the second last node of the
list. For this purpose, the two pointers ptr and preptr are defined.
now, we need to make just one more pointer adjustment. We need to make the next
pointer of preptr point to the next of ptr (i.e. head) and then make pointer ptr free.

Algorithm
If (head= NULL) then
Print “UNDERFLOW”
Else
If(head->next=head) then
ReturnNode(head)
Head=NULL
Else
ptr = head
While (ptr -> next!=head) do
preptr = ptr
ptr = ptr -> next
EndWhile
preptr -> next = ptr->next
ReturnNode (ptr)
Print “Node Deleted”
Endif
EndIf
Stop
2.3 Delete Specific Node
 Traverse till the node that need to be deleted. Such that at each movement the
address of the previous and current node is stored in separate pointers.
 Change next pointer of the previous node (previous to the specified node) to
hold the address of next node of the specified node (exclude the specified node
from the chain).
Algorithm
Input loc
ptr = head
If(loc=1)
begin_delete()
Return
EndIf
For i = 1 to loc-1 do
ptr1 = ptr
ptr= ptr->next;
If(ptr= NULL) then
Print “Cant delete”
Return
EndIf
EndFor
ptr1->Next= ptr->next;
ReturnNode(ptr)
Print “Deleted node”,loc
Stop

3. Searching

You can search an element on a linked list using a loop using the following steps. We
are finding item on a Circular linked list.
  Copy head to ptr, initialize flag =0 and i =1

 Run do-while loop until the ptr is head.

 In each iteration, check if the key of the node is equal to item. If it

the key matches the item set the flag to 1 and break from the loop,
otherwise increase the i by 1 and move the ptr to next node.

 After Iteration check the flag, if flag is 1- element found at i

otherwise element not found.
Algorithm
i=1
flag =0
ptr = head
If (ptr= NULL) then
` Print “List is Empty”
Else
Input item
do
If ptr → data = item
print “Item found at location”,i
flag =1
Break
EndIf
i=i+1
ptr= ptr->next
While(ptr!=head)
If (flag=0) then
Print “Element not found”
EndIf
EndIf
Stop

Search for 60 is given in diagram below

4. Traversing
Visiting each element of the list at least once in order to perform some specific
operation.
Traversing in circular singly linked list can be done through a loop. Initialize the
pointer variable ptr to head pointer and run the do - while loop until ptr becomes head.
Algorithm
ptr = head
If (head= NULL) then
Print “Nothing to print”
Else
Print “Printing values”
do
Print ptr→ data
ptr = ptr → next
While (ptr!= head)
EndIf
Stop

Complete program on Operations on Circular Linked List

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
void begInsert ();
void lastInsert ();
void randomInsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\nChoose one option from the following list ...");
printf("\n1.Insert in beginning \n2.Insert at last\n3.Insert at any random
location\n4.Delete from Beginning\n5.Delete from last\n6.Specify location of the
node you want to delete\n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?");
scanf("%d",&choice);
switch(choice)
{
case 1:
begInsert();
break;
case 2:
lastInsert();
break;
case 3:
randomInsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
 printf("Please enter valid choice..");
}
}
}

void randomInsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=1;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n can't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}

void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node which you want to delete \n");
scanf("%d",&loc);
ptr=head;

if(loc==1) {begin_delete(); return;}

else {
 for(i=1;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc);
}
}
void begInsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}

}
void lastInsert()
{
 struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}

printf("\nnode inserted\n");
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
free(head);
head = NULL;
printf("\nnode deleted\n");
}

else
{ ptr = head;
while(ptr -> next != head)
 ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");

}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
free(head);
head = NULL;
printf("\nnode deleted\n");

}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");

}
}

void search()
{
struct node *ptr;
int item,i=1,flag=0;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
 do
{
if(ptr->data == item)
{
printf("item found at location %d ",i);
flag=1;
break;
}

i++;
ptr = ptr -> next;
} while (ptr != head);
}
if(flag == 0)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");

do {

printf("%d\n", ptr -> data);

ptr = ptr -> next;
} while(ptr!=head);
}

}
Applications of Circular Linked Lists:

1. Useful for implementation of queue. Unlike this implementation, we don’t need to

maintain two pointers for front and rear if we use circular linked list. We can maintain
a pointer to the last inserted node and front can always be obtained as next of last.
2. Circular lists are useful in applications to repeatedly go around the list. For
example, when multiple applications are running on a PC, it is common for the
operating system to put the running applications on a list and then to cycle through
them, giving each of them a slice of time to execute, and then making them wait while
the CPU is given to another application. It is convenient for the operating system to
use a circular list so that when it reaches the end of the list it can cycle around to the
front of the list.
3. Circular Doubly Linked Lists are used for implementation of advanced data
structures like Fibonacci Heap.

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).
● Each link carries a data field(s) and two link fields called next and prev.
● Each link is linked with its next link using its next link.
● Each link is linked with its previous link using its previous link.
● The last link carries a link as null to mark the end of the list.

Representation of Doubly Linked List

DOUBLY LINKED LIST IMPLEMENTATION

The implementation of a linked list involves two tasks:

1. Declaring the doubly link list node
2. Defining the doubly linked list operations
1. Doubly Linked List Node Declaration
struct node
{
struct node *prev;
int data;
struct node *next;
};
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.

2. Operations
The typical operations performed on a linked list are:
1.Insert
2.Deletion
3.Search
4. Print
1. The insertion into a doubly linked list can be performed at different positions.
Based on the position of the new node being inserted, the insertion is categorized into
the following categories.
1.1 Insertion at beginning
1.2 Insert at the end of the list
1.3 Insertion after specified node

1.1 Insertion at Beginning

As in doubly linked list, each node of the list contain double pointers therefore we
have to maintain more number of pointers in doubly linked list as compare to singly
linked list.

There are two scenarios of inserting any element into doubly linked list. Either the list
is empty or it contains at least one element. Perform the following steps to insert a
node in doubly linked list at beginning.
 Firstly, allocate a new node (say new_node).
 Now put the required data in the new node.
 Make the next of new_node point to the current head of the doubly linked list.
 Make the previous of the current head point to new_node.
 Lastly, point head to new_node.
Algorithm :
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
ptr->prev =NULL
If(head=NULL) then
ptr->next = NULL
Else
ptr->next = head
head->prev = ptr
EndIf
head=ptr
Print"Node inserted"
EndIf
Stop

1.2 Insertion at End

In order to insert a node in doubly linked list at the end, we must make sure whether
the list is empty or it contains any element.
Allocate the memory for the new node. Make the pointer ptr point to the new node
being inserted.
Check whether the list is empty or not. The list is empty if the condition head ==
NULL holds. In that case, the node will be inserted as the only node of the list and
therefore the prev and the next pointer of the node will point to NULL and the head
pointer will point to this node.
In the second scenario, the condition head == NULL become false. The new node will
be inserted as the last node of the list. For this purpose, we have to traverse the whole
list in order to reach the last node of the list. Initialize the pointer temp to head and
traverse the list by using this pointer.
the pointer temp point to the last node at the end of this while loop. Now, we just need
to make a few pointer adjustments to insert the new node ptr to the list. First, make
the next pointer of temp point to the new node being inserted i.e. ptr.
make the previous pointer of the node ptr point to the existing last node of the list i.e.
temp.
make the next pointer of the node ptr point to the NULL as it will be the new last
node of the list.

Algorithm
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input item
ptr->data = item
If(head = NULL) then
ptr -> next = NULL
ptr ->prev = NULL
head = ptr
Else
temp = head
While (temp -> next != NULL) do
temp = temp -> next
EndWhile
temp->next = ptr;
ptr ->prev=temp
ptr->next = NULL;
EndIf
Print “Node inserted”
EndIf
Stop
1.3 Insertion after Specified Node

In order to insert a node after the specified node in the list, we need to skip the
required number of nodes in order to reach the mentioned node and then make the
pointer adjustments as required.
Allocate the memory for the new node. Use the following statements for this.
Traverse the list by using the pointer temp to skip the required number of nodes in
order to reach the specified node.
The temp would point to the specified node at the end of the for loop. The new node
needs to be inserted after this node therefore we need to make a ptr pointer
adjustments here. Make the next pointer of ptr point to the next node of temp.
make the prev of the new node ptr point to temp.
make the next pointer of temp point to the new node ptr.
make the previous pointer of the next node of temp point to the new node.
Algorithm:
ptr = GetNode(node)
If(ptr = NULL) then
Print"OVERFLOW”
Else
Input loc
temp=head
For i=1 to loc-1 do
temp = temp->next;
If(temp = NULL) then
Print " There are less than “,loc,”Elements”
Return
EndIf
EndFor
Input item
ptr->data = item
ptr ->next = temp ->next
ptr ->prev=temp;
temp ->next = ptr
temp->next->prev=ptr;
Print “Node inserted"
EndIf
Stop
2.Delete
The Deletion of a node from a singly linked list can be performed at different
positions. Based on the position of the node being deleted, the operation is
categorized into the following categories.

2.1 Delete at beginning

2.2 Deletion at the end of the list
2.3 Deletion specified node

2.1 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.
Make the prev of this new head node point to NULL.
Now free the pointer ptr by using the free function.
Algorithm:
If (head = NULL) then
Print “Empty List”
Else
If(head->next= NULL) then
ReturnNode(head)
head = NULL
Print “Node Deleted”
Else
ptr= head
head= head -> next
head->prev = NULL
ReturnNode(ptr)
Print “Node Deleted”
EndIf
Endif
Stop

2.2 Deletion 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.
If the list is already empty then the condition head == NULL will become true and
therefore the operation can not be carried on.
If there is only one node in the list then the condition head → next == NULL become
true. In this case, we just need to free head and assign the head of the list to NULL in
order to completely delete the list.
Otherwise, just traverse the list to reach the last node of the list. This will be done by
using the following statements.
The ptr would point to the last node of the list at the end of the loop. Just make the
next pointer of the previous node of ptr to NULL.
Free the pointer as this the node which is to be deleted.
Algorithm:
If (head= NULL) then
Print “Empty List”
Else
If(head->next=NULL) then
free(head)
Head=NULL
Print “Node deleted”
Else
ptr = head
While (ptr -> next!= NULL) do
ptr = ptr -> next
EndWhile
ptr -> prev->next = NULL
ReturnNode (ptr)
Print “Node deleted”
Endif
EndIf
Stop
2.3 Deletion the Specified Node

 Traverse till the node target node call it temp.

 Assign the next pointer of temp to temp's previous node's next pointer.
 Assign the temp's prev pointer to temp's next node's prev pointer.
 Delete the temp node.
Algorithm
Input location
ptr = head
If(loc=1) then
Delete_begining()
Return
EndIf
For i = 1 to loc-2 do
ptr= ptr->next
EndFor
If(ptr->next= NULL) then
Print “Cant delete”
Return
Else
temp = ptr->next
temp->prev -> next = temp -> next;
temp -> next -> prev = temp->prev;
ReturnNode (temp);
printf("\nnode deleted\n");
EndIf
Stop

3.Searching
You can search an element on a doubly linked list using a loop using the following
steps. We are finding item on a doubly linked list.

 Copy head to ptr, initialize flag =0 and i =1

 Run a loop until the ptr is NULL because the last element points
to NULL.

 In each iteration, check if the key of the node is equal to item. If it

the key matches the item set the flag to 1 and break from the loop,
otherwise increase the i by 1 and move the ptr to next node.

 After Iteration check the flag, if flag is 1- element found at i

otherwise element not found.
Algorithm
i=1
flag =0
ptr = head
If (ptr= NULL) then
` Print “List is Empty”
Else
Input item
While (ptr != NULL) do
If ptr → data = item
print “Item found at location”,i
flag =1
Break
EndIf
i=i+1
ptr= ptr->next
EndWhile
If (flag=0) then
Print “Element not found”
EndIf
EndIf
Stop

4. Traversing in doubly linked list

Perform following step to traverse doubly Linked List.
● copy the head pointer in any of the temporary pointer ptr.
● Then, traverse through the list by using while loop. Keep shifting value of
pointer variable ptr until we find the last node. The last node contains null in
its next part.
 ● Although, traversing means visiting each node of the list once to perform
some specific operation.

Algorithm
ptr = head
If (head= NULL) then
Print “Nothing to print”
Else
Print “Printing values”
While (ptr!= NULL) do
Print ptr→ data
ptr = ptr → next
EndWhile
EndIf
Stop

Doubly link list operations

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\
n4.Delete from Beginning\n5.Delete from last\n6.Delete specifies node\n7.Search\
n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
 switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
ptr->data=item;
ptr->prev=NULL;
 if(head==NULL)
{
ptr->next = NULL;
}
else
{
ptr->next = head;
head->prev= ptr;
}
head=ptr;

printf("\nNode inserted\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{

temp=head;
printf("Enter the location after which u want to insert");
scanf("%d",&loc);

for(i=1;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
free(head);
head = NULL;
printf("\nnode deleted\n");
}
else
{
 ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
free(head);
head = NULL;
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int loc,i;
printf("\n Enter the node number that you want to delete");
scanf("%d", &loc);
ptr = head;
if(loc==1) {deletion_beginning();return;}
for(i=1;i<loc-1;i++)
ptr = ptr -> next;
if(ptr->next== NULL)
{
printf("\nCan't delete\n");
}

else
{
 temp = ptr -> next;
temp -> prev->next = temp -> next;
temp -> next -> prev = temp->prev;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
ptr = head;
if(head==NULL)
printf(“Nothing to print”);
else{
printf("\n printing values...\n");

while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
}
void search()
{
struct node *ptr;
int item,i=1,flag=0;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i);
flag=1;
break;
}
i++;
ptr = ptr -> next;
}
if(flag==0)
{
printf("\nItem not found\n");
 }
}

Application of Doubly Linked Lists:

1. Redo and undo functionality.

2. Use of the Back and forward button in a browser.
3. The most recently used section is represented by the Doubly Linked list.
4. Other Data structures like Stack, Hash Table, and Binary Tree can also be applied
by Doubly Linked List.
5. Used to implement game objects and their interactions in a game engine.
6. Used in networking.
7. Used in Graph algorithms.
8. Operating systems use doubly linked lists to manage the process scheduling. Each
process waiting to be executed is represented as a node in the doubly linked list, and
the operating system can easily traverse the list in both directions to manage the
process queue.

Applications of linked list in computer science –

Implementation of stacks and queues

Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked li
Dynamic memory allocation : We use linked list of free blocks.
Maintaining directory of names
Performing arithmetic operations on long integers
Manipulation of polynomials by storing constants in the node of linked list
representing sparse matrices

Open