//FUNCTION: INSERT AT HEAD (BEGINNING)
Program:
void insert_from_head(int x)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//if head is NULL, it is an empty list
if (head == NULL)
{
head = ptr;
}
else
{
ptr->next = head;
head = ptr;
}
}
Algorithm:
Step 1: [Underflow?]
If AVAIL = NULL
then Write(‘AVAIBILITY STACK UNSERFLOW’)
Return(FIRST)
Step 2: [Obtain address of next free node]
NEW ← AVAIL
Prepared by: Komal Langalia
Step 3: [Remove free node from availability stack]
AVAIL ← LINK(AVAIL)
Step 4: [Initialize the fields of new node and its link to the list]
INFO(NEW) ← X
LINK(NEW) ← FIRST
Step 5: [Return address of new node]
Return(NEW)
//FUNCTION: INSERT AT TAIL (ENDING)
Program:
void insert_from_tail(int x)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//if head is NULL, it is an empty list
if (head == NULL)
head = ptr;
//Otherwise, find the last node and add the newly created node ptr
else
{
struct node *last = head;
//last node's next address will be NULL.
while(last->next!= NULL)
{
Prepared by: Komal Langalia
last = last->next;
}
//add ptr at the end of the linked list
last->next = ptr;
}
}
Algorithm:
Step 1: [Underflow?]
If AVAIL = NULL
then Write(‘AVAIBILITY STACK UNSERFLOW’)
Return(FIRST)
Step 2: [Obtain address of next free node]
NEW ← AVAIL
Step 3: [Remove free node from availability stack]
AVAIL ← LINK(AVAIL)
Step 4: [Initialize fields of new node]
INFO(NEW) ← X
LINK(NEW) ← NULL
Step 5: [Is the list empty?]
If FIRST = NULL
then Return(NEW)
Step 6: [Initiate/Search for the last node]
SAVE ← FIRST
Step 7: [Search end of the list]
Prepared by: Komal Langalia
Repeat While LINK(SAVE) ≠ NULL SAVE ← LINK(SAVE)
Step 8: [Set LINK Field of last node to NEW]
LINK(SAVE) ← NEW
Step 9: [Return first node pointer]
Return(FIRST)
//FUNCTION: INSERT NODE AT PARTICULAR POSITION
Program:
void insert_at_position(int place, int k)
{
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = k;
ptr->next = NULL;
if(head==NULL)
{
head = ptr;
return;
}
//consider position is starting with 0. That is 0 means 1st node
if(place == 0)
{
ptr->next = head;
head = ptr; //same as insert at head
return;
}
Prepared by: Komal Langalia
else// else is optional if you have used return in if block
{
count = 1;
struct node *pos;
pos = head;
while(count< place)
{
count++;
pos = pos->next;
}
ptr->next = pos->next;
pos->next = ptr;
}
}
//FUNCTION: INSERT INTO SORTED LINKED
LIST(ORDERED in ASC way)
Program:
void insertion_sorted_LL()//function to insert data in sorted position
{
int k;
printf("\nEnter data you want to insert: ");
scanf("%d",&k);
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = k;
ptr->next = NULL;
//If linked list is empty
if (head == NULL)
{
Prepared by: Komal Langalia
head = ptr;
return;
}
if (head->data >= k)
{
ptr->next = head;
head = ptr;
return;
}
//Locate the node before insertion
struct node *q = head;
while (q->next != NULL && q->next->data <= ptr->data)
q = q->next;
ptr->next = q->next;
q->next = ptr;
}
Algorithm:
Step 1: [Underflow?]
If AVAIL = NULL
then Write(‘AVAIBILITY STACK UNSERFLOW’)
Return(FIRST)
Step 2: [Obtain address of next free node]
NEW ← AVAIL
Step 3: [Remove free node from availability stack]
AVAIL ← LINK(AVAIL)
Step 4: [Copy information contents into new node]
INFO(NEW) ← X
Step 5: [Is the list empty?]
If FIRST = NULL
then LINK(NEW) ← NULL
Prepared by: Komal Langalia
Return(NEW)
Step 6: [Does the new node precede all others in the list?]
If INFO(NEW) ≤ INFO(FIRST)
then LINK(NEW) ← FIRST
Return(NEW)
Step 7: [Initialize temporary pointer]
SAVE ← FIRST
Step 8: [Search for predecessor of new node]
Repeat While LINK(SAVE) ≠ NULL and INFO(LINK(SAVE)) ≤ INFO(NEW)
SAVE ← LINK(SAVE)
Step 9: [Set link fields of new node and its predecessor]
LINK(NEW) ←LINK(SAVE)
LINK(SAVE) ← NEW
Step 10: [Return First node pointer]
Return(FIRST)
Note that:
For all these algorithms
FIRST is head in our program,
NEW means our ptr (newly created node),
SAVE is temporary struct node pointer,
LINK(NODENAME) is nodename->next and
INFO(NODENAME) is nodename->data.
//Insertion in singly LinkedList (Whole program)
#include <stdio.h>
#include <stdlib.h>
int count;
struct node{
int data;
struct node *next;
Prepared by: Komal Langalia
} *head=NULL;
void insert_from_head(int x)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//if head is NULL, it is an empty list
if (head == NULL){
head = ptr;}
else {
ptr->next = head;
head = ptr;
}
}
void insert_from_tail(int x)//Also called insertion from tail(last)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//if head is NULL, it is an empty list
if (head == NULL){
head = ptr;}
Prepared by: Komal Langalia
//Otherwise, find the last node and add the newly created Node ptr
else {
struct node *last = head;
//last node's next address will be NULL.
while(last->next!= NULL)
{
last = last->next;
}
//add the new Node ptr at the end of the linked list
last->next = ptr;
}
}
void insert_at_position(int place, int k)
{
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = k;
ptr->next = NULL;
if(head==NULL)
{
head = ptr;
return;
}
//consider position is starting with 0. That is 0 means 1st node
if(place == 0)
{
Prepared by: Komal Langalia
ptr->next = head;
head = ptr; //same as insert at head
return;
}
else// else is optional if you have used return in if block
{
count = 1;
struct node *pos;
pos = head;
while(count< place)
{
count++;
pos = pos->next;
}
ptr->next = pos->next;
pos->next = ptr;
}
}
void insertion_sorted_LL(int x)//function to insert data in sorted position
{
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//If linked list is empty
if (head == NULL) {
head = ptr;
return;
}
Prepared by: Komal Langalia
if (head->data >= x)
{
ptr->next = head;
head = ptr;
return;
}
//Locate the node before insertion
struct node *q = head;
while (q->next != NULL && q->next->data <= ptr->data)
q = q->next;
ptr->next = q->next;
q->next = ptr;
}
void display()//function to print linked list
{
struct node *p = head;
while (p)
{
printf("%d ",p->data);
p = p->next;
}
printf("NULL");
}
int main()
{
Prepared by: Komal Langalia
int choice,k;
int i,data[100]={3, 6, 9, 12, 30};
for(i=0;i<5;i++)
{
insertion_sorted_LL(data[i]);
}
printf("Linked list before deletion : \n");
display();
printf("\nEnter Choice of Insertion: ");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\nEnter node data :");
scanf("%d", &k);
insert_from_head(k);
break;
case 2: printf("\nEnter node data :");
scanf("%d", &k);
insert_from_tail(k);
break;
case 3: int place;
printf("\nEnter position of the node:");
scanf("%d", &place);
printf("\nEnter node data :");
scanf("%d", &k);
delete_at_position(place,k);
break;
case 4: printf("\nEnter node data :");
scanf("%d", &k);
insertion_sorted_LL(k);
Prepared by: Komal Langalia
break;
default: printf("\nEnter valid choice.");
}
printf("Linked list after deletion : \n");
display();
return 0;
}
//FUNCTION: DELETE AT HEAD (BEGINNING)
Program:
void delete_from_head()
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
}
struct node *del;
del = head;
head = head->next;
free(del);
}
//FUNCTION: DELETE AT TAIL (ENDING)
Program:
void delete_from_tail()
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
return;
}
Prepared by: Komal Langalia
struct node *del, *q;
q = head;
del = q->next;
while(del->next)
{
del = del->next;
q = q->next;
}
free(del);
q->next=NULL;
}
//FUNCTION: DELETE NODE AT PARTICULAR POSITION
Program:
void delete_at_position(int x)
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
}
//consider position is starting with 0. That is 0 means 1st node
if(x == 0)
{
struct node *del;
del = head;
head = head->next;
free(del);
return;
}
else// else is optional if you have used return in if block
{
Prepared by: Komal Langalia
count = 1;
struct node *del, *q;
q = head;
del = q->next;
while(count< x)
{
count++;
del = del->next;
q = q->next;
}
q->next = del->next;
free(del);
}
}
//FUNCTION: DELETE PARTICULAR VALUE
Program:
void deleteValue(int x)
{
struct node *del, *q;
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
return;
}
if(head->data == x)
{
del = head;
Prepared by: Komal Langalia
head = head->next;
free(del);
return;
}
q = head;
del = q->next;
while(del->data != x)
{
if(del->next==NULL)
{
printf("\nData not found.");
}
del = del->next;
q = q->next;
}
q->next = del->next;
free(del);
}
Algorithm:
Step 1: [Empty List?]
If FIRST = NULL
then Write(‘Underflow’)
Return
Step 2: [Initialize search for X]
TEMP ← FIRST
Step 3: [Find X]
Repeat thru step 5 while TEMP ≠ X and LINK(TEMP) ≠ NULL
Step 4: [Update predecessor marker]
PRED ← TEMP
Prepared by: Komal Langalia
Step 5: [Move to next node]
TEMP ← LINK(TEMP)
Step 6: [End of List?]
If TEMP ≠ X
then Write (‘Node Not Found’)
Return
Step 7: [Delete X]
If X = FIRST (Is X the first node?) then
FIRST ← LINK(FIRST)
else
LINK(PRED) ← LINK(X)
Step 8: [Return node to availability Area]
LINK(X) ← AVAIL
AVAIL ← X
Return
//Deletion in Singly LinkedList (Whole program)
#include <stdio.h>
#include <stdlib.h>
int count;
struct node{
int data;
struct node *next;
} *head=NULL;
void createList(int x)//Also called insertion from tail(last)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
Prepared by: Komal Langalia
//if head is NULL, it is an empty list
if (head == NULL){
head = ptr;
}
//Otherwise, find the last node and add the newly created Node ptr
else
{
struct node *last = head;
//last node's next address will be NULL.
while(last->next!= NULL)
{
last = last->next;
}
//add the new Node ptr at the end of the linked list
last->next = ptr;
}
}
void display()//function to print linked list
{
struct node *ptr = head;
while (ptr)
{
printf("%d ",ptr->data);
ptr = ptr->next;
}
printf("NULL");
}
Prepared by: Komal Langalia
void deletefirst()
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
}
struct node *del;
del = head;
head = head->next;
free(del);
}
void deletelast()
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
return;
}
struct node *del, *q;
q = head;
del = q->next;
while(del->next)
{
del = del->next;
q = q->next;
}
free(del);
q->next=NULL;
}
Prepared by: Komal Langalia
void delete_at_position(int x)
{
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
}
//consider position is starting with 0. That is 0 means 1st node
if(x == 0)
{
struct node *del;
del = head;
head = head->next;
free(del);
return;
}
else// else is optional if you have used return in if block
{
count = 1;
struct node *del, *q;
q = head;
del = q->next;
while(count< x)
{
count++;
del = del->next;
q = q->next;
}
q->next = del->next;
free(del);
Prepared by: Komal Langalia
}
}
void deleteValue(int x)
{
struct node *del, *q;
if(head==NULL)
{
printf("\nLinkedList Underflow on deletion");
return;
}
if(head->data == x)
{
del = head;
head = head->next;
free(del);
return;
}
q = head;
del = q->next;
while(del->data != x)
{
if(del->next==NULL)
{
printf("\nData not found.");
}
del = del->next;
q = q->next;
}
q->next = del->next;
Prepared by: Komal Langalia
free(del);
}
int main()
{
int choice,k;
int i,data[100]={3, 6, 9, 12, 30};
for(i=0;i<5;i++)
{
createList(data[i]);
}
printf("Linked list before deletion : \n");
display();
printf("\nEnter Choice of deletion: ");
scanf("%d", &choice);
switch(choice)
{
case 1: deletefirst(); break;
case 2: deletelast(); break;
case 3: printf("\nEnter position of the node to be deleted :");
scanf("%d", &k);
delete_at_position(k);
break;
case 4: printf("\nEnter data to be deleted :");
scanf("%d", &k);
deleteValue(k);
break;
default: printf("\nEnter valid choice.");
}
printf("Linked list after deletion : \n");
Prepared by: Komal Langalia
display();
return 0;
}
//FUNCTION FOR TRAVERSAL OF SINGLY LINKEDLIST
Program:
void traverse ()
{
struct node *p = head;
printf("\n\nList elements are - \n");
while (p! = NULL)
{
printf("%d -->",p->data);
p = p->next;
}
printf("NULL");
}
Algorithm:
STEP 1: SET PTR = FIRST
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 6
END OF IF
STEP 3: REPEAT STEP 4 AND 5 UNTIL PTR!= NULL
STEP 4: PRINT PTR→ DATA
STEP 5: PTR = PTR → NEXT
[END OF LOOP]
STEP 6: EXIT
//Write a C program to implement copy() operation in singly
LinkedList
Program:
#include <stdio.h>
#include <stdlib.h>
// Node for linked list
struct node {
Prepared by: Komal Langalia
int data;
struct node* next;
}*head1=NULL,*head2=NULL;
// Function to print given linked list
void display(struct node *p)
{
while(p)
{
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL");
}
// Function to create a new node
void insert_LL(int x)//Also called insertion from tail(last)
{
//create a new node
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
//if head is NULL, it is an empty list
if (head1 == NULL){
head1 = ptr;}
//Otherwise, find the last node and add the newly created Node ptr
else {
struct node *last = head1;
Prepared by: Komal Langalia
//last node's next address will be NULL.
while(last->next!= NULL)
{
last = last->next;
}
//add the new Node ptr at the end of the linked list
last->next = ptr;
}
}
// Function to create a copy of a linked list
struct node *copyList(struct node *sourceList)
{
if(sourceList==NULL)
{
return NULL;
}
struct node *targetList = (struct node *) malloc(sizeof(struct node));
targetList->data=sourceList->data;
targetList->next=copyList(sourceList->next);
return targetList;
}
// Driver Code
int main(void)
{
// Given nodes value
int data[] = { 1, 2, 3, 4, 5 };
int i;
Prepared by: Komal Langalia
for(i=0;i<5;i++)
{
insert_LL(data[i]);
}
display(head1);
// Head of the duplicate nexted List
head2 = copyList(head1);
display(head2);
return 0;
}
//Write a C program to implement a stack
Program:
#include <stdio.h>
#include <stdlib.h>
int size,count;
// Node for linked list
struct node {
int data;
struct node* next;
}*head=NULL;
void push(int x)//insert_from_head
{
if(count == size)
{
printf("\nStack overflow over push");
return;
}
struct node *ptr;
Prepared by: Komal Langalia
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
if (head == NULL)
{
head = ptr;
}
else
{
ptr->next = head;
head = ptr;
}
count ++;
}
void pop()//delete_from_head
{
if(head==NULL)
{
printf("\nStack underflow on pop");
}
struct node *del;
del = head;
head = head->next;
free(del);
count--;
}
void display()
{
Prepared by: Komal Langalia
struct node *p;
p = head;
while(p)
{
printf("%d-",p->data);
p = p->next;
}
}
int main()
{
int choice=0,k;
printf("Enter the size of stack:");
scanf("%d", &size);
while(choice != 3)
{
printf("\nEnter Choice of Operation: ");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\nEnter data to be pushed :");
scanf("%d", &k);
push(k);
printf("\nStack after operation push is: \n");
display();
break;
case 2: pop();
printf("\nStack after operation pop is: \n");
display();
break;
Prepared by: Komal Langalia
case 3: exit(0);
default: printf("\nEnter valid choice.");
}
}
return 0;
}
//Write a C program to implement a queue
Program:
#include <stdio.h>
#include <stdlib.h>
int size,count;
// Node for linked list
struct node {
int data;
struct node* next;
}*head=NULL;
void enqueue(int x)//insert_from_tail
{
if(count == size)
{
printf("\nStack overflow over enqueue");
return;
}
struct node *ptr;
ptr = (struct node *)malloc (sizeof(struct node));
ptr->data = x;
ptr->next = NULL;
Prepared by: Komal Langalia
if (head == NULL)
head = ptr;
else
{
struct node *last = head;
while(last->next!= NULL)
{
last = last->next;
}
last->next = ptr;
}
count ++;
}
void dequeue()//delete_from_head
{
if(head==NULL)
{
printf("\nStack underflow on dequeue");
}
struct node *del;
del = head;
head = head->next;
free(del);
count--;
}
void display()
{
struct node *p;
Prepared by: Komal Langalia
p = head;
while(p)
{
printf("%d-",p->data);
p = p->next;
}
}
int main()
{
int choice=0,k;
printf("Enter the size of stack:");
scanf("%d", &size);
while(choice != 3)
{
printf("\nEnter Choice of Operation: ");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\nEnter data to be pushed :");
scanf("%d", &k);
enqueue(k);
printf("\nStack after operation enqueue is: \n");
display();
break;
case 2: dequeue();
printf("\nStack after operation dequeue is: \n");
display();
break;
case 3: exit(0);
default: printf("\nEnter valid choice.");
Prepared by: Komal Langalia
}
}
return 0;
}
//Find Length of a Linked List (Iterative and Recursive)
Prepared by: Komal Langalia
