Data Structures Programs
1: Write a C program that uses functions to
perform the following:
a)
Create
a singly linked list of integers.
b)
Delete
a given integer from the above linked list.
c)
Display
the contents of the above list after deletion.
AIM: Implement
the Single linked List
Algorithms:
Inserting
a node into SLL:
Algorithm:
Insert
at front()
{
Allocate a memory for new node(new1) if
(new1== NULL) then
display
memory is full (insertion is not possible)
end if else
read
element ele;
new1->data=ele;/*copy the data into
new1 node */ new1->next=header->next;
header->next=new1;
end else
}
Algorithm:
Insert
at End()
{
Allocate
a memory for new node(new1) if(new1== NULL) then
display memory is
full (insertion is not possible)
end
if else
ptr=header
while(ptr->next!=NULL
)/*ptr moves end of list */ then
ptr=ptr->next
end
new1->next=NULL new1->data=ele ptr->next=new1
end else
}
Algorithm: Insert at middle ()
{
Allocate
a memory for new node(new1)
if
(new1== NULL)
display
memory is full (insertion is not possible)
exit
else
read ele,pos ptr=header count=0
while(ptr->next!=NULL)
{
ptr=ptr->next;
count ++;
}
if(count<pos-1)
then
display position
is not of range
end
ptr=header count=0
while(count<pos-1)
then
ptr=ptr->next
count++
end
new1->data=ele
new1->next=ptr->next
ptr->next=new1
end else
}
Deleting
a node from the SLL: Algorithm: Delete at front()
{
if
(header->next==NULL) then
display
list is empty
end
if else
temp=header->next;
header->next=header->next->next; free(temp);
end
if
}
Algorithm:
Delete
at end()
{
if(header->next==NULL)
then
display list is
empty
end
if else
ptr=header;
while(ptr->next->next!=NULL)
{
ptr->=Ptr->next;
}
temp=ptr->next;
ptr->next=NULL; free(temp);
end else
}
Algorithm:delete
at anyposition()
{
if
(header->next==NULL) then
display
list is empty /*deletion is not
possible*/
end
if ptr=header; count=0;
while(ptr->next!=NULL)
{
ptr=ptr->next;
count++;
}
if(count<pos-1)
{
Display position
is out of range
}
ptr=header;
count=0;
while(count<pos-1)
{
ptr=ptr->next;
count++;
}
temp=ptr->next;
ptr->next=temp->next; free(temp)
}
Traversing a List: Algorithm:Traverse()
{
ptr=header;
if(ptr
->next==NULL)
then
display list is empty end if
else
while(ptr -> next!=NULL)
{
display
ptr-> data
ptr=ptr -> next /* move to next
node */
}
end
if
}
--------------------------------------------------------------------------------------------------------------------------Program:
/*Implement a SLL*/ #include<stdio. h> #include<stdlib. h>
struct node
{
int data;
struct node *next; };
struct node *header=NULL; struct node *ptr=NULL,*temp=NULL;
void create();
void insert_at_front(); void insert_at_end(); void insert_at_ middle(); void delete_at_front(); void delete_at_end(); void delete_at_middle(); void display();
int main()
{
int ch;
header=(struct node*)malloc(sizeof(struct node)); header->next=NULL;
ptr=header;
//clrscr();
printf("\n\n1.create \n2- insert at front\n3- insert at middle\n4- insert at end\n5-display\n6.delete_at_front\n7.delete_at_middle\n8.delete_at_end\n9-exit");
while(1)
{
printf("\nenter ur choice : "); scanf("%d",&ch); switch(ch)
{
case 1: create(); break;
case 2: insert_at_front(); break;
case 3: insert_at_middle(); break;
case 4: insert_at_end(); break;
case 5: display(); break;
case 6: delete_at_front(); break;
case 7: delete_at_middle(); break;
case 8: delete_at_end(); break;
case 9: exit(0);
default: printf("wrong choice");
}
}
}
void create()
{
char ch; while(1)
{
insert_at_end();
printf("if u want to continue press 'y' or 'n' :"); scanf("\n%c",&ch);
if(ch=='y'||ch=='Y')
continue;
else
break;
}
}
void insert_at_front()
{
int ele;
struct node *new1;
new1=(struct node*)malloc(sizeof(struct node)); if(new1==NULL)
{
printf("out of space"); return;
}
printf("enter ele:"); scanf("%d",&ele); new1->next=header->next; header->next=new1; new1->data=ele; printf("inserted successfully");
}
void insert_at_end()
{
struct node *new1; int ele;
new1=(struct node*)malloc(sizeof(struct node));
ptr=header;
if(new1==NULL)
{
printf("out of space"); return;
}
printf("enter Inserted ele:"); scanf("%d",&ele);
/* Move the pointer to upto end of the node*/ while(ptr->next!=NULL)
{
ptr=ptr->next;
}
new1->next=NULL; ptr->next=new1; new1->data=ele; printf("inserted successfully");
}
void insert_at_middle()
{
struct node *new1; int ele;
int pos,count=0;
new1=(struct node*)malloc(sizeof(struct node)); ptr=header;
if(new1==NULL)
{
printf("out of space"); return;
}
printf("enter Inserted ele:"); scanf("%d",&ele);
printf("enter where it to be inserted at what position number:"); scanf("%d",&pos);
/* Calculate the no of elements in the list */ while(ptr->next!=NULL)
{
count++; ptr=ptr->next;
}
/*Compare the entered positions number is valid or not using count the no.of elements in the list*/
if(count<pos)
{
printf("pos is out of range"); return;
}
ptr=header;
count=0;
/*Move the ptr upto particular entered position number*/ while(count<pos-1)
{
ptr=ptr->next; count++;
}
new1->next=ptr->next; ptr->next=new1; new1->data=ele; printf("inserted successfully");
}
void display()
{
ptr=header;
/* Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list is empty"); return;
}
while(ptr->next!=NULL)
{
printf("%d -> ",ptr->next->data); ptr=ptr->next;
}
printf("NULL");
}
void delete_at_front()
{
ptr=header;
/* Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list is empty deletion is not possible"); return;
}
temp=ptr->next; ptr->next=ptr->next->next; free(temp);
printf("deleted succssfully");
}
void delete_at_end()
{
ptr=header;
/* Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list is empty deletion is not possible"); return;
}
/*Move the ptr upto last but one node*/ while(ptr->next->next!=NULL)
{
ptr=ptr->next;
}
temp=ptr->next; ptr->next=NULL;
free(temp); /* Clear the Memory*/ printf("deleted succssfully");
}
void delete_at_middle()
{
int pos,count; ptr=header;
/* Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list is empty deletion is not possible"); return;
}
count=0;
/* Calculate the no.of elements in the list */ while(ptr->next!=NULL)
{
ptr=ptr->next; count++;
}
printf("enter deleted position number:"); scanf("%d",&pos);
/*Compare the entered positions number is valid or not using count the no.of elements in the list*/
if(count<pos)
{
printf("position is out of range"); return;
}
ptr=header;
count=0;
/*Move the ptr upto particular entered position number*/ while(ptr->next->next!=NULL&&count<pos-1)
{
ptr=ptr->next; count++;
}
temp=ptr->next; ptr->next=ptr->next->next; free(temp);
printf("deleted succssfully");
}
OUTPUT:
1.create
2- insert at front
3-insert at middle
4-insert at end
5-display 6.delete_at_front 7.delete_at_middle 8.delete_at_end 9-exit
enter ur choice : 1 enter Inserted ele:10
inserted successfullyif u want to continue press 'y' or 'n' :y enter Inserted ele:20
inserted successfullyif u want to continue press 'y' or 'n' :y enter Inserted ele:30
inserted successfullyif u want to continue press 'y' or 'n' :n
enter ur choice : 5
10 -> 20 -> 30 -> NULL
enter ur choice : 2 enter ele:15
inserted successfully
enter ur choice : 5
15 -> 10 -> 20 -> 30 -> NULL
enter ur choice : 3 enter Inserted ele:25
enter where it to be inserted at what position number:2 inserted successfully
enter ur choice : 5
15 -> 25 -> 10 -> 20 -> 30 -> NULL
enter ur choice : 4
enter Inserted ele:3
5 inserted successfully
enter ur choice : 5
15 -> 25 -> 10 -> 20 -> 30 -> 35 -> NULL
enter ur choice : 6
deleted succssfully
enter ur choice : 5
25 -> 10 -> 20 -> 30 -> 35 -> NULL
enter ur choice : 7
enter deleted position number:2 deleted succssfully
enter ur choice : 5
25 -> 20 -> 30 -> 35 -> NULL
enter ur choice : 8
deleted succssfully
enter ur choice : 5
25 -> 20 -> 30 -> NULL
enter ur choice : 9 */