//singly linked list
#include<stdio.h>
#include<stdlib.h>
void insert_beg();
void insert_end();
void insert_pos();
void display();
int countNodes();
void delete_beg();
void delete_end();
void delete_pos();
void reverse();
struct node // creating node type
{
int data;
struct node *next;
};
struct node *start=NULL,*q,*t; // declaring global variables
int main()
{
int ch,count;
while(1)
{
printf("\n\n---- Singly Linked List ----");
printf("\n1.Insert\n2.Display\n3.Node count\n4.Delete\n5.Reverse\n6.Exit\n\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n---- Insert Menu ----");
printf("\n1.Insert at beginning\n2.Insert at end\n3.Insert at specified position");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert_beg();
break;
case 2: insert_end();
break;
case 3: insert_pos();
break;
default: printf("Wrong Choice!!");
}
break;
case 2: display();
break;
case 3: count=countNodes();
printf("No. of nodes= %d\n",count);
break;
case 4: printf("\n---- Delete Menu ----");
printf("\n1.Delete at beginning\n2.Delete at end\n3.Delete at specified position");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: delete_beg();
break;
case 2: delete_end();
break;
case 3: delete_pos();
break;
default: printf("Wrong Choice!!");
}
break;
case 5: reverse();
break;
case 6: exit(0);
default: printf("Wrong Choice!!");
}
}
return 0;
}
void insert_beg()
{
int num;
t=(struct node*)malloc(sizeof(struct node)); // creating new node
printf("Enter data:");
scanf("%d",&num);
t->data=num; // putting the data to the new node
if(start==NULL) // list is empty
{
t->next=NULL;
start=t;
}
else
{
t->next=start; // new node points to the start node
start=t;
}
}
void insert_end()
{
int num;
t=(struct node*)malloc(sizeof(struct node)); // creating new node
printf("Enter data:");
scanf("%d",&num);
t->data=num;
t->next=NULL;
if(start==NULL) // list is empty
{
start=t;
}
else
{
q=start;
while(q->next!=NULL) // traversing
q=q->next;
q->next=t; // last node points to the new node
}
}
void insert_pos()
{
int pos,i,num;
if(start==NULL)
{
printf("List is empty!!");
return;
}
t=(struct node*)malloc(sizeof(struct node)); // creating new node
printf("Enter data:");
scanf("%d",&num);
printf("Enter position to insert:");
scanf("%d",&pos);
t->data=num;
q=start;
for(i=1;i<pos-1;i++) // traversing to the previous node of the position node
{
if(q->next==NULL)
{
printf("There are less elements!!");
return ;
}
q=q->next;
}
t->next=q->next; // linking the new node to the next node
q->next=t; // linking the previous node to the new node
return ;
}
void display()
{
if(start==NULL)
{
printf("List is empty!!");
}
else
{
q=start;
printf("The linked list is:\n");
while(q!=NULL) // traversing
{
printf("%d->",q->data);
q=q->next;
}
}
}
int countNodes()
{
int count = 0;
struct node *temp;
temp = start;
while(temp != NULL) // traversing
{
count++;
temp = temp->next;
}
return count;
}
void delete_beg()
{
if (start == NULL)
{
printf("Underflow\n");
return;
}
struct node *ptr= start; // storing the value of the start
start=start->next; // start pointer goes to the next
free(ptr);
}
void delete_end()
{
if (start == NULL)
{
printf("Underflow\n");
return;
}
struct node *temp,*ptr= start;
while(ptr->next !=NULL) // traversing to the last node
{
temp=ptr; // storing the previous value of ptr
ptr=ptr->next;
}
if(ptr==start) // list has only one node
{
start=NULL;
}
else
temp->next=NULL; // 2nd last node points to NULL
free(ptr);
}
void delete_pos()
{
int position;
printf("\nEnter the position:");
scanf("%d",&position);
if (start == NULL)
{
printf("Underflow\n");
return;
}
if(position>countNodes())
{
printf("Position does not exist\n");
return;
}
int i=0;
struct node* temp,*ptr= start;
// traversing to the previous node of position
for(i=0;i<position-1;i++)
{
temp=ptr;
ptr=ptr-> next;
}
temp->next=ptr->next; // linking two nodes skipping one node in between
free(ptr);
}
void reverse()
{
struct node* current = start;
struct node *prev = NULL, *next;
while (current != NULL) // traversing the whole list
{
next = current->next; // next pointer goes to the next node
current->next = prev; // changing the link of the current node to previous node
prev = current; // previous node goes to the current node
current = next; // current node goes to the next node
}
start = prev; // changing the starting pointer to the last node
}//circular linked list
#include <stdio.h>
#include<stdlib.h>
#include <malloc.h>
void insert_beg();
void insert_end();
void display();
void delete_beg();
void delete_end();
struct node // creating node type
{
int data;
struct node *next; // pointer member for pointing to the next node
};
struct node *start=NULL,*ptr,*temp; // declaring the global variables
int main()
{
int ch;
while(1)
{
printf("\n\n---- Circular Linked List ----"); // main menu
printf("\n1.Insert\n2.Display\n3.Delete\n4.Exit\n\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n---- Insert Menu ----"); // insert menu
printf("\n1.Insert at beginning\n2.Insert at end");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert_beg();
break;
case 2: insert_end();
break;
default: printf("Wrong Choice!!");
}
break;
case 2: display();
break;
case 3: printf("\n---- Delete Menu ----"); // delete menu
printf("\n1.Delete at beginning\n2.Delete at end");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: delete_beg();
break;
case 2: delete_end();
break;
default: printf("Wrong Choice!!");
}
break;
case 4: exit(0);
default: printf("Wrong Choice!!");
}
}
return 0;
}
void insert_beg()
{
int num;
ptr=(struct node*)malloc(sizeof(struct node)); // creating new node
printf("Enter data:");
scanf("%d",&num);
ptr->data=num; //putting the data in the new node
if(start==NULL) // if list is empty
{
ptr->next=ptr; // the next pointer of the first node point to itself
start=ptr; // new pointer will be the start pointer
}
else // list is not empty
{
ptr->next=start; // new node point to start node
temp=start;
while(temp->next!=start) // traversing to the last node
{
temp=temp->next;
}
temp->next=ptr; // last node point to the first node
start=ptr; // new node is the first node
}
}
void insert_end()
{
int num;
ptr=(struct node*)malloc(sizeof(struct node)); // creating new node
printf("Enter data:");
scanf("%d",&num);
ptr->data=num; // putting the data in the new node
if(start==NULL) // if list is empty
{
ptr->next=ptr; // first node point to itself
start=ptr;
}
else // list is not empty
{
temp=start;
while(temp->next!=start) // traversing to ten last node
{
temp=temp->next;
}
temp->next=ptr; // last node point to the new node
ptr->next=start; // new node point to the start node
}
}
void display()
{
if(start==NULL) // list is empty
{
printf("List is empty!!");
}
else // list is not empty
{
ptr=start;
printf("The linked list is:\n");
do
{
printf("%d->",ptr->data);
ptr=ptr->next; // traversing through the whole list
}
while(ptr!=start);
}
}
void delete_beg()
{
if(start == NULL) // list is empty
{
printf("\nUNDERFLOW\n");
}
else // list is not empty
{
ptr=start; // storing the startign pointer
temp=start;
while(temp->next!=start) // traversing to the last node
{
temp=temp->next;
}
if(temp==start) // list has only one node
{
start=NULL;
}
else
{
start=start->next; // start pointer goes to the next node
temp->next=start; // last node points to start node
}
free(ptr);
}
}
void delete_end()
{
if (start == NULL) // list is empty
{
printf("\nList is empty\n");
return;
}
else // list is not empty
{
ptr=start;
while (ptr->next != start) // traversing to the last node
{
temp=ptr; // storing the previous value of ptr for getting 2nd last node
ptr=ptr->next;
}
if(ptr==start) // list has only one node
{
start=NULL;
}
else
{
temp->next=start; // 2nd last node points to the start node
}
free(ptr);
return;
}
}#include <stdio.h>
#include <stdlib.h>
void insert_beg();
void insert_pos();
void insert_end();
void delete_beg();
void delete_pos();
void delete_end();
void display();
struct node // making the structure of node
{
int data;
struct node *prev;
struct node *next;
};
struct node *head=NULL,*newnode,*temp; // declearing the global variables
int main()
{
int n,c;
while(1)
{
printf("\n****Main Menu****\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("Enter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:printf("\n---- Insert Menu ----\n");
printf("1.Insert at begining\n");
printf("2.Insert at specified position\n");
printf("3.Insert at end\n");
printf("Enter your choice:");
scanf("%d",&c);
switch(c)
{
case 1:insert_beg();
break;
case 2:insert_pos();
break;
case 3:insert_end();
break;
default:printf("Wrong choice\n");
}
break;
case 2:printf("\n---- Delete Menu ----\n");
printf("1.Delete at begining\n");
printf("2.Delete at specified position\n");
printf("3.Delete at end\n");
printf("Enter your choice:");
scanf("%d",&c);
switch(c)
{
case 1:delete_beg();
break;
case 2:delete_pos();
break;
case 3:delete_end();
break;
default:printf("Wrong choice\n");
}
break;
case 3:display();
break;
case 4:exit(0);
default:printf("Wrong choice\n");
}
}
return 0;
}
void insert_beg()
{
newnode=(struct node*)malloc(sizeof(struct node)); // creating the node
printf("Enter the data:");
scanf("%d",&newnode->data); // asking the data from the user
if(head==NULL) // if the list is empty
{
newnode->prev=NULL;
newnode->next=NULL;
head=newnode;
}
else // list is not empty
{
newnode->prev=NULL; // as this is the will be the first node
newnode->next=head; // newnode will point to the starting node
head->prev=newnode; // previous part of the starting node points to newnode
head=newnode; // haed will start from newnode
}
return ;
}
void insert_pos()
{
int pos,i;
if(head==NULL) // list is empty
{
printf("List is empty!!");
return ;
}
newnode=(struct node*)malloc(sizeof(struct node)); // creating the node
printf("Enter the position:");
scanf("%d",&pos); // asking for the position
printf("Enter the data:");
scanf("%d",&newnode->data); // asking for the data
temp=head;
for(i=1;i<pos-1;i++)
{
if(temp->next == NULL)
{
printf("Invalid position\n"); // if the position is greater than the no of node
return;
}
temp=temp->next; // traversing to the previous position node
}
newnode->prev=temp; // the previous pointer of the newnode node points to temp
newnode->next=temp->next; // the next pointer of the newnode points to next node of temp
temp->next->prev=newnode; // the previous pointer of the next node of temp points to newnode
temp->next=newnode; // the next pointer of the temp node points to newnode
return ;
}
void insert_end()
{
newnode=(struct node*)malloc(sizeof(struct node)); // creating the node
printf("Enter the data:");
scanf("%d",&newnode->data); // asking for the data
if(head==NULL) // list is empty
{
newnode->next=NULL;
newnode->prev=NULL;
head=newnode;
return;
}
temp=head; // list is not empty
while(temp->next!=NULL)
{
temp=temp->next; // traversing to the last node
}
temp->next=newnode; // the next pointer of the last node points to newnode
newnode->prev=temp; // previous pointer of the newnode will point to the last node
newnode->next=NULL; // the next pointer of the newnode points to NULL
return ;
}
void delete_beg()
{
if(head==NULL) // list is empty
{
printf("List is empty\n\n");
return;
}
else // list is not empty
{
temp=head; // storing the value of the head node
head=head->next; // head pointer goes to the next node
if(head != NULL) // if list has more than one node
head->prev=NULL; // the previous pointer of the head node points to NULL
free(temp); // deallocating the memory for the previous head node
}
return ;
}
void delete_pos()
{
if(head==NULL) // list is empty
{
printf("List is empty\n\n");
return ;
}
int pos,i; // list is not empty
printf("Enter the position:");
scanf("%d",&pos); // asking for the position for delete
temp=head;
for(i=1;i<pos-1;i++)
{
temp=temp->next; // traversing to the previous position node
}
struct node *ptr=temp->next; // declearing pointer variable and storing the address of the deleted node
temp->next=ptr->next; // the next pointer of the temp points to the next node of ptr
ptr->next->prev=temp; // the previous pointer of the next node of ptr points to temp
free(ptr);
return;
}
void delete_end()
{
if(head==NULL) // list is mepty
{
printf("List is empty\n\n");
return ;
}
struct node *ptr=head; // declearing pointer variable
while(ptr->next!=NULL)
{
temp=ptr; // storing the previous value of the ptr
ptr=ptr->next; // traversing to the last node
}
if(ptr == head) // list has only one node
head=NULL;
else // list has more than one node
temp->next=NULL; // the next pointer of the 2nd last node points to NULL
free(ptr);
return;
}
void display()
{
if(head==NULL) // list is empty
{
printf("List is empty\n\n");
return ;
}
temp=head; // list is not empty
while(temp!=NULL)
{
printf("%d ",temp->data); // printing the data for each node
temp=temp->next; // traversing to the last node
}
printf("\n\n");
return;
}#include <stdio.h>
#include <stdlib.h>
void insert_beg();
void insert_end();
void delete_beg();
void delete_end();
void display();
struct node // making the structure of node
{
int data;
struct node *prev;
struct node *next;
};
struct node *head=NULL,*newnode,*temp,*ptr; // declearing the global variables
int main()
{
int n,c;
while(1)
{
printf("\n****Main Menu****\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("Enter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:printf("\n---- Insert Menu ----\n");
printf("1.Insert at begining\n");
printf("2.Insert at end\n");
printf("Enter your choice:");
scanf("%d",&c);
switch(c)
{
case 1:insert_beg();
break;
case 2:insert_end();
break;
default:printf("Wrong choice\n");
}
break;
case 2:printf("\n---- Delete Menu ----\n");
printf("1.Delete at begining\n");
printf("2.Delete at end\n");
printf("Enter your choice:");
scanf("%d",&c);
switch(c)
{
case 1:delete_beg();
break;
case 2:delete_end();
break;
default:printf("Wrong choice\n");
}
break;
case 3:display();
break;
case 4:exit(0);
default:printf("Wrong choice\n");
}
}
return 0;
}
void insert_beg()
{
newnode=(struct node*)malloc(sizeof(struct node)); // creating the node
printf("Enter the data:");
scanf("%d",&newnode->data); // asking the data from the user
if(head==NULL) // if the list is empty
{
newnode->prev=newnode; // the previous pointer of the newnode points to itself
newnode->next=newnode; // the next pointer of the newnode points to itself
head=newnode;
}
else // list is not empty
{
temp=head;
while(temp->next!=head)
{
temp=temp->next; // traversing to the last node
}
temp->next=newnode; // the next pointer of the last node points to newnode
newnode->prev=temp; // the previous pointer of the newnode points to the last node
newnode->next=head; // newnode will point to the starting node
head->prev=newnode; // previous part of the starting node points to newnode
head=newnode; // haed will start from newnode
}
return ;
}
void insert_end()
{
newnode=(struct node*)malloc(sizeof(struct node)); // creating the node
printf("Enter the data:");
scanf("%d",&newnode->data); // asking for the data
if(head==NULL) // list is empty
{
newnode->prev=newnode; // the previous pointer of the newnode points to itself
newnode->next=newnode; // the next pointer of the newnode points to itself
head=newnode;
return;
}
temp=head; // list is not empty
while(temp->next!=head)
{
temp=temp->next; // traversing to the last node
}
temp->next=newnode; // the next pointer of the last node points to newnode
newnode->prev=temp; // previous pointer of the newnode will point to the last node
newnode->next=head; // the next pointer of the newnode points to head node
head->prev=newnode; // previous pointer of the head node will point to the last node or newnode
return ;
}
void delete_beg()
{
if(head==NULL) // list is empty
{
printf("List is empty\n\n");
return;
}
else // list is not empty
{
ptr=head; // storing the value of the head node
temp=head;
while(temp->next!=head)
{
temp=temp->next; // traversing to the last node
}
if(temp==head) // list has only one node
{
head=NULL; // list will be empty
}
else // list has more than one node
{
head=head->next; // head pointer goes to the next node
temp->next=head; // the next pointer of the last node points to new head
head->prev=temp; // the previous pointer of the head node points to last node
}
free(ptr); // deallocating the memory for the previous head node
}
return ;
}
void delete_end()
{
if(head==NULL) // list is mepty
{
printf("List is empty\n\n");
return ;
}
temp=head;
while(temp->next!=head)
{
temp=temp->next; // traversing to the last node
}
if(temp == head) // list has only one node
head=NULL;
else // list has more than one node
{
ptr=temp->prev; // storing the address of the 2nd last node
ptr->next=head; // the next pointer of the 2nd last node points to head
head->prev=ptr; // the prvious pointer of the head node points to the 2nd last node
}
free(temp);
return;
}
void display()
{
if(head==NULL) // list is empty
{
printf("List is empty\n\n");
return ;
}
temp=head; // list is not empty
while(temp->next!=head)
{
printf("%d ",temp->data); // printing the data for each node
temp=temp->next; // traversing to the last node
}
printf("%d ",temp->data); // printing the data of the last node
printf("\n\n");
return;
}
#include <stdio.h>
#include <stdlib.h>
void bubble_sort();
void insertion_sort();
void selection_sort();
int main()
{
int choice;
while(1)
{
printf("1:Bubble Sort\n2:Insertion Sort\n3:Selection Sort\n4:Exit\n");
printf("Enter choice:");
scanf("%d",&choice);
switch(choice)
{
case(1):
bubble_sort();
break;
case(2):
insertion_sort();
break;
case(3):
selection_sort();
break;
case(4):
exit(0);
default:
printf("Wrong input\n");
}
}
return 0;
}
void bubble_sort()
{
int n, i, j, temp;
printf("Enter number of elements:");
scanf("%d", &n);
int array[n];
printf("Enter %d Numbers:\n", n);
for(i = 0; i < n; i++)
scanf("%d", &array[i]); // scanning the values
for(i=0;i<n-1;i++)
{
// bringing the maximum element at the end of the list
for(j=0;j<n-i-1;j++)
{
if(array[j]>array[j+1])
{
//swapping
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
printf("Sorted list in ascending order:\n");
// printing the new sorted list
for(i=0;i<n;i++)
printf("%d ",array[i]);
printf("\n");
return;
}
void insertion_sort()
{
int n, i, j, temp;
printf("Enter number of elements:");
scanf("%d", &n);
int array[n];
printf("Enter %d Numbers:\n", n);
// scanning the elements
for(i=0;i<n;i++)
{
scanf("%d",&array[i]);
}
// traversing from 2nd position to the last
for(i=1;i<=n-1;i++)
{
j=i;
// searching for the position to insert
while(j>0 && array[j-1]>array[j])
{ // swapping two adjacent elements
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
j--;
}
/* OR we can just shift the elemets towards right after storing the
insering element into temp (Another approach) */
}
printf("Sorted list in ascending order:\n");
// printing the new sorted list
for(i=0;i<=n-1;i++)
{
printf("%d ",array[i]);
}
printf("\n");
return;
}
void selection_sort()
{
int n,i,j,min,temp;
printf("Enter number of elements:");
scanf("%d",&n);
int array[n];
printf("Enter %d Numbers:\n", n);
// scanning the elements
for(i=0;i<n;i++)
{
scanf("%d",&array[i]);
}
for(i=0;i<n-1;i++)
{
// finding the index of the minimum element
min=i;
for(j=i+1;j<n;j++)
{
if(array[min]>array[j])
min=j;
}
if(min!=i) // minimum element is not in correct position
{
// swapping two elements
temp=array[i];
array[i]=array[min];
array[min]=temp;
}
}
printf("Sorted list in ascending order:\n");
// printing the new sorted list
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf("\n");
return;
}
//merge sort
#include<stdio.h>
#include <stdlib.h>
void merge(int list[],int start,int end,int mid)
{
int left=start;
int right=mid+1;
int A[end+1]; // temporary array for storing the sorted elements
int i=start;
while(left<=mid && right<=end) // traversing by two index through the two sub array
{
if(list[left]<=list[right])
{
A[i]=list[left];
left++;
}
else
{
A[i]=list[right];
right++;
}
i++;
}
if(left>mid) // if left sub array is completed
{
while(right<=end)
{
A[i]=list[right];
i++;
right++;
}
}
else // if right sub array is completed
{
while(left<=mid)
{
A[i]=list[left];
i++;
left++;
}
}
// store back the sorted elements to the main list
for(i=start;i<=end;i++)
{
list[i]=A[i];
}
}
void merge_sort(int list[],int start,int end)
{
int mid;
if(start<end) // base condition
{
mid=(start+end)/2; // calculating middle index
merge_sort(list,start,mid); // calling the function recursively for the left sub array
merge_sort(list,mid+1,end); // calling the function recursively for the right sub array
merge(list,start,end,mid); // merging two subarray
}
}
int main()
{
int n,i;
printf("Enter the no of elements: ");
scanf("%d",&n);
int *list=(int *)malloc(n*sizeof(int));// allocating memory for array
printf("Enter the values: ");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
merge_sort(list,0,n-1); // calling the mergesort function
printf("New sorted list is:\n");
for(int i=0;i<n;i++)
{
printf("%d ",list[i]);
}
return 0;
}
//quick sort
#include <stdio.h>
#include<stdlib.h>
int partition(int A[],int start,int end)
{
int pivot=A[end],temp; // pivot is the last element of the given list
int pIndex=start;
for(int i=start;i<end;i++)
{
if(A[i]<pivot)
{
// swapping two elements
temp=A[pIndex];
A[pIndex]=A[i];
A[i]=temp;
pIndex++;
}
}
// swapping the pivot and the indexed element
A[end]=A[pIndex];
A[pIndex]=pivot;
return pIndex;
}
void quickSort(int A[],int start,int end)
{
int pIndex;
if(start<end)
{
pIndex=partition(A,start,end); // finding pivot element index
quickSort(A,start,pIndex-1); // recursively calling for the left part
quickSort(A,pIndex+1,end); // recursively calling for the right part
}
}
int main()
{
int n,i;
printf("Enter the no of elements: ");
scanf("%d",&n);
int *A=(int *)malloc(n*sizeof(int));
printf("Enter the values: ");
for(i=0;i<n;i++)
scanf("%d",&A[i]);
quickSort(A,0,n-1); // calling the function
printf("New sorted array is:\n");
for(i=0;i<n;i++)
printf("%d ",A[i]);
return 0;
}