DS UNIT -3

Linked list
Linked list is a linear data structure that includes a series of connected nodes. Linked list can be defined as the
nodes that are randomly stored in the memory. A node in the linked list contains two parts, i.e., first is the data
part and second is the address part. The last node of the list contains a pointer to the null. After array, linked
list is the second most used data structure. In a linked list, every link contains a connection to another link.

Representation of a Linked list

Linked list can be represented as the connection of nodes in which each node points to the next node
of the list. The representation of the linked list is shown below -

Till now, we have been using array data structure to organize the group of elements that are to be
stored individually in the memory. However, Array has several advantages and disadvantages that
must be known to decide the data structure that will be used throughout the program.

Why use linked list over array?

Linked list is a data structure that overcomes the limitations of arrays. Let's first see some of the
limitations of arrays -

o The size of the array must be known in advance before using it in the program.
o Increasing the size of the array is a time taking process. It is almost impossible to expand the size
of the array at run time.
o All the elements in the array need to be contiguously stored in the memory. Inserting an element
in the array needs shifting of all its predecessors.
Linked list is useful because -

o It allocates the memory dynamically. All the nodes of the linked list are non-contiguously stored
in the memory and linked together with the help of pointers.
o In linked list, size is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available memory space.

How to declare a linked list?

It is simple to declare an array, as it is of single type, while the declaration of linked list is a bit more
typical than array. Linked list contains two parts, and both are of different types, i.e., one is the
simple variable, while another is the pointer variable. We can declare the linked list by using the
user-defined data type structure.

The declaration of linked list is given as follows -

 DS UNIT -3
struct node
{
int data;
struct node *next;
}
In the above declaration, we have defined a structure named as node that contains two variables, one
is data that is of integer type, and another one is next that is a pointer which contains the address of
next node.

Types of Linked list

Linked list is classified into the following types -

o Singly-linked list - Singly linked list can be defined as the collection of an ordered set of
elements. A node in the singly linked list consists of two parts: data part and link part.
Data part of the node stores actual information that is to be represented by the node,
while the link part of the node stores the address of its immediate successor.
o 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), and pointer to the previous node (previous pointer).

Advantages of Linked list

The advantages of using the Linked list are given as follows -

o Dynamic data structure - The size of the linked list may vary according to the
requirements. Linked list does not have a fixed size.
o Insertion and deletion - Unlike arrays, insertion, and deletion in linked list is easier.
Array elements are stored in the consecutive location, whereas the elements in the linked
list are stored at a random location. To insert or delete an element in an array, we have to
shift the elements for creating the space. Whereas, in linked list, instead of shifting, we
just have to update the address of the pointer of the node.
o Memory efficient - The size of a linked list can grow or shrink according to the
requirements, so memory consumption in linked list is efficient.
o Implementation - We can implement both stacks and queues using linked list.

Disadvantages of Linked list

The limitations of using the Linked list are given as follows -

o Memory usage - In linked list, node occupies more memory than array. Each node of the
linked list occupies two types of variables, i.e., one is a simple variable, and another one
is the pointer variable.
o Traversal - Traversal is not easy in the linked list. If we have to access an element in the
linked list, we cannot access it randomly, while in case of array we can randomly access
it by index. For example, if we want to access the 3rd node, then we need to traverse all
the nodes before it. So, the time required to access a particular node is large.
o Reverse traversing - Backtracking or reverse traversing is difficult in a linked list. In a
doubly-linked list, it is easier but requires more memory to store the back pointer.
 DS UNIT -3
Applications of Linked list
The applications of the Linked list are given as follows -

o With the help of a linked list, the polynomials can be represented as well as we can
perform the operations on the polynomial.
o A linked list can be used to represent the sparse matrix.
o The various operations like student's details, employee's details, or product details can be
implemented using the linked list as the linked list uses the structure data type that can
hold different data types.
o Using linked list, we can implement stack, queue, tree, and other various data structures.
o The graph is a collection of edges and vertices, and the graph can be represented as an
adjacency matrix and adjacency list. If we want to represent the graph as an adjacency
matrix, then it can be implemented as an array. If we want to represent the graph as an
adjacency list, then it can be implemented as a linked list.
o A linked list can be used to implement dynamic memory allocation. The dynamic
memory allocation is the memory allocation done at the run-time.

