Data Structures

Linked List

Dr Deepak Gupta
Assistant Professor, SMIEEE
CSED, MNNIT Allahabad, Prayagraj
Email: deepakg@mnnit.ac.in
 Linked List

❑ Linked list is a linear data structure.

❑ Elements are not stored at contagious memory locations

❑ Elements in a linked list are linked using pointers:

❑ Linked list comprise of group of lost of nodes in which each node

contains a data (info) field and a reference (link) to the next node to
form a chain in the list.
 Why Linked List?

❑ Array have the following limitations:

❑ The size of the array is fixed
❑ To insert a new element in an array, existing elements have to be
shifted.

❑ Advantage:
❑ Dynamic size
❑ Ease of insertion and deletion
❑ Disadvantage:
❑ Random access is not allowed in Linked list.
 Representation of Linked List

Node Structure of Linked List

•A singly linked list consists of nodes, where each node contains:
❑ Data Field: Holds the actual data.
❑ Next Field: A pointer/reference to the next node.
// Define the structure for a node
struct node
{
// info field to hold the actual data
int info;
// Next field as a pointer to the next node
struct node *next;
};
 Types of Linked List
❑ Singly Linked List

❑ Doubly Linked list

❑ Circular Singly Linked list

❑ Circular Doubly Linked list

Basic operations of Linked List

❑ Insertion: Adds an element in to the list

❑ Deletion: Delete an element from the list

❑ Display: Display all the elements list

❑ Search: Searches an element using the given key.

 Insertion
❑ Insertion operation can be performed in three ways:

➢ Insertion at beginning of the list

➢ Insertion at End of the list

➢ Insertion at Specific position in the list

1. Create a temporary node

To insert a node, initially we will dynamically allocate space

for that node using malloc( ). Suppose tmp is a pointer that
points to this dynamically allocated node. In the info part of
the node we will put the data value.
tmp = (struct node *) malloc(sizeof(struct node)) ;
tmp->info = data;
temp->next = NULL;

In our explanation we will refer to this new node as node T.

1. Insertion in an empty list
❑ When the list is empty, value of start will be NULL.

start = NULL;

❑ The new node that we are adding will be the only node in the list.
Since it is first node, start should point to this node and it is also the
last node so its next should be

tmp->next = NULL;
start = tmp;

❑ Since initially start was NULL, we can write start instead of NULL in
the first statement, so now these two statements can be written as -
tmp->next = start;
start = tmp;
2. Insertion at the beginning of the list
❑ We have to insert node T at the beginning of the list. Suppose the first
node of list is node P, so the new node T should be inserted before it.

❑ After this statement, link of node T will point to node P.

tmp->next = start;
❑ We want to make node T the first node; hence we should update start so
that now it points to node T.

start = tmp;

struct node *addatbeg(struct node *start , int data)

{
struct node *tmp;
tmp = (struct node *) malloc ( sizeof ( struct node)) ;
tmp->info = data;
tmp->next = start;
start = tmp;
return start;
}/* End of addatbeg() */
3. Insertion at the end of the list
❑ We have to insert a new T at the end of the list. Suppose the last node of
list is node P, so node T should be inserted after node P.

p->next = tmp;
tmp->next = NULL;
❑ So, in this case we should have a pointer p pointing to the last node of the
list. The only information about the linked list that we have is the pointer
start. p = start; Terminating condition is
while(p->next!=NULL) (p->next!=NULL).
p = p->next;

struct node *addatend (struct node * start , int data)

{
struct *p, *tmp;
tmp = (struct node *) malloc ( sizeof ( struct node)) ;
tmp->info = data;
p = start;
while(p->next!=NULL)
p = p->next;
p->next = tmp;
tmp->next = NULL;
return start;
}/* End of addatend( ) */
4. Insertion in between the list nodes.
❑ We have to insert a node T between nodes P and Q.
❑ Suppose we have two pointers p and q pointing to nodes P and Q
respectively. The two statement should be written for insertion of node T
are –
tmp->next = q;
p->next = tmp;

❑ Before insertion address of node Q is in p->next , so instead of pointer q

