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