SINGLE LINKED LIST PROGRAM ARCHITECTURE
/*
Single Linked List program with all the operations:
initialising Linked List, creating, appending a node at end, deleting at any position, deleting all the linked list,
reverse of linked list, copying the linked list, displaying the linked list
*/
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();
~sll();
int isempty();
void display();
int length();
T find(int i);
node<T>* search(T x);
void append(node<T> *k);
void create();
void reverse();
sll(sll<T> &a);
void erase();
void rev();
void insert(int i, T x);
T del(int i);
};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
template<class T>
void sll<T>::display()
{
node<T>* p;//p is pointer to a node
if(isempty())
cout<<"Linked List is empty\n";
else
{
cout<<"Linked list is as follows\n";
p=first;
while(p!=NULL)
{
cout<<p->data<<"\t"<<p->link<<"\n";
p=p->link;
}
}//end of else
}//end of display()
//finding lengh of nodes
template<class T>
int sll<T>::length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()
//searching
template<class T>
node<T>* sll<T>::search(T x)
{
node<T> * p;
p=first;
while(p!=NULL)
{
if(p->data==x)
return(p);
else
p=p->link;
}
return(NULL);
}
template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()
//c.c
template<class T>
sll<T>::sll(sll<T> &a)
{
node<T> *p,*k;
first=NULL;
p=a.first;
while(p!=NULL)
{
k=new node<T>;
k->data=p->data;
append(k);
p=p->link;
}
}
//function for reverse of a single linked list
template<class T>
void sll<T>::reverse()
{
node<T> *cur,*prev,*next;
next=first;
cur=NULL;
while(next!=NULL)
{
prev=cur;
cur=next;
next=next->link;
cur->link=prev;
}
first=cur;
}//end of reverse()
template<class T>
void sll<T>::erase()
{
node<T> *p;
while(!isempty())
{
p=first;
first=first->link;
delete p;
}
}
template<class T>
sll<T>::~sll()
{
erase();
}
template<class T>
void sll<T>::insert(int i, T x)
{
node<T> *p,*temp;
//check the no of nodes should be 0 and total no of the nodes
if(i<0||i>length())
{
cout<<"Non-Existing Nodes\n";
}
else
{
p=new node<T>;
p->data=x;
//insert at the beginning or Linked List is empty
if(i==0)
{
p->link=NULL;
first=p;
}
//insert in the middle or at the end
else
{
temp=first;
//move temp ptr to ith node (desired node)
for(int j=1;j<=i-1;j++)
{
temp=temp->link;
}
//insert new node p after temp
p->link=temp->link;
temp->link=p;
}//inner else
}//outer else
}//end of insert()
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function
void menu()
{
cout<<"1. insertion a node after ith node \n";
cout<<"2. delete ith node\n";
cout<<"3. display SLL\n";
cout<<"4. length of the linked list\n";
cout<<"5. display data of the ith node (find())\n";
cout<<"6. search for a value in the ll\n";
cout<<"7. reverse of ll\n";
cout<<"8. copy linked list\n";
cout<<"9. erase linked list\n";
cout<<"10. exit \n";
}
int main()
{
sll<int> a;//creating object a, d.c is called
node<int> *p;
int ch,x,i;
clrscr();
menu();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<10)
{
switch(ch)
{
case 1: {
cout<<"enter value of i(0-10) insert at beginning\n";
cin>>i;
cout<<"enter value of new node\n";
cin>>x;
a.insert(i,x);//insert x after ith node
break;
}
case 2: {
cout<<"enter value of i\n";
cin>>i;
x=a.del(i);
if(x==-1)
cout<<"Non-existing node\n";
else
cout<<"Data of the deleted node is="<<x<<"\n";
break;
}
case 3: {
a.display();
break;
}
case 4: {
cout<<"No. of nodes="<<a.length()<<"\n";
break;
}
case 5: {
cout<<"enter value of i\n";
cin>>i;
if(x==-1)
cout<<"Non existing node\n";
else
cout<<"data of the desired node is="<<x<<"\n";
break;
}
case 6: {
cout<<"enter value to be searched\n";
cin>>x;
p=a.search(x);
if(p==NULL)
cout<<"value is not found\n";
else
cout<<"value is found at address="<<p<<"\n";
break;
}
case 7: {
a.reverse();
a.display();
break;
}
case 8: {
sll<int> b=a;
b.display();
break;
}
case 9: {
a.erase();
a.display();
break;
}
}//switch
menu();
cout<<"enter ur choice\n";
cin>>ch;
}//end of while
getch();
return(0);
}
No comments:
Post a Comment