Department of Electrical and Electronics

Engineering
U20EST356
DATA STRUCTURES

Handling by
Mr.J.Muruganandham
Assistant Professor
Department of EEE
 UNIT III
LINKED LIST OPERATIONS
Linked Lists: Singly linked list: Representation in memory.
Algorithms of several operations: Traversing – Searching –
Insertion – Deletion. Linked representation of Stack and
Queue. Doubly linked list: operations. Circular Linked Lists:
operations.
Single linked list
 Single linked list
• A Linked List is a data structure, where data
nodes are linked together forming a chain or
list.
• A Linked list is made up of nodes, where a
node is made up of two parts:
• Data Part: Holds the data
• Address Part: Holds the address of the next
node.
 Define a node using structure

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*head
 Create list

void create(int x)
{
struct node *temp;
int main()
temp=(struct node*)malloc(sizeof(struct node));
{
temp->data=x;
create(10);
temp->next=NULL;
}
start=temp;
printf("\nList created");
}
 Display

void display()
{
if(head==NULL)
printf("List is empty\n");
else
{
struct node *p;
p=head;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("End\n");
}
}
 Insert at the front

void insert_front(int x)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->next=head;
head=temp;
}
 Insert at end

void insert_end(int x)
{
struct node *temp,*p;
p=head;
while(p->next!=NULL)
{
p=p->next;
}
temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->next=NULL;
p->next=temp;
}
 Insert at middle

void insert_mid(int x,int pos)

{
int i;
struct node *p=head,*q;
for(i=1;i<pos;i++)
{
q=p;
p=p->next;
}
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->next=q->next;
q->next=temp;

}
 Delete at the front

void delet_front()
{
struct node *p;
p=head;
head=head->next;
free(p);
}
 Delete at the end

void delet_end()
{
struct node *p=head,*q;
while(p->next!=NULL)
{
q=p;
p=p->next;
}
q->next=NULL;
free(p);
}
 Delete node at the position

void delet_mid(int pos)

{
int i;
struct node *p=head,*q;
for(i=1;i<pos;i++)
{
q=p;
p=p->next;
}
q->next=p->next;
free(p);
}
 Double linked list

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
struct node
{
int info;
struct node *next;
struct node *prv;
}*start;
 Create and insert at the end

else
void create(int data) {
{ ptr=start
struct node *ptr, *temp; while(ptr->next!=NULL)
temp=(struct node*)malloc(sizeof(struct node)); {
temp->info=data; ptr=ptr->next;
if(start==NULL) }
{ ptr->next=temp;
temp->next=NULL; temp->next=NULL;
temp->prv=NULL; temp->prv=prt;
start=temp; return;
} }
}
 Insert at the begging

void insert_beg(int data)

{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
temp->prv=NULL;
temp->next=start;
start=temp;
}
 Inset at the after

void insert_after(int data, int pos)

{
struct node *temp,*ptr,*t;
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
int i;
ptr=start;
for(i=0;i<position;i++)
{
if(ptr==NULL)
{
printf("Invalid position");
return;
}
ptr=ptr->next;
}
temp->next=t;
t->prv=temp;
temp->prv=ptr;
ptr->next=temp;
}
 Delete the number at the begning

Void delet_beg()
{
struct *temp,*ptr;
if(start->info==data)
{
temp=start;
start=start->next;
start->prv=NULL;
free(temp);
Return;
}
}
void delet_mid(int data)
{
struct node *ptr, *t1, *t2;
ptr=start;
while(1)
{
ptr=ptr->next;
if(ptr->info==data)
{
t1=ptr->prv;
t2=ptr->next;
t1->next=t2;
t2->prv=t1;
}
}
 Circular Linked List

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>

struct node
{
int info;
struct node *link;
}*last;
 Create the circular linked list
void creat_list(int data)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
if(last==NULL)
{
last=temp;
temp->link=last;
printf("\nList created ");
}
else
{
temp->link=last->link;
last->link=temp;
last=temp;
printf("\nElement added at the END");
}
}
void display() Display()
{
struct node *ptr;
if(last==NULL)
{
printf("\nList is Empty");
return;
}
else
{
ptr=last->link;
printf("\n");
while(1)
{
printf("%d\t",ptr->info);
if(ptr!=last)
ptr=ptr->link;
else
break;
}
}
}
 Inserted at beginning

void insert_beg(int data)

