Data Structures

Linked List

Dr Deepak Gupta
Assistant Professor, SMIEEE
CSED, MNNIT Allahabad, Prayagraj
Email: [email protected]
 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;
}