1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
|
#include<iostream>
#include<cassert>
using namespace std;
//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement an iterator
// to a linked list.
//***********************************************************
template <class Type>
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType<Type> *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator<Type> operator++();
//Overload the preincrement operator.
//Postcondition: The iterator is advanced to the next node.
bool operator==(const linkedListIterator<Type>& right) const;
//Overload the equality operator.
//Postcondition: Returns true if this iterator is equal to
// the iterator specified by right, otherwise it returns
// false.
bool operator!=(const linkedListIterator<Type>& right) const;
//Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not equal to
// the iterator specified by right, otherwise it returns
// false.
private:
nodeType<Type> *current; //pointer to point to the current
//node in the linked list
};
template <class Type>
linkedListIterator<Type>::linkedListIterator()
{
current = NULL;
}
template <class Type>
linkedListIterator<Type>::
linkedListIterator(nodeType<Type> *ptr)
{
current = ptr;
}
template <class Type>
Type linkedListIterator<Type>::operator*()
{
return current->info;
}
template <class Type>
linkedListIterator<Type> linkedListIterator<Type>::operator++()
{
current = current->link;
return *this;
}
template <class Type>
bool linkedListIterator<Type>::operator==
(const linkedListIterator<Type>& right) const
{
return (current == right.current);
}
template <class Type>
bool linkedListIterator<Type>::operator!=
(const linkedListIterator<Type>& right) const
{
return (current != right.current);
}
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of a linked list. This is an abstract class.
// We cannot instantiate an object of this class.
//***********************************************************
template <class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=
(const linkedListType<Type>&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty, otherwise
// it returns false.
void print() const;
//Function to output the data contained in each node.
//Postcondition: none
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL, count = 0;
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program terminates;
// otherwise, the first element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the last
// element of the list is returned.
virtual bool search(const Type& searchItem) const = 0;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the list,
// otherwise the value false is returned.
virtual void insertFirst(const Type& newItem) = 0;
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list, last points to
// the last node in the list, and count is incremented by
// 1.
virtual void insertLast(const Type& newItem) = 0;
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the end of the list, last points to the
// last node in the list, and count is incremented by 1.
virtual void deleteNode(const Type& deleteItem) = 0;
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem is
// deleted from the list. first points to the first node,
// last points to the last node of the updated list, and
// count is decremented by 1.
linkedListIterator<Type> begin();
//Function to return an iterator at the beginning of the
//linked list.
//Postcondition: Returns an iterator such that current is set
// to first.
linkedListIterator<Type> end();
//Function to return an iterator one element past the
//last element of the linked list.
//Postcondition: Returns an iterator such that current is set
// to NULL.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType<Type>& otherList);
//copy constructor
~linkedListType();
//destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of list elements
//
nodeType<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
private:
void copyList(const linkedListType<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and assigned
// to this list.
};
|