{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data;
temp->link=last->link;
last->link=temp;
printf("\nElement added at beginning ");
}
 Inserted at the given position

void insert_mid(int data, int pos)

{
struct node *temp,*ptr;
int i;
ptr=last->link;
for(i=0; i<pos-1; i++)
{
ptr=ptr->link;
}

temp=(struct node*)malloc(sizeof(struct node));

temp->info=data;
temp->link=ptr->link;
ptr->link=temp;
printf("\nInserted at The given position");
}
 Delete the last node
Void delet(int data)
{
struct node *temp, *ptr;
if(last->link==last&&last->info==data) //only one element
{
tmp=last;
last=NULL;
free(tmp);
return;
}
ptr=last->link;
if(prt->info==data)
{
temp=prt;
last->link=ptr->link
Free(temp)
return;
}
While(prt->link!=last)
{
If(ptr->link->info==data)
{
Temp=ptr->link;
Ptr->link=temp->link;
Free(temp);
Printf(“Item deleted”);
return
}
Ptr=ptr->link;
}
Linked stack
 Stack Operations using Linked List
To implement a stack using a linked list, we need to set the following things
before implementing actual operations.

Step 1 - Include all the header files which are used in the program. And
declare all the user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define a Node pointer 'top' and set it to NULL.
Step 4 - Implement the main method by displaying Menu with list of
operations and make suitable function calls in the main method.

#include <stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*top=NULL;
push(value) - Inserting an element into the Stack
• We can use the following steps to insert a new node into the stack...
• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

void push(int a) {
{ struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
if(top==NULL)
{ temp->data=a;
struct node *temp; temp-->link=top;
temp=(struct node*)malloc(sizeof(struct node)); top=temp;
temp->data=a; }}
temp->link=NULL;
top=temp;
}
 Linked stack void push(int a) • Push( )
{ • Pop( )
if(top==NULL) • Display( )
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=a;
temp->link=NULL;
top=temp;
}
else
#include <stdio.h> {
#include <stdlib.h> struct node *temp;
#include<malloc.h>
temp=(struct node*)malloc(sizeof(struct node));
int data;
struct node temp->data=a;
{ temp-->link=top;
int data; top=temp;
struct node *link; }}
}*top=NULL;
pop() - Deleting an Element from a Stack
• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not
possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).
void pop()
{
if(top==NULL)
printf("Underflow");
else
{
struct node *p;
p=top;
printf("Deleted item is : %d",p->data);
top=top->link;
free(p);
}
}
• pop() - Deleting an Element from a Stack
• We can use the following steps to delete a node from the stack...
• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not
possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to
'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).
• display() - Displaying stack of elements
• We can use the following steps to display the elements (nodes) of a stack...
• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the
function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize
with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the
same until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL
void pop()
{ void display()
if(top==NULL) {
printf("Underflow"); struct node *p;
else p=top;
{
while(p!=NULL)
struct node *p;
p=top;
{
a=top->data; printf("\n%d",ptr->data);
top=top->link; ptr=ptr->link;
printf("Deleted item is : %d",data); }
free(p); }
}
} int main()
{
push();
display();
pop();
display();
return 0;
}
 void Enqueue(int a)
Linked Queue {
if(front==NULL)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=a;
temp->link=NULL;
#include <stdio.h> front=rear=temp;
#include <stdlib.h> }
#include<malloc.h> else
int data; {
struct node struct node *temp;
{ temp=(struct node*)malloc(sizeof(struct node));
int data; temp->data=a;
struct node *link; temp->link=NULL;
rear->link=temp;
}*front=NULL,*rear=NULL;
}
}
 void display()
void dequeue()
{
{
struct node *p;
struct node *p;
p=front;
if(front==NULL)
if(front==NULL)
printf("under flow");
printf("Under flow");
else
else
{
{
p=front;
while(ptr!=NULL)
front=front->link;
{
free(p);
printf("%d",ptr->data);
}
p=p->link;
}
}
}
}
Circular linked list and linked
stack and linked queue
 Circular Linked List
What is Circular Linked List?
• In single linked list, every node points to its next node in the sequence and
the last node points NULL.
• But in circular linked list, every node points to its next node in the sequence
but the last node points to the first node in the list.
• A circular linked list is a sequence of elements in which every element has a
link to its next element in the sequence and the last element has a link to the
first element.
Linked stack
 Stack Operations using Linked List
