C++ Program for Linked List Implementation of List ADT

Linked list implementation of List ADT

AIM:

• To Write a C++ Program for linked list implementation of list ADT.

Algorithm:
Step1: Create nodes first,last,next,prev and cur then set the value as NULL.
Step 2: Read the list operation type.
step 3: If operation type is create then process the following steps.
1. Allocate memory for node cur.
2. Read data in cur's data area.
3. Assign cur link as NULL.
4. Assign first=last=cur.
Step 4: If operation type is Insert then process the following steps.
1. Allocate memory for node cur.
2. Read data in cur's data area.
3. Read the position the Data to be inserting.
4. Availability of the position is true then assign cur's link as first and first=cur.
5. If availability of position is false then do following steps.
1. Assign next as cur and count as zero.
2. Repeat the following steps until count less than position.
1 .Assign prev as next
2. Next as prev of link.
3. Add count by one.
4. If prev as NULL then display the message INVALID POSITION.
5. If prev not qual to NULL then do the following steps.
1. Assign cur's link as prev's link.
2. Assign prev's link as cur.
Step5: If operation type is delete then do the following steps.
1. Read the position .
2. Check list is Empty .If it is true display the message List empty.
3. If position is first.
1. Assign cur as first.
2. Assign First as first of link.
3. Reallocate the cur from memory.
4. If position is last.
1. Move the current node to prev.
2. cur's link as Null.
3. Reallocate the Last from memory.
4. Assign last as cur.
5. If position is enter Mediate.
1. Move the cur to required position.
2. Move the Previous to cur's previous position
3. Move the Next to cur's Next position.
4. Now assign previous of link as next.
5. Reallocate the cur from memory.
step 6: If operation is traverse.
1. Assign current as first.
2. Repeat the following steps until cur becomes NULL.

Program:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class list
{
struct node
{
int data;
node *link;
}*p;
public:
void inslast(int);
void insbeg(int);
void insnext(int,int);
void delelement(int);
void delbeg();
void dellast();
void disp();
int seek(int);
list(){p=NULL;}
~list();
};
void list::inslast(int x)
{
node *q,*t;
if(p==NULL)
{
p=new node;
p->data=x;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=x;
t->link=NULL;
q->link=t;
}
cout<<"\n\nInserted successfully at the end..";
disp();
}
void list:: insbeg(int x)
{
node *q;
q=p;
p=new node;
p->data=x;
p->link=q;
cout<<"\n\nInserted successfully at the begining..";
disp();
}
void list::delelement(int x)
{
node *q,*r;
q=p;
if(q->data==x)
{
p=q->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==x)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
cout<<"\n\nElement you entered "<<x<<" is not found..";
}
void list:: delbeg()
{
cout<<"\n\nThe list before deletion:";
disp();
node *q;
q=p;
if(q==NULL)
{
cout<<"\n\nNo data is present..";
return;
}
p=q->link;
delete q;
return;
}
void list:: dellast()
{
cout<<"\n\nThe list before deletion:";
disp();
node *q,*t;
q=p;
if(q==NULL)
{
cout<<"\n\nThere is no data in the list..";
return;
}
if(q->link==NULL)
{
p=q->link;
delete q;
return;
}
while(q->link->link!=NULL)
q=q->link;
q->link=NULL;
return;
}
list::~list()
{
node *q;
if(p==NULL) return;
while(p!=NULL)
{
q=p->link;
delete p;
p=q;
}
}
void list::disp()
{
node *q;
q=p;
if(q==NULL)
{
cout<<"\n\nNo data is in the list..";
return;
}
cout<<"\n\nThe items present in the list are \n";
while(q!=NULL)
{
cout<<q->data<<"\n";
q=q->link;
}
}
void list :: insnext(int value,int position)
{
node *temp,*temp1;
temp=p;
if(temp1==NULL)
{
temp1= new node;
temp1->data=value;
temp1->link=NULL;
p=temp1;
return;
}
for(int i=0;((i<position)&&(temp->link!=NULL)) ;i++)
{
if(i==(position-1))
{
temp1= new node;
temp1->data= value;
temp1->link=temp->link;
temp->link=temp1;
}
temp=temp->link;
}
cout<<"\n\nInserted successfully at "<<position;
disp();
}
int list::seek(int value)
{
node *temp;
temp=p;
int position=0;
while(temp!=NULL)
{
if(temp->data==value)
return position+1;
else
{
temp=temp->link;
position=position+1;
}
}
cout<<"\n\nElement "<<value<<" not found";
return 0;
}
void main()
{
list l;
int ch,v,p,ps;
do
{
clrscr();
cout<<"\n\nOperations on List..";
cout<<"\n\n1.Insertion\n2.Deletion\n3.Display\n4.Seek\n5.Exit";
cout<<"\n\nEnter ur Option :";
cin>>ch;
switch(ch)
{
case 1:
clrscr();
cout<<"INSERTION";
cout<<"\n\n1.Insertion at begining\n2.Insertion at the end";
cout<<"\n3.Insertion between two Nodes";
cout<<"\n\nEnter ur choice:";
cin>>ps;
cout<<"Enter the value to insert:";
cin>>v;
switch(ps)
{
case 1:
l.insbeg(v);
break;
case 2:
l.inslast(v);
break;
case 3:
cout<<"\nEnter the position to insert the value:";
cin>>p;
l.insnext(v,p);
break;
default:
cout<<"\nThe choice is invalid";
return;
}
break;
case 2:
clrscr();
cout<<"\n1.Delete the first element\n2.Delete the last element";
cout<<"\n3.Enter the element to delete from the list";
cout<<"\n\nEnter ur choice:";
cin>>ps;
switch(ps)
{
case 1:
l.delbeg();
cout<<"\nThe list after deletion:";
l.disp();
break;
case 2:
l.dellast();
cout<<"\nThe list after deletion:";
l.disp();
break;
case 3:
l.disp();
cout<<"\nEnter the element to delete : ";
cin>>v;
l.delelement(v);
cout<<"\nThe list after deletion:";
l.disp();
break;
default:
cout<<"\nThe option is invalid...";
break;
}
break;
case 3:
clrscr();
l.disp();
break;
case 4:
clrscr();
l.disp();
cout<<"\nEnter the element to search:";
cin>>v;
cout<<"\nThe position of the element "<< v<<" is "<<l.seek(v);
getch();
break;
case 5:
exit(1);
default:
cout<<"\nThe option is invalid...";
return;
}
getch();
}while(ch!=5);
getch();
return;
}

Output:
Singly Linked List
1.Create
2.Insert
3.Delete
4.Exit
Enter Your Choice : 1
Enter The Data: 10
10
1.Create
2.Insert
3.Delete
4.Exit
Enter Your Choice : 2
Enter The Data: 30
Enter The Position: 1
30
10
1.Create
2.Insert
3.Delete
4.Exit
Enter Your Choice : 3
Enter The Position : 2
List Is Empty

Result:

• Thus, the linked list implementation of list ADT for singly linked list program has been written and executed successfully.