we can write p->link. Now the two statement for insertion can be written
as-
tmp->next = p->next;
p->next = tmp;
Three cases of insertion in between the nodes-
1. Insertion after a node
2. Insertion before a node
3. Insertion at a given position
4.1 Insertion after a node
struct node *addafter(struct node *start, int data, int item)
{
struct node *tmp, *p;
p = start;
while( p!= NULL)
{
if(p->info == item)
{
tmp = (struct node *) malloc ( sizeof ( struct node)) ;
tmp->info = data;
tmp->next = p->next;
p->next = tmp;
return start;
}
p = p->next;
}
printf(“%d not present in the list\n”,item);
return start;
}/* End of addafter()*/
4.2. Insertion before a node
struct node *addbefore(struct node *start, int data, int item)
{
struct node *tmp, *p, *q;
if(start == NULL)
{
printf(“List is empty\n”);
}
/* If data to be inserted before first node*/
if(item== start ->info)
{
tmp = (struct node *) malloc ( sizeof ( struct node)) ;
tmp->info = data;
tmp->link = start;
start = tmp;
return start;
}
 p= start;
while(p->next!=NULL)
{
If(p->info==item)
{
tmp = (struct node *) malloc ( sizeof (struct node)) ;
tmp->info = data;
tmp->link = q->link;
q->link = tmp;
return start;
}
q = p;
p = p->next;
}
printf(“%d not present in the list\n”, item);
return start;
} /*End of addbefore()*/
4.3. Insertion at given position
struct node *addatpos(struct node *start, int data, int pos)
{
struct node *tmp, *p;
int i;
tmp = (struct node *) malloc ( sizeof ( struct node)) ;
tmp->info = data;
if(pos==1)
{
tmp->next = start;
start = tmp;
return start;
}
 p= start;
for(i=1; i<pos-1 && p!=NULL; i++)
{
p = p->next;
}
if(p == NULL)
{
printf(“There are less than %d elements\n”, pos);
}
else
{
tmp->next = p->next;
p->next = tmp;
}
return start;
} /*End of addatpos( )*/
 Deletion
❑ Deletion operation can be performed in three ways:

➢ Deletion at beginning of the list

➢ Deletion at End of the list

➢ Deletion at Specific position in the list

➢Deletion at beginning of the list
// Delete the first node and return the new start
struct node* delete_firstnode(struct node* start)
{
struct node* temp;
// Check if the list is empty
if (start == NULL)
{
printf(“ \n Underflow: List if empty”);
return NULL;
}
temp = start; // Store the current start in a temporary variable
start = start->next; // Move the start pointer to the next node
free(temp); // Free the memory of the old start node
return start;
}
➢Deletion at end of the list
void delete_lastnode(struct node* start)
{
struct node* temp, *prev;
temp = start;
// Check if the list is empty
if (start == NULL) {
printf(“ \n Underflow: List if empty”);
return NULL;
}
if (temp->next == NULL)
start = NULL;
else
{
while(temp->next!=NULL)
{
prev = temp;
temp = temp->next;
}
prev ->next = NULL;
}
free(temp);
printf(“\n Node Deleted”);
}
// Delete the node at position
void delete_pos(struct node* start, int pos)
{
struct node* temp, *prev;
temp = start;
// Check if the list is empty
if (start == NULL) {
printf(“ \n Underflow: List if empty”);
return NULL;
}
if (pos ==0)
printf(“\n Invalid position”);
if (pos == 1)
start = temp->next;
else {
for(i=1; i<pos ; i++) {
prev = temp;
temp = temp->next;
}
prev ->next = temp->next;
}
free(temp);
printf(“\n Node deleted at position”);
}
Display and count the element of the list:
void display(struct node *start)
{
struct node *temp;
int count=0;
if(start == NULL)
{
printf(“List is empty\n”);
return;
}
/* Display the element of the list:*/
printf(“\n\nThe linked list is:”);
while(temp != NULL)
{
printf(“%d”, temp->info);
count++;
temp = temp->info;
}
printf(“The total no. of element is %d” , count);
return;
}
Reversing a Single Linked List:
❑ The following changes need to be done in a single linked list for
reversing it.

➢ First node should become the last node of linked list.

➢ Last node should become the first node of linked list and now start should
point to it.
➢ Link of 2nd node should point to 1st node, link of 3rd node should point to 2nd
node and so on.
Prev is NULL.

Start
ptr next

1 2 3 4

Start
ptr next

1 2 3 4

Start
prev ptr

1 2 3 4

Start
prev ptr next

1 2 3 4
Start
prev ptr next

1 2 3 4

Start
prev ptr

1 2 3 4

Start
prev ptr next

1 2 3 4
Start
prev ptr next

1 2 3 4

Start
prev ptr

1 2 3 4

Start next is NULL

prev ptr

1 2 3 4
Start next is NULL
prev ptr

1 2 3 4

Start ptr is NULL

prev

1 2 3 4

Start ptr is NULL

prev

