Experiment No.
6
Implement Singly Linked List
ADT
Date of Performance:5/9
Date of Submission:23/9
Experiment No. 6: Singly Linked List Operations
Aim: Implementation of Singly Linked List
Objective:
It is used to implement stacks and queues which are like fundamental needs throughout computer
science. To prevent the collision between the data in the hash map, we use a singly linked list.
Theory :
A linked list is a ordered collection of finite, homogenous elements referred as a node.
Each node consist of two fields: one field for data which is referred as information and other
field is an address field to store the address of next element in the list.
The address field of last node contains null value to indicate the end of list. The elements
of linked list are not stored in continuous memory location but they are scattered, and still
bounded to each other by an explicit link
The structure of linked list is as shown below
12 null
Header is a node containing null in its information field and an next address field
contains the address of first data node in the list. Various operations can be performed on singly
linked list like insertion at front, end and at specified position , deletion at front, end and at
specified position, traversal, copying and merging.
Algorithm
Algorithm : INSERT_SPECIFIED(Header, X, Key)
Input : Header is a pointer to header node. X is a data of node to be inserted and Key is data of
node after which insertion is to be done.
Output :A singly linked list enriched with newly inserted node.
Data Structure : A singly linked list whose address of starting node is in Header. And two fields
info and next to point to data field and address field respectively. ptr is used to an address of
current node
1. new = GETNODE()
2. if new = NULL then
print “Insufficient Memory”
Exit
3. else
ptr = HEADER
while info(ptr)!= Key AND next(ptr)!= NULL do
ptr = next(ptr)
end while
3. if next(ptr) = NULL then
print “Key not found”
exit
4. else
next(new) = next(ptr)
info(new) = x
next(ptr) = new
end if
end if
5. stop
Algorithm : DELETE_SPECIFIED(Header, Key)
Input : Header is a pointer to header node. Key is data of node after which is to be deleted.
Output :A singly linked list with removed node.
Data Structure : A singly linked list whose address of starting node is in Header. And two fields
info and next to point to data field and address field respectively. ptr is used to an address of
current node
1. ptr1 = HEADER
ptr = next(ptr1)
2. while ptr!= NULL do
if info(ptr) != Key
ptr1 = ptr
ptr = next(ptr)
else
next(ptr1) = next(ptr)
print(info(ptr))
FREENODE(ptr)
End if
End while
3. if ptr = NULL then
print “ key not found”
end if
4. stop
Algorithm : TRAVERSAL(Header)
Input : Header is a pointer to header node.
Output :A singly linked list is traversed and its data value is printed.
Data Structure : A singly linked list whose address of starting node is in Header. And two fields
info and next to point to data field and address field respectively. ptr is used to an address of
current node
1. ptr = next(HEADER)
2. while ptr!= NULL do
print (Info(ptr))
End while
3. stop
Code:#include<stdio.h>
#include<conio.h>
struct node{
int data;
struct node *next;
};
struct node *head=0;
struct node *createnode()
struct node *h1;
h1=(struct node*)malloc(sizeof(struct node));
printf("Enter a data");
scanf("%d",&h1->data);
h1->next=0;
return h1;
void iB()
struct node *N1;
N1=createnode();
if(head==0)
head=N1;
}
else
N1->next=head ;
head=N1;
void display()
struct node*j1;
j1=head;
while(j1!=0)
printf("%d",j1->data);
j1=j1->next;
void dB()
struct node*temp;
if(head==0)
printf("underflow");
else{
temp=head;
head=head->next;
temp->next=0;
free(temp);
void iE()
struct node*N2;
struct node*temp1;
N2=createnode();
if(head==0)
head=N2;
else
temp1=head;
while(temp1->next!=0)
temp1=temp1->next;
temp1->next=N2;
}
void dE()
struct node*temp2;
struct node*p1;
if(head==0)
printf("underflow");
temp2=head;
while(temp2->next->next!=0)
temp2=temp2->next;
p1=temp2->next;
temp2->next=0;
free(p1);
void iM()
struct node*N3,*J,*temp3;
N3=createnode();
if(head==0)
{
head=N3;
else
int d;
printf("Enter Position you want to enter ");
scanf("%d",&d);
temp3=head;
while(temp3->next->data!=d)
temp3=temp3->next;
J=temp3->next ;
temp3->next =N3;
N3->next=J;
void dM()
struct node*p;
struct node*temp4;
struct node*h;
if(head==0)
{
printf("underflow");
else
int v;
printf("Enter data you want to delete ");
scanf("%d",&v);
temp4=head;
while(temp4->next->data!=v)
temp4=temp4->next;
p=temp4->next->next;
temp4->next->next=0;
h=temp4->next;
temp4->next=p;
free(h);
void main()
int choice;
clrscr();
printf("1.Insert at beginning\n");
printf("2.Insert at end\n" );
printf("3.Insert at middle\n");
printf("4.Delete from beginning\n");
printf("5.Delete from end\n");
printf("6.Delete from middle\n");
printf("7.Display\n");
printf("8.Exit\n");
while (1)
printf(" Enter your choice");
scanf("%d",&choice);
switch(choice)
case 1: iB();
break;
case 2: iE();
break;
case 3: iM() ;
break;
case 4: dB();
break;
case 5: dE();
break;
case 6: dM();
break;
case 7: display();
break;
case 8: printf("exit");
return;
default: printf("invalid choice");
Conclusion: A singly linked list is a data structure that stores data in
nodes that are connected to each other in a chain. Each node contains
data and a reference to the next node in the chain. In C, a singly linked
list can be implemented using pointers and structures.
OUTPUT:
Conclusion: A singly linked list is a data structure that stores data in
nodes that are connected to each other in a chain. Each node contains
data and a reference to the next node in the chain. In C, a singly linked
list can be implemented using pointers and structures.
