New Page 0

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>

typedef struct node *ptrtype; // Pointer to a struct node
struct node {
int data;
ptrtype next;
};

class ptrList {
private:
ptrtype head;

public:
ptrList(){head=NULL;}
ptrList ( const ptrList &list ) // Copy constructor
{
head=NULL;
for( ptrtype ptr = list.head ;ptr!=NULL ; ptr= ptr->next)
if( !insertBack(ptr->data) )
{
cout<<"not enough memory";
break;
}
}
~ptrList(){};
ptrtype gethead() { return head;}
ptrtype getnode() { return ( new node ); }
ptrtype freenode(ptrtype p) {
//p->data=0;
//p->next=NULL;
delete p ;
return (NULL);
}

int insertFront( int newitem );
int insertBack ( int newitem);
int insertConditional ( int newitem );

int deleteFront();
int deleteBack();
int deleteSpecific ( int item );

// ptrList& operator=(const ptrList &OriginalList);

void traverse();
};
//===========================================================================
int ptrList :: insertFront ( int newitem)
{
ptrtype temp = getnode();
if(temp == NULL)
return (0);
else {
temp->data= newitem;
temp->next=head; // temp point to the address that is in head
head=temp; // let head point to temp
return (1);
}
}
//=============================================================================
// insert to the back with traversal
int ptrList ::insertBack ( int newitem)
{
ptrtype temp = getnode();

if (temp == NULL)
return 0;
else
{
temp->data = newitem;
temp->next =NULL;

if (head != NULL) // check empty list
{ // loop until last node point to NULL
for (ptrtype tail=head ; tail->next!=NULL ; tail=tail->next);

tail->next = temp; // let last node point to temp
}
else
head =temp; // if temp is the first node
return 1;
}//end outer else
}
//============================================================================
// insert to the back while maintaining a tail pointer
/*int ptrList ::insertBack ( int newitem )
{
ptrtemp temp = getnode();

if (temp == NULL)
return 0;
else
{
temp->data = newitem;
temp->next =NULL;

if (tail= NULL) // check empty list
head = temp;
else //non empty list
tail->next = temp

tail=temp; // tail is updated in both cases
return 1;
}//end outer else
}*/
//=============================================================================
int ptrList :: insertConditional ( int newitem )
{
// loop to get to the point of insertion
for ( ptrtype cur=head , prev=NULL ;
cur!=NULL && newitem > cur->data ;
prev=cur , cur= cur->next);

ptrtype temp = getnode();

if ( temp == NULL)
return 0;
else
{
temp->data = newitem;
temp->next = NULL;
if ( head == NULL ) //(1) empty list ,Beginning of list
head = temp;
else if ( prev == NULL) //one node in the list
{ // & newitem < cur->data
temp->next = head;
head = temp;
}
else
{ // (2)(3)Middle or end of list
temp->next = cur;
prev->next = temp;
}
}// end outer else
return 1;
}// end insertConditional
//===========================================================================
int ptrList :: deleteFront(){
if( head==NULL)
return 0;
else
{
ptrtype temp = head;
head = head->next;
temp = freenode(temp);
return(1);
}
}
//===========================================================================
int ptrList :: deleteBack(){
if( head==NULL)
return 0;
else
{
// Loop to reach to the node before the end
for ( ptrtype cur=head, prev=NULL;
cur->next !=NULL ;
prev=cur, cur=cur->next );

if( prev==NULL ) // Only one item in the list
head=NULL;
else
prev->next=NULL;

cur = freenode(cur);
return(1);
}
}
//=========================================================================
int ptrList :: deleteSpecific(int value)
{
//The list is traversed to reach the node to be deleted
for(ptrtype cur=head, prev=NULL;
cur->data!=value && cur!=NULL;
prev=cur, cur=cur->next);

if(cur==NULL) // empty list or not found
return 0;
else if(prev==NULL) // beginnning of the list
{
head=head->next;
cur=freenode(cur);
}
else // middle of the list
{
prev->next = cur->next;
cur = freenode(cur);
}
}
//===========================================================================
void ptrList :: traverse ()
{
if(head==NULL) //Empty List
cout << "\nEmpty List \n";

cout<<"\n\n The list is : ";
for ( ptrtype cur=head ; cur!=NULL ; cur=cur->next)
cout << cur->data<<" ";

cout<<"\n\n";
}
//=========================================================================
// Overload the = operator to make a deep copy
/*ptrList& ptrList :: operator=(const ptrList & OriginalList)
{
head=NULL;
for( ptrtype ptr = OriginalList.head ;ptr!=NULL ; ptr= ptr->next)
if( !insertBack(ptr->data) )
{
cout<<"not enough memory";
break;
}
return *this;
}*/
/* returns a reference to the object itself. this points to the object,
implicitely known in member functs.*/
// Read a number for the user
int getnum()
{
int num;
cout<<" Enter a number";
cin >>num;
return num;
}
//===========================================================================
int main(){
ptrList list;
int choise;

while (1)
{
clrscr();
cout<<" \n\n\t\t =====Linked list using pointers =====\n\n";
cout<<" Please select one of the following options\n"
<<" 1 insertFront\n"
<<" 2 insertBack\n"
<<" 3 insertConditional\n"
<<" 4 deleteFront\n"
<<" 5 deleteBack\n"
<<" 6 deleteSpecific\n"
<<" 7 traverse\n"
<<" 99 exit\n\n";
cin >>choise;

switch(choise)
{
case 1:{ list.insertFront(getnum()); break;}
case 2:{ list.insertBack(getnum()); break;}
case 3:{ list.insertConditional(getnum()); break; }
case 4:{ list.deleteFront(); break; }
case 5:{ list.deleteBack(); break;}
case 6:{ list.deleteSpecific(getnum()); break;}
case 7:{ list.traverse();getch(); break; }
case 99: exit(1);
default :cout<<" wrong selection!";
}//end switch
}//end while
return 0;
}