To implement a stack using a linked list, we need to set the following things
before implementing actual operations.

Step 1 - Include all the header files which are used in the program. And declare
all the user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define a Node pointer 'top' and set it to NULL.
Step 4 - Implement the main method by displaying Menu with list of
operations and make suitable function calls in the main method.

#include <stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*top=NULL;
push(value) - Inserting an element into the Stack
• We can use the following steps to insert a new node into the stack...
• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

void push(int a) {
{ struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
if(top==NULL)
{ temp->data=a;
struct node *temp; temp-->link=top;
temp=(struct node*)malloc(sizeof(struct node)); top=temp;
temp->data=a; }}
temp->link=NULL;
top=temp;
}
pop() - Deleting an Element from a Stack
• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not
possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).
void pop()
{
if(top==NULL)
printf("Underflow");
else
{
struct node *p;
p=top;
printf("Deleted item is : %d",p->data);
top=top->link;
free(p);
}
}
display() - Displaying stack of elements
• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and
terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer P and
initialize with top.
• Step 4 - Display p→ data --->' and move it to the next node.
Repeat the same until p reaches to the first node in the stack. (p→
next != NULL).
• Step 5 - Finally! Display p→ data ---> NULL

void display()
{
struct node *p;
p=top;
while(p!=NULL)
{
printf("\n%d",ptr->data);
ptr=ptr->next;
}
}
 void Enqueue(int a)
Linked Queue {
if(front==NULL)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=a;
temp->link=NULL;
#include <stdio.h> front=rear=temp;
#include <stdlib.h> }
#include<malloc.h> else
int data; {
struct node struct node *temp;
{ temp=(struct node*)malloc(sizeof(struct node));
int data; temp->data=a;
struct node *link; temp->link=NULL;
rear->link=temp;
}*front=NULL,*rear=NULL;
}
}
 void display()
void dequeue()
{
{
struct node *p;
struct node *p;
p=front;
if(front==NULL)
if(front==NULL)
printf("under flow");
printf("Under flow");
else
else
{
{
p=front;
while(ptr!=NULL)
front=front->link;
{
free(p);
printf("%d",ptr->data);
}
p=p->link;
}
}
}
}
 Queue Using Linked List
• The major problem with the queue implemented using an array is, It will
work for an only fixed number of data values.
• That means, the amount of data must be specified at the beginning itself.
Queue using an array is not suitable when we don't know the size of data
which we are going to use.
• A queue data structure can be implemented using a linked list data
structure.
• The queue which is implemented using a linked list can work for an
unlimited number of values. T
• hat means, queue using linked list can work for the variable size of data
(No need to fix the size at the beginning of the implementation).
• The Queue implemented using linked list can organize as many data values
as we want
• In linked list implementation of a queue, the last inserted node is
always pointed by 'rear' and the first node is always pointed by
'front'.
 Operations
• Step 1 - Include all the header files which are used in the program.
And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define two Node pointers 'front' and 'rear' and set both
to NULL.
• Step 4 - Implement the main method by displaying Menu of list of
operations and make suitable function calls in the main method to
perform user selected operation.
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
int data;
struct node
{
int data;
struct node *link;
}*front=NULL,*rear=NULL;
 enQueue(value) - Inserting an element into the Queue
• Step 1 - Create a newNode with given value and set 'newNode → next'
to NULL.
• Step 2 - Check whether queue is Empty (rear == NULL)
• Step 3 - If it is Empty then, set front = newNode and rear = newNode.
• Step 4 - If it is Not Empty then, set
rear → next = newNode and rear = newNode.
void Enqueue(int a)
{
if(front==NULL)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=a;
temp->link=NULL;
front=rear=temp;
}
else
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=a;
temp->link=NULL;
rear->link=temp;
}
}
deQueue() - Deleting an Element from Queue
• Step 1 - Check whether queue is Empty (front == NULL).
• Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not
possible!!!" and terminate from the function
• Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to
'front'.
• Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).
void dequeue()
{
struct node *p;
if(front==NULL)
printf("under flow");
else
{
p=front;
front=front->link;
free(p);
}
}
void display()
{
struct node *p;
p=front;
if(front==NULL)
printf("Under flow");
else
{
while(ptr!=NULL)
{
printf("%d",ptr->data);
p=p->link;
}
}
}