2 // A generic list class using a circular singly linked list
\r
3 // by James L. Hammons
\r
4 // (C) 2004 Underground Software
\r
6 // Based upon work I did for CS240 Project 5 at Cal Poly Pomona for Dr. Bruce Hillam.
\r
7 // Hello Dr. Hillam! :-)
\r
9 // JLH = James L. Hammons <jlhamm@acm.org>
\r
12 // --- ---------- -------------------------------------------------------------
\r
13 // JLH 08/30/1999 Created this file
\r
14 // JLH 05/11/2004 Cleaned up a few things in the implementation
\r
18 // Some exception constants
\r
20 #define LIST_EMPTY 1
\r
21 #define OUT_OF_RANGE 2
\r
23 template <class T> class List; // Forward declaration...
\r
24 template <class T> class Node
\r
26 friend class List<T>;
\r
29 Node(void): next(NULL) {}
\r
30 Node(const T d, Node * ptr = NULL): data(d), next(ptr) {}
\r
37 template <class T> class List
\r
39 // This class implements the following exceptions:
\r
40 // LIST_EMPTY is thrown if you attempt to remove an object from an empty list.
\r
41 // OUT_OF_RANGE is thrown if you attempt to Add or Get from a position that
\r
42 // does not exist for the list.
\r
51 bool operator==(List &l);
\r
52 void AddAtFront(T data);
\r
53 void AddAtRear(T data);
\r
54 void AddAtPosition(int pos, T data);
\r
57 T GetPosition(int pos);
\r
60 T PeekPosition(int pos);
\r
66 // List class implementation
\r
68 template <class T> List<T>::List(void)
\r
74 template <class T> List<T>::~List()
\r
76 while (length) // Destroy all nodes that were created...
\r
78 Node<T> * tmp = last;
\r
85 template <class T> bool List<T>::operator==(List &l)
\r
87 if (Length() != l.Length())
\r
90 Node<T> * ptr1 = last->next, * ptr2 = l.last->next;
\r
94 if (ptr1->data != ptr2->data)
\r
97 ptr1 = ptr1->next, ptr2 = ptr2->next;
\r
99 while (ptr1 != last);
\r
104 template <class T> void List<T>::AddAtFront(T data)
\r
106 Node<T> * newNode = new Node<T>(data);
\r
108 if (last == NULL) // i.e., the list is empty...
\r
109 last = newNode->next = newNode;
\r
112 newNode->next = last->next;
\r
113 last->next = newNode;
\r
119 template <class T> void List<T>::AddAtRear(T data)
\r
121 Node<T> * newNode = new Node<T>(data);
\r
123 if (last == NULL) // i.e., the list is empty...
\r
124 last = newNode->next = newNode;
\r
127 newNode->next = last->next;
\r
128 last->next = newNode;
\r
135 template <class T> void List<T>::AddAtPosition(int pos, T data)
\r
137 if ((pos < 1) || (pos > length))
\r
138 throw OUT_OF_RANGE;
\r
141 AddAtFront(data); // Why reinvent the wheel?
\r
146 Node<T> * newNode = new Node<T>(data), * tmp = last;
\r
148 for(int i=1; i!=pos; i++) // Make tmp point to node ahead of add position
\r
151 newNode->next = tmp->next;
\r
152 tmp->next = newNode;
\r
157 template <class T> T List<T>::GetFront(void)
\r
162 T retVal = last->next->data;
\r
163 Node<T> * ptr = last->next;
\r
168 last->next = last->next->next;
\r
176 template <class T> T List<T>::GetRear(void)
\r
181 T retVal = last->data;
\r
182 Node<T> * ptr = last;
\r
191 while (ptr->next != last)
\r
194 ptr->next = ptr->next->next;
\r
204 template <class T> T List<T>::GetPosition(int pos)
\r
209 if ((pos < 1) || (pos > length))
\r
210 throw OUT_OF_RANGE;
\r
213 return GetFront(); // Why reinvent the wheel?
\r
218 Node<T> * tmp = last;
\r
220 for(int i=1; i!=pos; i++) // Make tmp point to node ahead of del position
\r
223 Node<T> * nodeToDelete = tmp->next;
\r
224 T retVal = nodeToDelete->data;
\r
226 tmp->next = tmp->next->next;
\r
227 delete nodeToDelete;
\r
233 template <class T> T List<T>::PeekFront(void)
\r
238 return last->next->data;
\r
241 template <class T> T List<T>::PeekRear(void)
\r
249 template <class T> T List<T>::PeekPosition(int pos)
\r
254 if ((pos < 1) || (pos > length))
\r
255 throw OUT_OF_RANGE;
\r
258 return PeekFront(); // Why reinvent the wheel?
\r
263 Node<T> * tmp = last;
\r
265 for(int i=1; i!=pos; i++)
\r
268 return tmp->next->data;
\r
271 template <class T> inline bool List<T>::IsEmpty(void)
\r
273 return (bool)(length == 0);
\r
276 template <class T> inline int List<T>::Length(void)
\r