1 2 3 4
Reversing a Single Linked List:
Struct node *reverse(struct node *start)
{
struct node *prev, *ptr, *next;
prev = NULL;
ptr = start;
while(ptr!=NULL)
{
next = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = next;
}
start = prev;
return start;
}/*end of reverse*/
 Doubly Linked List
To overcome the drawback of a singly linked list, we have another data
structure called a doubly linked list or two-way list, in which each node has
two pointers and one information value. One of these pointers points to the
next node and the other points to the previous node.
The structure of a doubly linked list can be declared as:
struct node{
struct node *prev;
int info;
struct node *next;
Contains address
}; of the next node

Contains address of
the previous node
 Traversing a doubly linked list
The function of traversal of doubly linked list is similar to singly linked
list.
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf(“List is empty”);
}
p=start;
while(p!=NULL)
{
printf(“%d”, p->info);
p=p->next;
}
printf(“/n”);
}
Insertion in a doubly linked list
We will study all four cases of insertion in a doubly linked list:
1. Insertion at the beginning of the list
2. Insertion in an empty list
3. Insertion at the end of the list
4. Insertion in between the nodes
 1. Insertion at the beginning of the list
After Insertion
Before Insertion Start
Start
Node P
1 2 3 4
Node P
Node T
1 2 3 4 6

• Node T has become the first node so its prev should be NULL.
tmp->prev = NULL;
• The next part of the Node T should point to node P, and address of
node P is in strat so we should write:
tmp->next = start;
• Node T is inserted before node P so prev part of node P should now
point to node T.
start->prev = tmp;
• Now Node T has become the first node so start should point to it.
start = tmp;
struct node *addatbeg (struct node *start, int data)
{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
tmp -> prev = NULL;
tmp -> next = start;
start -> prev = tmp;
start = tmp;
return start;
}
2. Insertion in an empty list

• Node T is the first node so its prev part should be NULL, and it is also
the last node so its next part should also be NULL. Node T is the first
node so start should point to it.
tmp->prev = NULL;
tmp->next = NULL;
start = tmp;
struct node *addtoempty (struct node *start, int data)
{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
tmp -> prev = NULL;
tmp -> next = NULL;
start = tmp;
return start;
}
3. Insertion at the end of the list

Suppose Node P is the last node of the list

• Node T becomes the last node so its next should be NULL
tmp->next = NULL;
• next part of Node P should point to Node T.
p ->next = tmp;

• prev part of Node T should point to Node P.

tmp ->prev = p;
struct node *addatend (struct node *start, int data)
{
struct node *tmp, *p;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
p = start;
while(p ->next != NULL)
p = p->next;
p -> next = tmp;
tmp -> next = NULL;
tmp -> prev = p;
return start;
}
4. Insertion in between the nodes

Suppose pointers p and q point to Node P and Node Q respectively.

• Node P is before Node T so prev part of Node T should point to Node P
tmp->prev = p;
• Node Q is after Node T so next part of Node T should point to Node Q
tmp->next = q;
• Node T is before Node Q so prev part of Node Q should point to Node T
q->prev = tmp;
• Node T is after Node P so next part of Node P should point to Node T
p->next = tmp;
We can replace q by p->next.

tmp->prev = p; tmp->prev = p;
tmp->next = q; tmp->next = p->next;
q->prev = tmp; p->next ->prev = tmp;
p->next = tmp; p->next = tmp;
4. Insertion in between the nodes (continue..)
struct node *addafter (struct node *start, int data, int item)
{
struct node *tmp, *p;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
p = start;
while(p != NULL)
{
if(p->info == item)
{
tmp->prev = p;
tmp->next = p->next;
if ( p->next!=NULL)
p->next ->prev = tmp;
p->next = tmp;
return start;
}
p = p -> next;
}
printf(“%d not present in the list\n”, item);
return start;
}
Creation in a doubly linked list
struct node *create_list (struct node *start)
{
int i, n, data;
printf(“Enter the number of nodes: ”);
scanf(“%d”, &n);
start = NULL;
if(n==0)
return start;
printf(“Enter the element to be inserted: ”);
scanf(“%d”, &data);
start = addtoempty(start, data);
for(i=2; i<=n; i++)
{
printf(“Enter the element to be inserted: ”);
scanf(“%d”, &data);
start = addatend(start, data);
}
return start;
}
Deletion from doubly linked list
We will study all four cases of insertion in a doubly linked list:
1. Deletion of the first node
2. Deletion of the only node
3. Deletion in between the nodes
4. Deletion at the end of the list
1. Deletion of the first node