Singly Linked list

It is the commonly used linked list in programs. If we are talking about the linked list, it means it is a
singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is the data
part, and the other one is the address part, which contains the address of the next or the successor
node. The address part in a node is also known as a pointer.

Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:

We can observe in the above figure that there are three different nodes having address 100, 200 and
300 respectively. The first node contains the address of the next node, i.e., 200, the second node
contains the address of the last node, i.e., 300, and the third node contains the NULL value in its
address part as it does not point to any node. The pointer that holds the address of the initial node is
known as a head pointer.

The linked list, which is shown in the above diagram, is known as a singly linked list as it contains
only a single link. In this list, only forward traversal is possible; we cannot traverse in the backward
direction as it has only one link in the list.

Representation of the node in a singly linked list

struct node
 DS UNIT -3
{
int data;
struct node *next;
}
In the above representation, we have defined a user-defined structure named a node containing two
members, the first one is data of integer type, and the other one is the pointer (next) of the node typ

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such
operations is given below.

Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));

Insertion
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.

Operation Description

It involves inserting any element at the

front of the list. We just need to a few
1 Insertion at beginning
link adjustments to make the new
node as the head of the list.

It involves insertion at the last of the

linked list. The new node can be
inserted as the only node in the list or
2 Insertion at end of the list
it can be inserted as the last one.
Different logics are implemented in
each scenario.

It involves insertion after the specified

node of the linked list. We need to
3 Insertion after specified node skip the desired number of nodes in
order to reach the node after which the
new node will be inserted. .
 DS UNIT -3
Deletion and Traversing
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.

Operation Description

It involves deletion of a node from

the beginning of the list. This is the
1 Deletion at beginning simplest operation among all. It just
need a few adjustments in the node
pointers.

It involves deleting the last node of

the list. The list can either be empty
2 Deletion at the end of the list or full. Different logic is
implemented for the different
scenarios.

It involves deleting the node after the

specified node in the list. we need to
skip the desired number of nodes to
3 Deletion after specified node
reach the node after which the node
will be deleted. This requires
traversing through the list.

In traversing, we simply visit each

node of the list at least once in order
4 Traversing to perform some specific operation
on it, for example, printing data part
of each node present in the list.

In searching, we match each element

of the list with the given element. If
the element is found on any of the
5 Searching
location then location of that element
is returned otherwise null is returned.
.

Linked List in C: Menu Driven Program

#include<stdio.h>
 DS UNIT -3
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

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("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.De
lete from Beginning\n 5.Delete from last\n6.Delete node after specified location\
n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
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;
 DS UNIT -3
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");
}
 DS UNIT -3
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=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
 DS UNIT -3
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
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 after which you want to perfrm deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
 DS UNIT -3
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
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("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}

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

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 :

struct node
{
struct node *prev;
 DS UNIT -3
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.

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.
 DS UNIT -3

Operations on doubly linked list

Node Creation

struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;
All the remaining operations regarding doubly linked list are described in the following table.

SN Operation Description

Adding the node into the linked

1 Insertion at beginning
list at beginning.
 DS UNIT -3
Adding the node into the linked
2 Insertion at end
list to the end.

Adding the node into the linked

3 Insertion after specified node
list after the specified node.

Removing the node from

4 Deletion at beginning
beginning of the list

Removing the node from end of

5 Deletion at the end
the list.

Removing the node which is

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

Comparing each node data with

the item to be searched and
7 Searching return the location of the item in
the list if the item found else
return null.

Visiting each node of the list at

least once in order to perform
8 Traversing
some specific operation like
searching, sorting, display, etc.