Linked List and Classes

LinkedList_with_class.hpp

// See Section "Linked List as an ADT" of Chapter 17 of DS Malik's book. #include <iostream> #include <assert.h> // assert function using namespace std; //**** A single node ********************************************************************** template <class Type> // so later we can declare Type as int or double or other data types struct nodeType // a single node { Type info; nodeType<Type> * link; }; //**** Iterator *************************************************************************** template <class Type> class linkedListIterator // an iterator is used to overload operators and process each node { public: // constructors: linkedListIterator(); linkedListIterator(nodeType<Type> * ptr); // operator overloading: Type operator * (); linkedListIterator<Type> operator ++ (); bool operator == (const linkedListIterator<Type> & right) const; bool operator != (const linkedListIterator<Type> & right) const; // a const function cannot modify the object on which it's called private: nodeType <Type> * current; // pointer to the current node in the linked list }; //**** member functions of the iterator: ************************************************** // copy constructor template <class Type> linkedListIterator<Type>::linkedListIterator(nodeType<Type> * ptr) { current = ptr; // This is a literal for the null pointer. } // default constructor template <class Type> linkedListIterator<Type>::linkedListIterator() { current = NULL; // This is the null pointer. } template <class Type> Type linkedListIterator<Type>::operator * () { // * is overloaded so it directly dereferences the pointer info return current->info; } template <class Type> linkedListIterator<Type> linkedListIterator<Type>::operator ++ () { // ++ is overloaded so that it makes the current pointer pointing to the next node current = current->link; return * this; } template <class Type> bool linkedListIterator<Type>::operator == (const linkedListIterator<Type> & right) const { // == is overloaded to check if the two operands point to the same node return (current == right.current); } template <class Type> bool linkedListIterator<Type>::operator != (const linkedListIterator<Type> & right) const { // != is overloaded to check if the two operands point to different nodes return (current != right.current); } //**** Abstract class ********************************************************************* template <class Type> class linkedListType { public: bool isEmpty() const; // Check if the list is empty void destroyList(); // reset the list to empty void intializeList(); // reset the list to empty const linkedListType<Type>& operator = (const linkedListType<Type> &); // overload assignment operator for deep copy void print() const; // print all nodes of the list int length() const; // return the length of the list Type front() const; // return the data of the first node Type back() const; // return the data of the last node // abstract class contains virtual function // virtual functions are to be realized in the derived classes // There are supposed to be 2 derived classes: ordered list and unordered list virtual bool search (const Type& searchItem) const = 0; virtual void insertFirst (const Type& newItem) = 0; virtual void insertLast (const Type& newItem) = 0; virtual void deleteNode (const Type& deleteItem) = 0; // Iterators: linkedListIterator<Type> begin(); linkedListIterator<Type> end(); // constructors: linkedListType(); // default linkedListType(const linkedListType<Type> & otherList); // copy constructor // destructor: ~linkedListType(); protected: // can only be used by this class and its children (derived classes) int count; // length of the list nodeType<Type> * first; nodeType<Type> * last; private: // not to be used outside this class void copyList(const linkedListType<Type> & otherList); // copy the list from source to the current (deep copy) }; //**** Member functuions of the abstract class ******************************************** template <class Type> bool linkedListType<Type>::isEmpty() const { return (first == NULL); // if first is null, list is empty, return true } template <class Type> void linkedListType<Type>::destroyList() { nodeType<Type> * temp; while (first != NULL) { temp = first; first = first->link; delete temp; } last = NULL; count = 0; } template <class Type> void linkedListType<Type>::intializeList() { destroyList(); // reset the list to empty } template <class Type> void linkedListType<Type>::copyList(const linkedListType<Type> & otherList) { // DEEP COPY the data from otherList to this list nodeType<Type> * newNode, * current; if (first != NULL) // if the list is not empty, make it empty, destroyList(); // so that the old list will be overwritten. if (otherList.first == NULL) { first = NULL; last = NULL; count = 0; } else { current = otherList.first; count = otherList.count; // copy the first node first = new nodeType<Type>; // deep copy first->info = current->info; first->link = NULL; last = first; // copy the remaining list // similar to the example "LinkedList.cpp" current = current->link; while (current != NULL) { // create and copy newNode = new nodeType<Type>; newNode->info = current->info; newNode->link = NULL; // attach the new node to the last of the list: last->link = newNode; last = newNode; // current pointer points to the next of the other list current = current->link; } // end while } // end else } // end function template <class Type> const linkedListType<Type>& linkedListType<Type>::operator = (const linkedListType<Type> & otherList) { if (this != &otherList) // avoid self copy { copyList(otherList); // assignment operator calls the copy function } return * this; } template <class Type> void linkedListType<Type>::print() const { nodeType<Type> * current; current = first; while (current != NULL) { cout << current->info << " "; current = current->link; } cout << endl; } template <class Type> int linkedListType<Type>::length() const { return count; } template <class Type> Type linkedListType<Type>::front() const { assert(first != NULL); // terminate the program if first is null return first->info; } template <class Type> Type linkedListType<Type>::back() const { assert(last != NULL); // terminate the program if first is null return last->info; } // constructors: template <class Type> linkedListType<Type>::linkedListType() // default { first = NULL; last = NULL; count = 0; } // copy constructor with parameter template <class Type> linkedListType<Type>::linkedListType(const linkedListType<Type> & otherList) { first = NULL; copyList(otherList); // call the copy function } // destructor: template <class Type> linkedListType<Type>::~linkedListType() { destroyList(); } //**** Iterator functions: **************************************************************** template <class Type> linkedListIterator<Type> linkedListType<Type>::begin() { // call the copy constructor of the iterator linkedListIterator<Type> temp(first); return temp; } template <class Type> linkedListIterator<Type> linkedListType<Type>::end() { // call the copy constructor of the iterator linkedListIterator<Type> temp(NULL); return temp; } //**** Derived class - unordered linked list: ********************************************* template <class Type> class unorderedLinkedList: public linkedListType<Type> { public: // realize the virtual functions: bool search (const Type& searchItem) const; void insertFirst (const Type& newItem); void insertLast (const Type& newItem); void deleteNode (const Type& deleteItem); // no need to declare other members, because they are inherited. }; //**** Member functuions of unordered linked list: **************************************** template <class Type> bool unorderedLinkedList<Type>::search (const Type& searchItem) const { // This function searches for a node that has the same data as searchItem // If it's found, return true. Otherwise, return false. nodeType<Type> * current; bool found = false; current = this->first; while (current != NULL && !found) { if (current->info == searchItem) found = true; else current = current->link; } return found; } template <class Type> void unorderedLinkedList<Type>::insertFirst (const Type& newItem) { // insert a node at the head of the list nodeType<Type> * newNode; newNode = new nodeType<Type>; newNode->info = newItem; newNode->link = this->first; this->first = newNode; this->count++; if (this->last == NULL) // if last node was null, the list was empty before the insertion this->last = newNode; // then the list has one node after the insertion } template <class Type> void unorderedLinkedList<Type>::insertLast (const Type& newItem) { // insert a node at the tail of the list nodeType<Type> * newNode; newNode = new nodeType<Type>; newNode->info = newItem; newNode->link = NULL; if (this->first == NULL) // insert to empty list { this->first = newNode; this->last = newNode; this->count++; } else { this->last->link = newNode; this->last = newNode; this->count++; } } template <class Type> void unorderedLinkedList<Type>::deleteNode (const Type& deleteItem) { // This function deletes the node that has the data deleteItem nodeType<Type> * current, * trailCurrent; // remember p and q in the previous example // "linkedList.cpp"? // We use tailCurrent for p, current for q // in this function. bool found; // deleteItem must exists in the list before we can delete it if (this->first == NULL) // Case 1: the list was empty { cout << "Cannot delete from an empty list." << endl; } else if (this->first->info == deleteItem) // Case 2: the first node { // is the one we want to delete. current = this->first; this->first = this->first->link; // make the second node the new first this->count--; if (this->first == NULL) // if the list had one node before deletion { this->last = NULL; // the list should become an empty list now } delete current; // free the memory space of the original first node } else // search for the value, if found (Case 3), delete it. { found = false; // We can assume the first node isn't the one we want to delete, trailCurrent = this->first; // so we start searching from the second node: current = this->first->link; // searching... while (current != NULL && !found) { if (current->info != deleteItem) { // not this node. go to the next one trailCurrent = current; current = current->link; } else { found = true; } } // at the end of the loop, if found is true, //current must point to the node that we want to delete. if (found) { // delete the node by connecting its previous node // to its next node: trailCurrent->link = current->link; this->count--; if (this->last == current) // if the node to be deleted was the last node this->last = trailCurrent; // we update the pointer of last delete current; // free the memory space } else { cout << "The item that you wanted to delete does not exist " << "in the list." << endl; } } }