• tmp will be assigned the address of first node

tmp = start;

• start will be updated so that now it points to Node P

start = start->next;

• Now Node P is the first node so its prev part should contain NULL
start->prev = NULL;
2. Deletion of the only node

tmp = start;
start = NULL;
3. Deletion in between the nodes

Suppose we have to delete Node T, and let pointers p, tmp and q point to
Nodes P, T and Q respectively.
• The two statements for deleting Node T can be written as:
p->next = q;
q->prev = p;
• The address of q is in tmp->next so we can replace q by tmp->next.
• The address of p is in tmp->prev so we can replace p by tmp->prev.
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
4. Deletion at the end of the list

Suppose Node T is to be deleted and pointers tmp and p points to Nodes T

and P respectively.
• The deletion can be performed by writing the following statement:
p->next = NULL;

• The address of node P in above statement, is stored in tmp->prev, so we

can replace p by tmp->prev.
tmp->prev->next = NULL;
struct node *del (struct node *start, int data)
{
struct node *tmp;
if(start = = NULL)
{
printf(“List is empty”);
return start;
}
if(start->next = = NULL) /*Deletion of only node*/
if(start->info = =data)
{
tmp = start;
start = NULL;
free(tmp);
return start;
}
else
{
printf(“Element %d not found\n”, data);
return start;
}
if(start->info = = data) /*Deletion of first node*/
{ {
tmp = start;
start = start->next;
start->prev = NULL;
free(tmp);
return start;
}
tmp = start->next; /*Deletion in between*/
while(tmp->next!=NULL)
{
if(tmp->info = = data)
{
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
free(tmp);
return start;
}
tmp = tmp->next;
}
 if(tmp->info = = data) /*Deletion of last node*/
{
tmp->prev->next = NULL;
free(tmp);
return start;
}
printf(“Element %d not found\n”, data);
return start;
}
Reversing a doubly linked list

In the reversed list:

• start point to Node D.
• Node D is the first node so its prev is NULL.
• Node A is the last node so its next is NULL.
• next of D points to C, next of C points to B and next of B points to A.
• prev of A points to B, prev of B points to C, prev of C points to D.
struct node *reverse (struct node *start)
{
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while(p2!=NULL)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev;
}
start = p1;
printf(“List reversed”);
return start;
}
 Circular Linked List
In a singly linked list, the link part of the last node is NULL, if we utilize
this link to point to the first node then we can have some advantages. The
structure thus formed is called a circular linked list.
The circular singly linked list has no beginning and no ending. There is no
null value present in the next part of any of the nodes. The following figure
shows a circular linked list:

struct node{
int info;
struct node *next;
};
 Traversal in a Circular linked list
The function of traversal of a Circular linked list is similar to a singly
linked list.
void display(struct node *last)
{
struct node *p;
if(last==NULL)
{
printf(“List is empty”);
return;
}
p=last->next;
do
{
printf(“%d”, p->info);
p=p->next;
} while(p!=last->next);
printf(“/n”);
}
 Insertion in a Circular linked list
1. Insertion at the beginning of the list

• After insertion, link of node T should point to node P and address of

node P is in last->link
tmp->next = last->next;
• Link of last node should point to node T
last->next = tmp;

struct node *addatbeg (struct node *last, int data)

{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
tmp -> next = last->next;
last->next = tmp;
return last;
}
 Circular Linked List
2. Insertion in an empty list

• After insertion, T is the last node so the pointer last points to node T
last = tmp;
• Here, T is the first node so last->link points to node T
last->next = last;

struct node *addtoempty (struct node *last, int data)

{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
last = tmp;
last -> next = last;
return last;
}
 Circular Linked List
3. Insertion at the end of the list

• link of Node T should point to node A and the address of node A is in

last->link.
tmp->next = last->next;
• Link of node P should point to node T
last->next = tmp;
• last should point to node T struct node *addatend (struct node *last, int data)
{
last = tmp;
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
tmp->next = last->next;
last->next = tmp;
last = tmp;
return last;
}
 Circular Linked List
4. Insertion in between the nodes
• The logic for insertion in between the nodes is the same as in single linked list. If
insertion is done after the last node then the pointer last should be updated.
struct node *addafter (struct node *last, int data, int item)
{
struct node *tmp, *p;
p = last->next;
do
{
if(p->info = = item)
{
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = data;
tmp->next = p->next;
p->next = tmp;
if ( p = = last)
last = tmp;
return last;
}
p = p -> next;
} while(p != last->next);
printf(“%d not present in the list\n”, item);
return last;
}
 Circular Linked List
