| bl00dninja |
Sep 11th, 2006 1:05 AM |
singly-linked list templaste class in C++ w/ example driver
yeah, everyone's done it before, but what the hell.
comments and criticism are well received.
TemplateList.h
:
//benjamin hancock
//cs340
//mp03
//singly-linked list class in template form
/*
conventions:
current is always left pointing at a new element if one was added
whenever an element is deleted current moves back to the previous element
if an element is added, the size var is incremented
likewise, decremented if one is deleted
*/
// TemplateList.h
#include <iostream>
using namespace std;
#ifndef TEMPLATELIST_H
#define TEMPLATELIST_H
template <class elementDataType>
class TemplateList { // singly linked list class
public:
TemplateList(); // constructor
~TemplateList(); // destructor
TemplateList(const TemplateList<elementDataType> &); // copy constructor
void deleteElement(); // deletes the current element
void addElementAfterCurrent(elementDataType); // adds an element AFTER the current element
void addElementAsHead(elementDataType); // adds an element at the list head
void addElementAsTail(elementDataType); // adds an element at the list tail
elementDataType getCurrentElementValue(); // gets data value of current element
void moveForward(); // move forward one node in list
bool isFirstElement(); // returns true if current element is list head
bool isLastElement(); // returns true if current element is head tail
bool isEmpty(); // returns true if list is empty
int size(); // returns the size of the list
void moveToListHead(); // moves current node to the list head
void showList(); // shows list contents
protected:
struct node //holds a node's info
{
elementDataType nodeData;
node * next; // self referential
};
private:
node * head; // list head
node * current; // current node being processed
int currentSize; //current size of templateList object (# of nodes)
};
//constructor**********************************************************
//PRE: there is no list
//POST: there is an empty list
template <class elementDataType>
TemplateList<elementDataType>::TemplateList()
{
//set head to null
head = 0;
//set current to head
current = head;
//set size = 0
currentSize = 0;
}
//destructor*************************************************************
//PRE: there is a list
//POST: deallocate all dynamically allocated memory
template <class elementDataType>
TemplateList<elementDataType>::~TemplateList()
{
//shows destructor works (one message per object being murdered)
cout<<"\n***************************"<<endl;
cout<<"*-> destructor called <-*\t\t"<<endl;
cout<<"***************************\n"<<endl;
//works on empty lists also
//temp node to hold head's place
node * temp = head;
//as long as somethin's there, we destroy it
while(temp != 0)
{
//disconnect head link, attach to next
head = head->next;
//deallocate old head
delete temp;
//reset temp to new head
temp = head;
}
}
//copy constructor********************************************************
//PRE: there is a list object
//POST: there is another list object identical to the old one
template <class elementDataType>
TemplateList<elementDataType>::TemplateList(const TemplateList<elementDataType> & nextObject)
{
cout<<"\n***************************"<<endl;
cout<<"*-> copy ctor called <-*\t\t"<<endl;
cout<<"***************************\n"<<endl;
//set head and current in new list to null
head = current = 0;
//set current size variable
currentSize = nextObject.currentSize;
//if empty list, make a copy of what we've got and leave it alone
if (nextObject.head == 0) return;
//otherwise we've got some work ahead of us...
else
{
//pointer to old list's nodes
node * oldTemp = nextObject.head;
//create the first new node
node * firstNode = new node;
//set that node to the new head
head = firstNode;
//fill first node with data
firstNode->nodeData = oldTemp->nodeData;
//set a prev node to find prev element's data members
node * prevNode = firstNode;
//while there's still items in the old list
while(oldTemp->next != 0)
{
//advance oldTemp to next item in old list
oldTemp = oldTemp->next;
//create a new node
node * newNode = new node;
//fill new node with old TemplateList's corresponding data
newNode->nodeData = oldTemp->nodeData;
//connect last node in new TemplateList with new node in new TemplateList
prevNode->next = newNode;
//move previous node up so we can do it again
prevNode = newNode;
}
//point last element to null
prevNode->next = 0;
//now we find where to point current
int items = 1;
oldTemp = nextObject.head;
while(oldTemp != nextObject.current)
{
//advance oldTemp
oldTemp = oldTemp->next;
//items will end up being the index of current
items++;
}
//set new current to new head
current = head;
for(int i = 1; i < items; i++)
{
//move current until we need to stop
current = current->next;
}
}
}
//delete the current element*****************************************************
//PRE: there is a list
//POST: delete an element if current points to one
template <class elementDataType>
void TemplateList<elementDataType>::deleteElement()
{
//note arbitrary convention of moving current to element before
//deleted element (made sense with empty list)
//taken care of by deleteElement()
//do nothing if no elements
if(head == 0) cout<<"\nempty list.\n"<<endl;
//if 1 element
else if(head->next == 0)
{
//reset head to next
head = 0;
//deallocate current node
delete current;
//set current to head
current = 0;
//adjust size
currentSize--;
}
//if >1 element && current = head
else if(current == head && current->next != 0)
{
//drop first element
head = head->next;
//dump that node
delete current;
//set current to head
current = head;
//adjust list size
currentSize--;
}
//if in middle of list...
else if (current != head && current->next != 0)
{
//temp node*
node * temp = head;
//find the place right before current
while(temp->next != current)
{
temp = temp->next;
}
//connect THAT place with the next place
temp->next = current->next;
//get rid of current node
delete current;
//set current to old place
current = temp;
//adjust list size
currentSize--;
}
//we're pointing at tail...
else if(current != head && current->next == 0)
{
//set temp to head
node * temp = head;
//find node before current
while(temp->next != current)
{
temp = temp->next;
}
//set temp's next to null
temp->next = 0;
//dump this node
delete current;
//reset current
current = temp;
currentSize--;
}
}
//add after current*************************************************************
//PRE: there is a list
//POST: new element after where current was pointing
template <class elementDataType>
void TemplateList<elementDataType>::addElementAfterCurrent(elementDataType input)
{
//if nothing, add as head
if(head == 0) addElementAsHead(input);
//if at end, add as tail
else if (current ->next == 0) addElementAsTail(input);
//otherwise...
else
{
//temp node
node * temp = new node;
//hold current position
temp->next = current->next;
//back current up some
current->next = temp;
//insert data
temp->nodeData = input;
//set current to new item
current = current->next;
//adjust list size
currentSize++;
}
}
//add as head******************************************************************
//PRE: there is a list
//POST: there is a new element at the head
template <class elementDataType>
void TemplateList<elementDataType>::addElementAsHead(elementDataType input)
{
//if no elements, set head to new one
if (head == 0)
{
head = new node;
head->nodeData = input;
head->next = 0;
current = head;
}
//otherwise...
else if(head != 0)
{
//new node
node * temp = new node;
//new node's data = paramater
temp->nodeData = input;
//push the old head back a bit
temp->next = head;
//reset head to new stuff
head = temp;
//set current to new element
current = temp;
}
//adjust list size
currentSize++;
}
//add to tail****************************************************************
//PRE: there is a list
//POST: there is a new element at the tail
template <class elementDataType>
void TemplateList<elementDataType>::addElementAsTail(elementDataType input)
{
//if no elements, we just repeat the crap above...
if (head == 0)
{
head = new node;
current = head;
head->nodeData = input;
head->next = 0;
}
//otherwise...
else
{
//new node
node * temp = new node;
//set start
current = head;
//find end of list
while(current->next != 0)
{
current = current->next;
}
//set temp at end
current->next = temp;
//set tail pointer to null
temp->next = 0;
//insert data
temp->nodeData = input;
//set current to new crap
current = temp;
}
//adjust list size
currentSize++;
}
//return current's value*******************************************************
//PRE: current is pointing somewhere
//POST: return value of current's->data
template <class elementDataType>
elementDataType TemplateList<elementDataType>::getCurrentElementValue()
{
//duh...
return current->nodeData;
}
//move current to next element*************************************************
//PRE: current is pointing to an element
//POST: current is pointing to next element (prompt user whether or not to wrap)
template <class elementDataType>
void TemplateList<elementDataType>::moveForward()
{
//if empty TemplateList, chide user
if (head == 0) cout<<"empty list, try again buddy."<<endl;
//if we're at the end, make sure the user understands the implications
// of moving forward (we go back to the start)
else if (current->next == 0)
{
cout<<"\nwarning: end of list, want to wrap to head? (y or n)"<<endl;
char choice = 'n';
//get choice
cin>>choice;
//move current to start of list
if(choice == 'y') current = head;
//do nothing if they want to stay at the end
else if (choice == 'n') cout<<"ok, you're gonna stay at the end"<<endl;
//WTF!?!..the user is retarded, exit program and suggest
// they stay away from computers
else
{
cout<<"invalid parameter, bye."<<endl;
exit(1);
}
}
//or we can just move to the next element
else current = current->next;
}
//is current the head?**********************************************************
//PRE: current may be pointing to an element
//POST: returns if current = head
template <class elementDataType>
bool TemplateList<elementDataType>::isFirstElement()
{
//if no elements, remind user that they suck
if (head == 0)
{
cout<<"\nempty list\n"<<endl;
return 0;
}
//return if they are pointing to the start
else
{
return (current == head);
}
}
//is current the last element?***************************************************
//PRE: current points to an element
//POST: returns whether current = tail
template <class elementDataType>
bool TemplateList<elementDataType>::isLastElement()
{
//duh...there's nothing there
if (head == 0)
{
cout<<"\nempty list\n"<<endl;
return 0;
}
//return if the user is pointing to the tail node
else
{
return (current->next == 0);
}
}
//are there elements?**************************************************************
//PRE: there may or may not be elements
//POST: user is aware
template <class elementDataType>
bool TemplateList<elementDataType>::isEmpty()
{
//if head's not pointing to something real, there's nothing there
return (head == 0);
}
//return # of elements*************************************************************
//PRE: there may be a list
//POST: if so, # of elements is returned
template <class elementDataType>
int TemplateList<elementDataType>::size()
{
return currentSize;
}
//move current element to the start of the list************************************
//PRE: current is pointing to an element
//POST: element is removed and placed at the head
template <class elementDataType>
void TemplateList<elementDataType>::moveToListHead()
{
//do nothing if already at head
if(current == head) cout<<"\n\nalready at head\n\n"<<endl;
else
{
//temp node
node * temp = current;
//add that crap to the start (with correct paramater)
addElementAsHead(temp->nodeData);
//point current to old stuff (so we can trash it)
current = temp;
//get rid of the old crap
deleteElement();
//reset current to new stuff
current = head;
}
}
//print out TemplateList contents, and vars, etc.********************************************
//PRE: a list exists
//POST: list contents and data vals printed out
template <class elementDataType>
void TemplateList<elementDataType>::showList()
{
//nice DOS formatting ;-)
cout<<"\n\n********************************************************"<<endl;
//show size
cout<<"size:\t"<<size()<<"\n"<<endl;
//avoid dereferincing nodeData from non-existent element
if (current == 0) cout<<"***** empty list, no elements *****"<<endl;
//show current val
else cout<<"current val:\t"<<current->nodeData<<"\n"<<endl;
//loop through list and show elements in numbered order
int i = 1;
for(node * temp = head; temp != 0; temp = temp->next)
{
//display that info
cout<<"element "<<i<<"\t"<<temp->nodeData<<endl;
i++;
}
//more fancy c-prompt graphics
cout<<"\n\n*********************************************************"<<endl;
}
//*****************************************************************************************
#endif
mp03b.cpp //test driver for fun
:
#include <iostream>
#include "TemplateList.h"
using namespace std;
int main()
{//begin main
bool finalQuit = false;
do{
cout<<"\n\nPick a type of list:\n"<<endl;
cout<<"1:\tint\t2:\tlong"<<endl;
cout<<"3:\tfloat\t4:\tdouble"<<endl;
cout<<"5:\tbool\t6:\tchar"<<endl;
cout<<"7:\tquit program\n"<<endl;
int mainChoice;
cin>>mainChoice;
if (mainChoice == 1)
{//type if selection
bool quit = false;
TemplateList<int> * x = new TemplateList<int>;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the List empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tcopy test"<<endl;
cout<<"11:\tdestroy current list\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
int in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsHead(in);
x->showList();
break;
}
case 2:
{
int in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsTail(in);
x->showList();
break;
}
case 3:
{
int in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAfterCurrent(in);
x->showList();
break;
}
case 4:
{
x->moveForward();
x->showList();
break;
}
case 5:
{
if(x->isFirstElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 6:
{
if(x->isLastElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 7:
{
if(x->isEmpty() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 8:
{
x->moveToListHead();
x->showList();
break;
}
case 9:
{
x->deleteElement();
x->showList();
break;
}
case 10:
{
x->showList();
cout<<"\n*************FIRST OBJECT (ORIGINAL)***********"<<endl;
TemplateList<int> X(*x);
X.showList();
cout<<"\n*************SECOND OBJECT (COPY)***********"<<endl;
break;
}
case 11:
{
quit = true;
delete x;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
else if (mainChoice == 2)
{
bool quit = false;
TemplateList<long> * x = new TemplateList<long>;
//infinite menu loop
do //while quit == false
{
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the List empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tcopy test"<<endl;
cout<<"11:\tdestroy current list\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
long in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsHead(in);
x->showList();
break;
}
case 2:
{
long in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsTail(in);
x->showList();
break;
}
case 3:
{
long in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAfterCurrent(in);
x->showList();
break;
}
case 4:
{
x->moveForward();
x->showList();
break;
}
case 5:
{
if(x->isFirstElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 6:
{
if(x->isLastElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 7:
{
if(x->isEmpty() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 8:
{
x->moveToListHead();
x->showList();
break;
}
case 9:
{
x->deleteElement();
x->showList();
break;
}
case 10:
{
x->showList();
cout<<"\n*************FIRST OBJECT (ORIGINAL)***********"<<endl;
TemplateList<long> X(*x);
X.showList();
cout<<"\n*************SECOND OBJECT (COPY)***********"<<endl;
break;
}
case 11:
{
quit = true;
delete x;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
else if (mainChoice == 3)
{
bool quit = false;
TemplateList<float> * x = new TemplateList<float>;
//infinite menu loop
do //while quit == false
{
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the List empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tcopy test"<<endl;
cout<<"11:\tdestroy current list\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
float in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsHead(in);
x->showList();
break;
}
case 2:
{
float in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsTail(in);
x->showList();
break;
}
case 3:
{
float in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAfterCurrent(in);
x->showList();
break;
}
case 4:
{
x->moveForward();
x->showList();
break;
}
case 5:
{
if(x->isFirstElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 6:
{
if(x->isLastElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 7:
{
if(x->isEmpty() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 8:
{
x->moveToListHead();
x->showList();
break;
}
case 9:
{
x->deleteElement();
x->showList();
break;
}
case 10:
{
x->showList();
cout<<"\n*************FIRST OBJECT (ORIGINAL)***********"<<endl;
TemplateList<float> X(*x);
X.showList();
cout<<"\n*************SECOND OBJECT (COPY)***********"<<endl;
break;
}
case 11:
{
quit = true;
delete x;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
else if (mainChoice == 4)
{
bool quit = false;
TemplateList<double> * x = new TemplateList<double>;
//infinite menu loop
do //while quit == false
{
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the List empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tcopy test"<<endl;
cout<<"11:\tdestroy current list\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
double in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsHead(in);
x->showList();
break;
}
case 2:
{
double in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsTail(in);
x->showList();
break;
}
case 3:
{
double in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAfterCurrent(in);
x->showList();
break;
}
case 4:
{
x->moveForward();
x->showList();
break;
}
case 5:
{
if(x->isFirstElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 6:
{
if(x->isLastElement() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 7:
{
if(x->isEmpty() ) cout<<"\n\n***** yes *****\n\n"<<endl;
else cout<<"\n\n***** no *****\n\n"<<endl;
system("PAUSE");
x->showList();
break;
}
case 8:
{
x->moveToListHead();
x->showList();
break;
}
case 9:
{
x->deleteElement();
x->showList();
break;
}
case 10:
{
x->showList();
cout<<"\n*************FIRST OBJECT (ORIGINAL)***********"<<endl;
TemplateList<double> X(*x);
X.showList();
cout<<"\n*************SECOND OBJECT (COPY)***********"<<endl;
break;
}
case 11:
{
quit = true;
delete x;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
else if (mainChoice == 5)
{
bool quit = false;
TemplateList<bool> * x = new TemplateList<bool>;
//infinite menu loop
do //while quit == false
{
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the List empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tcopy test"<<endl;
cout<<"11:\tdestroy current list\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
bool in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsHead(in);
x->showList();
break;
}
case 2:
{
bool in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x->addElementAsTail(in);
x->showList();
break;
}
case 3:
{
bool in;
| 