Algorithm and functions for Linked List Operations
Algorithm to Create a Linked List
1. Begin
2. Declare: struct node *q, *t
3. If start=NULL, then
(a) Set start=Assign memory address using malloc() function
(b) Set start->data =num [Insert num into data field of node]
(c) Set start->next =NULL
4. Else
(a) Set q=start [Assign the address of first node in another pointer]
(b) Repeat until q->next !=NULL
Set q=q->next
[End of while Loop]
(c) [Add node at the end] Set t=Assign memory address using malloc() function
(d) Set t->data=num
(e) Set t->next=NULL
(f) Set q->next=t
[End of If structure]
5. Return
Function to Create a Singly Linked List
void create(int num)
{
struct node *q,*temp;
if(start==NULL)
{
start=(struct node*)malloc(sizeof(struct node));
start->item=num;
start->next=NULL;
}
else
{
q=start;
//Go to the last node
while(q->next!=NULL)
q=q->next;
//Add node at the end of the list
temp=(struct node*)malloc(sizeof(struct node));
temp->item=num;
temp->next=NULL;
q->next=temp;
}
}
Algorithm to Display a Linked List
1. Begin
2. Declare: struct node *q
3. If start=NULL, then
Write: "List is empty" and exit
4. Set q=start [Starting address to the pointer variable q]
5. Repeat steps (a) and (b) while q!=NULL
(a) Print: q->data
(b) Set q=q->next
[End of while loop]
6. Return
Function to Display Linked List Elements
void display()
{
struct node *q;
if(start==NULL)
{
printf("No element in the linked list");
return;
}
else
{
printf("\nItems in the linked list:");
for(q=start;q!=NULL;q=q->next)
printf("\t%d",q->item);
}
}
Algorithm for counting the nodes in a linked list
1. Begin
2. Declare: struct node *q
3. Set n=0
4. Repeat for q=start to NOT NULL by q=q->next
Set n=n+1
[End of for loop]
5. Print the value of n
6. Return
Function to count the number of nodes in a linked list
void count()
{
struct node *q;
int n=0;
for(q=start;q!=NULL;q=q->next)
n++;
printf("\n Number of nodes:%d",n);
}
Algorithm to add a node at beginning in a linked list
1. Begin
2. Declare: struct node *q
3. Set q=Assign memory address using malloc() function
4. Set q->data =num [Insert num into data field of node]
5. Set q->next=start
6. Set start=q
7. Return
Function to add a node at beginning in a linked list
void addbeg(int num)
{
struct node *q;
q=(struct node*)malloc(sizeof(struct node));
q->item=num;
q->next=start;
start=q;
}
Algorithm to add a node after specified position in a linked list
1. Begin
2. Declare: struct node *q,*t
3. [Skip to the desired position]
Set q=start [Assign the address of first node in another pointer]
4. Repeat steps (a) and (b) for i=0 to pos
(a) Set q=q->next
(b) If q=NULL, then
Write: "There is no element in linked list" and return
[End of for loop]
5. Set t=Assign memory address using malloc() function
6. Set t->data=num [Insert num into data field of new node]
7. Set t->next =q->next
8. Set q->next =t
9. Return
Function to add a node after specified position in a linked list
void addspec(int pos,int num)
{
struct node *q,*temp;
int i;
//skip to the desired position
q=start;
for(i=1;i<pos-1;i++)
q=q->next;
//Insert new node at particular location
temp=(struct node*)malloc(sizeof(struct node));
temp->item=num;
temp->next=q->next;
q->next=temp;
}
Algorithm to delete a specified node from a linked list
1. Begin
2. Declare: struct node *q, *t
3. Set q=start [Assign the address of first node in another pointer]
4. If q=NULL, then: "List is Empty" and return
5. If q->data =num, then [Node to be removed is first node]
(a) Set start=q->next
(b) Write: "Element removed"
(c) free(q) and return [Release memory using free function]
[End of If structure]
6. Set t=q and q=q->next
7. Repeat step 8 while q!=NULL [Traverse list till the last]
8. If q->data=num
(a) Set t->next =q->next
(b) Write: "Item Removed"
(c) free(q) [Release memory using free function]
(d) return
Else
(a) Set t=q
(b) Set q=q->next
[End of while loop]
9. Write : "Item is not found"
10. Return
Function to delete a specified node from a linked list
void del(int num)
{
struct node *q,*temp;
q=start;
if(q==NULL)
{
printf("The list is empty");
return;
}
//Node to be removed is first node
if(q->item==num)
{
start=q->next;
printf("Element Removed");
free(q);
return;
}
//Traverse List till the last node
temp=q;
while(q!=NULL)
{
if(q->item==num)
{
temp->next=q->next;
printf("Item Removed");
free(q);
return;
}
temp=q;
q=q->next;
}
printf("\nItem=%d is not found",num);
}
Algorithm to search a node element in a singly linked list
1. Begin
2. Declare: struct node *q
3. Set q=start, loc =1
4. Repeat step 5 while q!=NULL
5. If q->data=num
(a) Write : "Element num is found at position LOC"
(b) return
Else
Set q=q->next and loc= loc +1
[End of If Else]
[End of while loop]
6. Write: "Element Not Found"
7. Return
Function to search a node element in a singly Linked List
void search(int num)
{
struct node *q;
int loc=1;
q=start;
while(q!=NULL)
{
if(q->item==num)
{
printf("Item %d found at location%d\n",num,loc);
return;
}
else
{
q=q->next;
loc++;
}
}
printf("Item %d not found in the list",num);
}
Function to reverse a singly Linked List
void reverse()
{
struct node *p1,*p2,*p3;
if(start->next==NULL) //Only one element
return;
p1=start;
p2=p1->next;
p3=p2->next;
p1->next=NULL;
p2->next=p1;
while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->next;
p2->next=p1;
}
start=p2;
}
Function to sort a linked list by using bubble sort method
void bubblesort()
{
struct node *q,*r,*p,*s;
p=s=start;
while(s!=NULL)
{
for(q=start;q->next!=NULL;q=q->next)
{
if(p->item>q->next->item)
{
r->item=p->item;
p->item=q->next->item;
q->next->item=r->item;
}
p=p->next;
}
q=p=start;
s=s->next;
}
}
Function to sort the nodes of linked list by using selection sort method
void selectionsort()
{
struct node *q,*r,*p;
p=start;
while(p!=NULL)
{
for(q=start;q!=NULL;q=q->next)
{
if(p->item<q->item)
{
r->item=p->item;
p->item=q->item;
q->item=r->item;
}
}
p=p->next;
}
}
Function to find even odd number in a singly Linked list
void evenodd()
{
struct node *q;
int esum=0,osum=0,tsum=0,ec=0,oc=0;
q=start;
while(q!=NULL)
{
if(q->item%2==0)
{
esum=esum+q->item;
ec++;
}
else
{
osum=osum+q->item;
oc++;
}
tsum=esum+osum;
q=q->next;
}
printf("\nTotal Even Nodes:%d",ec);
printf("\nTotal Odd Nodes:%d",oc);
printf("\nEven Numbers Total:%d",esum);
printf("\nOdd Numbers Total:%d",osum);
printf("\nTotal Sum:%d",tsum);
}