LINKED LIST IMPLEMENTATION OF LIST ADT


AIM:
To write a program to implement List ADT using linked list

ALGORITHM:
1.INSERTION
STEP 1: Get the new node and read the data to be inserted.
STEP 2: If the list is empty assign new node has head.Otherwise go to step 3.
STEP 3: Get the address of preceding node after which the new node is to be
inserted
STEP 4: Make the link field of the new node is to be pointed the next node.
STEP 5: Make the link field of the preceding node is to be pointed the new node.


2.DELETION
STEP 1: Create a pointer which is to be pointed the previous node of the deleted
node.
STEP 2: Make the link field of the previous node is to be pointed the data field 
of the next node
STEP 3: Release the memory for the deleted node.


3.SEARCH
STEP 1: Get the data to be search.
STEP 2:Traverse the list from one node to another by advancing the head pointer 
and compare the data field with search data till last node .


STEP 3:If the search data is found print the data.


4.DISPLAY
STEP 1: Display the information in data field of the head.
STEP 2:Traverse the list from one node to another by advancing the head pointer


PROGRAM:
#include<iostream.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
class sll
{
private:
struct node
{
int data;
struct node *next;
}*head;
public:
sll();
void create();
void display();
void search(int key);
void insert_head(); void insert_after();
void insert_last();
void dele();
~sll();
};
sll::sll()
{
head=NULL;
}
sll::~sll()
{
node *temp,*temp1; 
temp=head->next; 
delete head; 
while(temp!=NULL) 
{ 
temp1=temp->next; 
delete temp; 
temp=temp1; 
} 
} 
void sll::create() 
{ 
node *temp,*New; 
int val,flag; 
char ans='y'; flag=TRUE; 
do 
{ 
cout<<"\n Enter the data:"; 
cin>>val; 
New=new node; if(New==NULL) 
cout<<"Unable to allocate memory \n"; 
New->data=val; 
New->next=NULL; 
if(flag==TRUE) 
{ 
head=New; temp=head; 

 flag=FALSE; 
} 
else 
{ 
temp->next=New; 
temp=New; 
} 
cout<<"\n Do You want to enter more elements?(y/n)"; 
ans=getch(); 
} 
while(ans=='y'||ans=='Y'); 
cout<<"\n The Singly list is created \n"; 
getch(); 
clrscr(); 
} 
void sll::display() 
{ 
node *temp; temp=head; 
if(temp==NULL) 
{ 
cout<<"\n The list is empty \n"; 
getch(); 
clrscr(); 
return; 
} 
while(temp!=NULL) 
{ 
cout<<temp->data<<" "; 
temp=temp->next; 
} 
getch(); 
} 
void sll::search(int key) 
{ 
node *temp; 
int found; 
temp=head; 
if(temp==NULL) 
{ 
cout<<"The Linked list is empty \n"; 
getch(); 
clrscr(); 
} 
found=FALSE; 
while(temp!=NULL && found==FALSE) 
{ 
if(temp->data!=key) 
temp=temp->next; 
else 
found=TRUE; 
} 
if(found==TRUE) 
{ 
cout<<"\n the element is present in the list \n"; 
getch(); 
} 
else 
{ 
cout<<"The element is not present in the list \n"; 
getch(); 
} 
} 
void sll::dele() 
{ 
node *temp,*prev; 
int key; 
temp=head; 
clrscr(); 
cout<<"\n Enter the data of the node you want to delete:"; 
cin>>key; 
while(temp!=NULL) 
{ 
if(temp->data==key) 
break; 
prev=temp; 
temp=temp->next; 
} 
if(temp==NULL) 
cout<<"\n Node not found"; 
else 
{ 
if(temp==head) 
head=temp->next; 
else 
prev->next=temp->next; 
delete temp; 
cout<<"\n The Element is deleted \n"; 
} 
getch(); 
} 
void sll::insert_last() 
{ 
node *New,*temp; 
cout<<"\n Enter the element which you want to insert"; 
cin>>New->data; 
if(head==NULL) 
head=New; 
else 
{ 
temp=head; 
while(temp->next!=NULL) 
temp=temp->next; temp->next=New; 
New->next=NULL; 
} 
} 
void sll::insert_after() 
{ 
int key; 
node *temp,*New; 
New=new node; 
cout<<"\n Enter the element which you want to insert"; 
cin>>New->data; 
if(head==NULL) 
{ 
head=New;
}
else
{
cout<<"\n Enter the element after which you want to insert the node"; cin>>key;
temp=head;
do
{
if(temp->data==key)
{
New->next=temp->next;
temp->next=New;
break;
}
else
temp=temp->next;
}
while(temp!=NULL);
}
}
void sll::insert_head()
{
node *New,*temp;
New=new node;
cout<<"\n Enter the element which you want  to insert";
cin>>New ->data;
if(head==NULL)
head=New;
else 
{ 
temp=head; 
New->next=temp; 
head=New; 
} 
} 
void main() 
{ 
sll s; 
int choice,val,ch1; 
char ans='y'; 
do 
{ 
clrscr(); 
cout<<"\n program to perform various operation on linked list"; 
cout<<"\n 1.Create"; 
cout<<"\n 2.Display"; 
cout<<"\n 3.Search"; 
cout<<"\n 4.Insert an element in a list"; 
cout<<"\n 5.Delete an element from list"; 
cout<<"\n 6.Quit"; 
cout<<"\n Enter your choice(1-6)"; 
cin>>choice; 
switch(choice){ case 1:s.create(); 
break; 
case 2: 
s.display(); 
break; 
case 3: 
cout<<"enter the element you want to search"; 
cin>>val; 
s.search(val); 
break; 
case 4: 
clrscr(); 
cout<<"\n The list is:\n"; 
s.display(); 
cout<<"\n menu"; 
cout<<"\n 1.Insert at begining \n 2.Insert after"; 
cout<<"\n 3.Insert at end"; 
cout<<"\n Enter Your choice"; 
cin>>ch1; 
switch(ch1){ 
case 1: 
s.insert_head(); 
break; 
case 2: 
s.insert_after(); 
break; 
case 3: 
s.insert_last(); 
break; 
default: 
cout<<"\n Invalid choice"; 
} 
break; 
default: 
cout<<"\n Invalid choice"; 
} 
cout<<"\n Continue?"; 
cin>>ans; 
}while(ans=='y'||ans=='Y'); 
getch(); 
return; 
}
OUTPUT: 
program to perform various operation on linked list 
1.Create 
2.Display 
3.Search 
4.Insert an element in a list 
5.Delete an element from list 
6.Quit 
Enter your choice(1-6)1 
Enter the data:10 
Do You want to enter more elements?(y/n) Y 
Enter the data:20 
Do You want to enter more elements?(y/n) Y 
The Singly list is created 
Enter your choice(1-6)2 
10 20 
Continue? Y 
  
Enter your choice(1-6)3 
enter the element you want to search 20 
the element is present in the list 
Continue? Y 
  
Enter your choice(1-6)4 
The list is: 
10 20 menu 
1.Insert at beginning 
2.Insert after 
3.Insert at end 
Enter Your choice 2 
Enter the element which you want to insert 30 
Enter the element after which you want to insert the node 10 
Continue? Y 
  
Enter your choice(1-6)2 
10 30 20 
Enter your choice(1-6)5 
Enter the data of the node you want to delete:20 
The Element is deleted 
Continue?Y 

V. Enter your choice(1-6)2 
W. 10 30 
X. Continue? Y 
Y. Enter your choice(1-6)6