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(void): next(NULL) {}
\r
31 // Node(const T d, Node * ptr = NULL) { data = d; next = ptr; }
\r
32 Node(const T d, Node * ptr = NULL): data(d), next(ptr) {}
\r
39 template <class T> class List
\r
41 // This class implements the following exceptions:
\r
42 // LIST_EMPTY is thrown if you attempt to remove an object from an empty list.
\r
43 // OUT_OF_RANGE is thrown if you attempt to Add or Get from a position that
\r
44 // does not exist for the list.
\r
53 bool operator==(List &l);
\r
54 void AddAtFront(T data);
\r
55 void AddAtRear(T data);
\r
56 void AddAtPosition(int pos, T data);
\r
59 T GetPosition(int pos);
\r
62 T PeekPosition(int pos);
\r
68 // List class implementation
\r
70 template <class T> List<T>::List(void)
\r
76 template <class T> List<T>::~List()
\r
78 while (length) // Destroy all nodes that were created...
\r
80 Node<T> * tmp = last;
\r
87 template <class T> bool List<T>::operator==(List &l)
\r
89 if (Length() != l.Length())
\r
92 Node<T> * ptr1 = last->next, * ptr2 = l.last->next;
\r
96 if (ptr1->data != ptr2->data)
\r
99 ptr1 = ptr1->next, ptr2 = ptr2->next;
\r
101 while (ptr1 != last);
\r
106 template <class T> void List<T>::AddAtFront(T data)
\r
108 Node<T> * newNode = new Node<T>(data);
\r
110 if (last == NULL) // i.e., the list is empty...
\r
111 last = newNode->next = newNode;
\r
114 newNode->next = last->next;
\r
115 last->next = newNode;
\r
121 template <class T> void List<T>::AddAtRear(T data)
\r
123 Node<T> * newNode = new Node<T>(data);
\r
125 if (last == NULL) // i.e., the list is empty...
\r
126 last = newNode->next = newNode;
\r
129 newNode->next = last->next;
\r
130 last->next = newNode;
\r
137 template <class T> void List<T>::AddAtPosition(int pos, T data)
\r
139 if ((pos < 1) || (pos > length))
\r
140 throw OUT_OF_RANGE;
\r
143 AddAtFront(data); // Why reinvent the wheel?
\r
148 Node<T> * newNode = new Node<T>(data), * tmp = last;
\r
150 for(int i=1; i!=pos; i++) // Make tmp point to node ahead of add position
\r
153 newNode->next = tmp->next;
\r
154 tmp->next = newNode;
\r
159 template <class T> T List<T>::GetFront(void)
\r
164 T retVal = last->next->data;
\r
165 Node<T> * ptr = last->next;
\r
170 last->next = last->next->next;
\r
178 template <class T> T List<T>::GetRear(void)
\r
183 T retVal = last->data;
\r
184 Node<T> * ptr = last;
\r
193 while (ptr->next != last)
\r
196 ptr->next = ptr->next->next;
\r
206 template <class T> T List<T>::GetPosition(int pos)
\r
211 if ((pos < 1) || (pos > length))
\r
212 throw OUT_OF_RANGE;
\r
215 return GetFront(); // Why reinvent the wheel?
\r
220 Node<T> * tmp = last;
\r
222 for(int i=1; i!=pos; i++) // Make tmp point to node ahead of del position
\r
225 Node<T> * nodeToDelete = tmp->next;
\r
226 T retVal = nodeToDelete->data;
\r
228 tmp->next = tmp->next->next;
\r
229 delete nodeToDelete;
\r
235 template <class T> T List<T>::PeekFront(void)
\r
240 return last->next->data;
\r
243 template <class T> T List<T>::PeekRear(void)
\r
251 template <class T> T List<T>::PeekPosition(int pos)
\r
256 if ((pos < 1) || (pos > length))
\r
257 throw OUT_OF_RANGE;
\r
260 return PeekFront(); // Why reinvent the wheel?
\r
265 Node<T> * tmp = last;
\r
267 for(int i=1; i!=pos; i++)
\r
270 return tmp->next->data;
\r
273 template <class T> inline bool List<T>::IsEmpty(void)
\r
275 return (bool)(length == 0);
\r
278 template <class T> inline int List<T>::Length(void)
\r