Creation of Circular linked list
struct node *create_list (struct node *last)
{
int i, n, data;
printf(“Enter the number of nodes: ”);
scanf(“%d”, &n);
last = NULL;
if(n==0)
return last;
printf(“Enter the element to be inserted: ”);
scanf(“%d”, &data);
last = addtoempty(last, data);
for(i=2; i<=n; i++)
{
printf(“Enter the element to be inserted: ”);
scanf(“%d”, &data);
last = addatend(last, data);
}
return last;
}
 Circular Linked List
Deletion in Circular linked list
1. Deletion of the first node

• Before deletion, last points to node Z and last->next points to node T.

• After deletion, the link of node Z should point to node A, so last->next

should point to node A. The Address of node A is in the link of node T.
tmp = last->next;
last->next = tmp->next;
 Circular Linked List

2. Deletion of the only node

• There will be only one node in the list if link of the last node points to
itself. After deletion, the list will become empty so NULL Is assigned to
last.
last = NULL;

3. Deletion in between the nodes

Deletion in between is same as in single linked list.

 Circular Linked List

4. Deletion at the end of the list

• Before deletion, last points to node T and last->link points to node A, p

is a pointer to node P.

• After deletion, link of node P should point to node A. The address of

node A is in last->next.
p->next = last->next;
• Now P is the last node so last should point to node P
last = p;
struct node *del (struct node *last, int data)
{
struct node *tmp, *p;
if(last = = NULL)
{
printf(“List is empty”);
return last;
}
if(last->next = = last && last->info = = data) /*Deletion of only node*/
{
tmp = last;
last = NULL;
free(tmp);
return last;
}
if(last->next>info = = data) /*Deletion of first node*/
{
tmp = last->next;
last->next = tmp->next;
free(tmp);
return last;
}
 p = last->next; /*Deletion in between*/
while(p->next!=last)
{
if(p->next->info = = data)
{
tmp = p->next;
p->next = tmp->next;
free(tmp);
return last;
}
p = p->next;
}
if(last->info = = data) /*Deletion of last node*/
{
tmp = last;
p->next = last->next;
last = p;
free(tmp);
return last;
}
printf(“Element %d not found\n”, data);
return last;
}
 Doubly Circular Linked List

• It is similar to a doubly linked list that points to not only the next node
but to the previous node as well. In a doubly circular linked list, the
next of the last node points to the first node and the prev of the first
node points to the last node.
 Doubly Circular Linked List
1. Insertion at the beginning of the list
struct node *addatbeg (struct node *start, int data)
{ struct node *tmp, *ptr;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
printf(“\nOverflow”);
else
ptr -> info = data;
if(start = = NULL) /*list is empty*/
{ start=ptr;
ptr->next = start;
ptr->prev = start;
}
else /*list is not empty*/
{ temp = start;
while(temp->next!=start)
temp=temp->next;
temp -> next = ptr;
ptr -> prev = temp;
start -> prev = ptr;
ptr->next = start;
start = ptr;
}
}
 Doubly Circular Linked List
2. Insertion at the end of the list
struct node *addatend (struct node *start, int data)
{ struct node *tmp, *ptr;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
printf(“\nOverflow”);
else
ptr -> info = data;
if(start = = NULL) /*list is empty*/
{ start=ptr;
ptr->next = start;
ptr->prev = start;
}
else /*list is not empty*/
{ temp = start;
while(temp->next!=start)
temp=temp->next;
temp -> next = ptr;
ptr -> prev = temp;
start -> prev = ptr;
ptr->next = start;
}
}
 Doubly Circular Linked List
1. Deletion at the beginning of the list
struct node *delatbeg (struct node *start, int data)
{ struct node *tmp;
if(start==NULL)
printf(“\nUnderflow”);
else if(start->next==start)
{
start = NULL;
free(start);
printf(“Node deleted”);
}
else
{
temp = start;
while(temp->next!=start)
temp=temp->next;
temp -> next = start->next;
start -> next -> prev = temp;
free(start);
start = temp->next;
}
}
 Doubly Circular Linked List
2. Deletion at the end of the list
struct node *delatbeg (struct node *start, int data)
{ struct node *ptr;
if(start==NULL)
printf(“\nUnderflow”);
else if(start->next==start)
{
start = NULL;
free(start);
printf(“Node deleted”);
}
else
{
ptr = start;
if(ptr->next!=start)
ptr = ptr->next;
ptr ->prev-> next = start;
start ->prev = ptr->prev;
free(ptr);
printf(“node deleted”);
}
}