Monday, November 2, 2009

List Class

/* List Class Template File
Title: CS 1410 Lab 13 - List Template
Author: Daniel J. Tanner
Date: April 10, 2006
*/
#ifndef TANNLIST_H
#define TANNLIST_H

#include
#include
#include
using namespace std;

namespace Metzengerstein
{
//class declaration
template
class List
{
public:
List(){head_ = NULL;}
List(const List & someList);
~List();
void append(const T & newData);
void insert(int index, const T & newData);
void erase(const T & oldData);
void clear();
void display();
List operator=(const List & someList);
private:
struct Node
{
friend List;
T data;
Node * next;
Node(const T & newData, Node * newNext = NULL){data = newData; next = newNext;}
};
Node * head_;
};

//function definitions
//copy constructor
template
List::List(const List & someList)
{
Node * curr = head_;
Node * temp = someList.head_;
while(temp != NULL)
{
curr = new Node(temp->data);
curr = curr->next;
temp = curr->next;
}
}

//Operator = overloader ~ makes = do something appropriate for dynamically
//allocated list
template
List List::operator=(const List & someList)
{
Node * curr = head_;
Node * temp = someList.head_;
while(temp != NULL)
{
curr = new Node(temp->data);
curr = curr->next;
temp = curr->next;
}
}
//Destuctor ~ properly destroys list after it is used
template
List::~List()
{
Node * temp;
while(head_ != NULL)
{
temp = head_;
head_ = head_->next;
delete temp;
}
}

//Display function ~ Traverses the list to display the contents
template
void List::display()
{
Node * curr = head_;
while(curr != NULL)
{
cout << curr->data << ' ';
curr = curr->next;
}
}

//append function ~ adds a new node at the end of the list
template
void List::append(const T & newData)
{
if(head_ == NULL)
head_ = new Node(newData);
else
{
Node * curr = head_;
while(curr->next != NULL)
curr = curr->next;
curr->next = new Node(newData);
}
}

//erase function ~ erases the first item in the list with data equivalent
//to the given data
template
void List::erase(const T & oldData)
{
if(head_ != NULL)
{
//special case ~ first item is the one that needs erasing
if(head_->data == oldData)
{
Node *curr = head_;
delete curr;
head_ = NULL;
return;
}

//regular cases
Node *prev = head_, *curr = head_;
while(curr->next != NULL && curr->data != oldData)
{
prev = curr;
curr = curr->next;
}
if(curr->data == oldData)
{
prev->next = curr->next;
delete curr;
}
else
return;
}
}

//insert function ~ inserts an item at the index given -- or at the beginning
//or end depending on the index given
template
void List::insert(int index, const T & newData)
{
Node *curr, *prev;
if(index <= 0 || head_ == NULL)
head_ = new Node(newData, head_);
else
{
curr = head_;
for(int count = 1; curr->next != NULL && count < index; count++)
{
prev = curr;
curr = curr->next;
}
if(curr->next == NULL && count < index)
append(newData);
else
prev->next = new Node(newData, curr);
}
}

//clear function ~ clears all the nodes from a list
template
void List::clear()
{
Node * temp;
while(head_ != NULL)
{
temp = head_;
head_ = head_->next;
delete temp;
}
}
}

#endif

No comments:

Post a Comment