Code:#ifndef LIST_H #define LIST_H /* -- BEGIN CLASS LIST -- */ template <typename T> class List{ /* -- BEGIN PRIVATE DEFINITIONS -- */ private: /* -- BEGIN CLASS NODE -- */ struct Node{ T data; Node *next, *prev; Node(const T& d) : data(d), next(0), prev(0) {}; Node(const Node& src) : data(src.data), next(src.next), prev(src.prev) {}; Node& operator=(const Node& src){ if(this != &src){ Node *n, *p; try{ n = new Node(*src.next); // Test for self-assignment p = new Node(*src.prev); } catch(...){ delete n, p; // If self-assignment occurred, throw an exception throw; } delete next, prev; n = src.next; p = src.prev; } return *this; }; }; /* -- END CLASS NODE -- */ /* List Private Fields: */ Node *head, *tail; // Pointers to first and last Nodes in List unsigned int size; // Number of elements in List bool empty; // TRUE if NO elements in List, FALSE if ( >= 1 ) elements in List /* -- BEGIN PUBLIC DECLARATIONS -- */ public: /* -- BEGIN CLASS ITERATOR -- */ class Iterator{ private: Node *curr; public: /* Iterator Constructor: */ Iterator(Node* n = 0) : curr(n) {}; /* Overloaded Operators: NOTE: Postfix & Prefix operators preform the same function. */ Iterator& operator++() { curr = curr->next; return *this; }; Iterator& operator++(int) { curr = curr->next; return *this; }; Iterator& operator--() { curr = curr->prev; return *this; }; Iterator& operator--(int) { curr = curr->prev; return *this; }; bool operator!=(const Iterator& i) { return i.curr != curr; }; bool operator==(const Iterator& i) { return i.curr == curr; }; const T& operator*() const { return curr->data; }; Node* get_curr() const { return curr; } }; /* -- END CLASS ITERATOR -- */ /* -- PUBLIC INTERFACE -- */ /* List Constructors: */ List<T>(); // Creates an instance of List List<T>(const List& src); // Copies an existing List List<T>& operator=(const List& src); // Copies an existing List through assignment ~List<T>(); // Deletes all instances of Node & List /* List Functions: */ bool is_empty(){ return empty; } // Returns 1 if the List is Empty unsigned int size_of(){ return size; } // Returns an integer (size of List) void push_front(const T&); // Appends to beginning of List void pop_front(); // Deletes Node in head position void push_back(const T&); // Appends to end of List void pop_back(); // Deletes Node in tail position void insert(const T&); // Assumes List is sorted, inserts with < void remove(const T&); // Removes all elements w/matching value void sort(); // Sorts List with < void swap(Node*); // Swaps next and prev pointers for specified Node void reverse(); // Reverses order of List void unique(); // Removes duplicate values void clear(); // Deletes all elements in List void display(); // Displays values to std::cout /* Iteration-based Functions: */ Iterator begin() const { return Iterator(head); }; // Beginning of List (head) Iterator end() const { return Iterator(0); }; // End of List (tail->next = 0) Iterator rbegin() const { return Iterator(tail); }; // Beginning of List (tail) Iterator rend() const { return Iterator(0); }; // End of List (head->prev = 0) Iterator at(Node* x) const { return Iterator(x); }; // Returns an Iterator at specified Node Iterator at(Iterator i) const { return Iterator(i.get_curr()); }; Iterator at(int n) const { Iterator iter = begin(); for(int i = 0; i < n; i++){ iter++; } return iter; } Iterator insert(Iterator, const T&); // Insert at specified position, return position Iterator remove(Iterator); // Removes element at specified position, return position }; /* -- END CLASS LIST -- */ /* LIST CONSTRUCTOR: */ template <typename T> List<T>::List() : head(0), tail(0), size(0), empty(1) {} /* LIST COPY-CONSTRUCTOR: */ template <typename T> List<T>::List(const List& src) : head(0), tail(0), size(0), empty(1){ clear(); for(Iterator i = at(src.head); i != end(); i++){ push_back(*i); } /* Implementation w/out Iterators clear(); for(Node* curr = src.head; curr != (src.tail)->next; curr = curr->next){ push_back(curr->data); } */ } /* LIST ASSIGNMENT OPERATOR: */ template <typename T> List<T>& List<T>::operator=(const List& src){ if(this != &src){ Node *h, *t; try{ h = new Node(*src.head); // Test for self-assignment t = new Node(*src.tail); } catch(...){ delete h, t; // If self-assignment occurred, throw an exception throw; } delete head, tail; h = src.head; t = src.tail; } return *this; } /* LIST DESTRUCTOR: */ template <typename T> List<T>::~List(){ clear(); delete head; delete tail; } /* FUNCTION: push_front(const T&) PURPOSE: Creates an instance of Node in the head position. */ template <typename T> void List<T>::push_front(const T& x){ if(!empty){ head->prev = new Node(x); (head->prev)->next = head; head = head->prev; head->prev = 0; } else{ head = tail = new Node(x); empty = !empty; } size++; } /* FUNCTION: pop_front() PURPOSE: deletes the Node in the head position */ template <typename T> void List<T>::pop_front(){ if(!empty){ if(head != tail){ Node *curr(head); (head->next)->prev = 0; head = head->next; delete curr; } else{ Node* curr = head; head = tail = 0; delete curr; empty = !empty; } size--; } } /* FUNCTION: push_back(const T&) PURPOSE: Creates an instance of Node in the tail position */ template <typename T> void List<T>::push_back(const T& x){ if(!empty){ tail->next = new Node(x); (tail->next)->prev = tail; tail = tail->next; tail->next = 0; } else{ head = tail = new Node(x); empty = !empty; } size++; } /* FUNCTION: pop_back() PURPOSE: deletes the Node in the tail position */ template <typename T> void List<T>::pop_back(){ if(!empty){ if(head != tail){ Node* curr(tail); (tail->prev)->next = 0; tail = tail->prev; delete curr; } else{ Node* curr = head; head = tail = 0; delete curr; empty = !empty; } size--; } } /* FUNCTION: insert(const T&) PURPOSE: Assumes List is sorted, Inserts with < */ template <typename T> void List<T>::insert(const T& x){ if(!empty){ Iterator i = begin(); while(i != end() && *i <= x){ i++; } if(i == begin()){ push_front(x); } else if(i == end()){ push_back(x); } else{ Node* curr = i.get_curr(); Node* temp = new Node(x); (curr->prev)->next = temp; temp->prev = curr->prev; temp->next = curr; curr->prev = temp; size++; } } else{ head = tail = new Node(x); empty = !empty; size++; } } /* FUNCTION: remove(const T&) PURPOSE: Removes all elements w/matching value (x) */ template <typename T> void List<T>::remove(const T& x){ if(!empty){ Iterator i = begin(); while(i != end()){ if(*i == x){ if(i == begin()){ pop_front(); i = begin(); } else if(i == rbegin()){ pop_back(); i = begin(); } else{ Node* curr = i.get_curr(); (curr->prev)->next = curr->next; (curr->next)->prev = curr->prev; delete curr; curr = head; size--; } }/* -- END IF(*i == x) -- */ else{ i++; } }/* -- END WHILE -- */ } } /* FUNCTION: sort() PURPOSE: Sorts List with < */ template <typename T> void List<T>::sort(){ } /* FUCNTION: swap(Node*) PURPOSE: Swaps next and prev pointers for specified Node */ template <typename T> void List<T>::swap(Node* x){ Node* temp = x->next; x->next = x->prev; x->prev = temp; } /* FUNCTION: reverse() PURPOSE: Reverses the order of the List */ template <typename T> void List<T>::reverse(){ if(!empty){ for(Iterator i = begin(); i != end(); i--){ swap(i.get_curr()); } Node* temp = head; head = tail; tail = temp; } } /* FUNCTION: unique() PURPOSE: Removes duplicate values */ template <typename T> void List<T>::unique(){ } /* FUNCTION: clear() PURPOSE: deletes all elements in List */ template <typename T> void List<T>::clear(){ if(!empty){ while(!empty){ if(!empty){ pop_front(); } if(!empty){ pop_back(); } } } } /* FUNCTION: display() PURPOSE: displays values to std::cout */ template <typename T> inline void List<T>::display(){ if(!empty){ for(Iterator i = begin(); i != end(); i++){ std::cout << *i << std::endl; } } } #endif