// --------------------------------------------------------------------------- // SimpleLinkedList.h // // A generic linked list class. (There is already a list class in the // Standard C++ Library; this class is just an illustration of how such a // class is written from scratch!) // --------------------------------------------------------------------------- #ifndef _SIMPLE_LINKED_LIST_H #define _SIMPLE_LINKED_LIST_H #include <stdexcept> using namespace std; // A list object is represented as a doubly-linked ring of nodes. One // header (or "dummy") node always exists, so that insertion and removal // can be implemented consistently whether or not it is taking place // at the middle or the ends. template<class T> class List { // A private local class for the nodes that are linked together. private: class Node { public: Node* previous; T data; Node* next; Node(Node* previous, T data, Node* next): previous(previous), data(data), next(next) { } }; // The list itself is just a pointer to the dummy header node. private: Node* header; int size; // Constructors and Destructors public: // Constructs a new EMPTY list. The empty list is represented as one // containing only the header. List(): header(new Node(0, T(), 0)), size(0) { header->previous = header; header->next = header; } // The copy constructor! List(const List& other): header(new Node(0, T(), 0)), size(other.size) { header->previous = header; header->next = header; for (Node* n = other.header->next; n != other.header; n = n->next) { Node* newNode = new Node(header->previous, n->data, header); newNode->previous->next = newNode; newNode->next->previous = newNode; } } // Deletes all the nodes. TODO: THIS IS AN INEFFICIENT so it should be // rewritten. ~List() { destroy(); delete header; } // Behavior public: // Returns the number of items in the list. int getSize() { return size; } // Returns whether the list is empty. bool isEmpty() { return size == 0; } // Adds an item so that it has position index. The index positions start // at zero. If the index argument is not in the range 0..size then an // out_of_range is thrown. void add(int index, T item) { addBefore(item, (index == size ? header : nodeAt(index))); } // Removes the item at position index. Throws an out_of_range if the // index is not in the range 0..size-1. void remove(int index) { remove(nodeAt(index)); } // Returns the index of the first occurence of the given item, or -1 // if not found. int indexOf(T item) { int index = 0; for (Node* n = header->next; n != header; n = n->next) { if (n->data == item) { return index; } index++; } return -1; } // Retrieve the item at the given index. T get(int index) { return nodeAt(index)->data; } // Update the item at the given index. void set(int index, T item) { nodeAt(index)->data = item; } // Assignment Operator List& operator=(const List& other) { if (&other == this) { return *this; } destroy(); size = other.size; for (Node* n = other.header->next; n != other.header; n = n->next) { Node* newNode = new Node(header->previous, n->data, header); newNode->previous->next = newNode; newNode->next->previous = newNode; } return *this; } // Returns whether this list has the same size, and values in the // same positions, as another. bool operator==(const List& other) { if (size != other.size) { return false; } Node* n1 = header->next; Node* n2 = other.header->next; while (n1 != header && n2 != other.header) { if (n1->data != n2->data) { return false; } n1 = n1->next; n2 = n2->next; } return true; } // Helpers private: // Deletes all the nodes in this list except the header. void destroy() { while (!isEmpty()) { remove(0); } } // Return a pointer to the node at the given index position. Node* nodeAt(int index) { if (index < 0 || index > size) { throw out_of_range("Invalid list position"); } Node* n = header; for (int i = 0; i <= index; i++) { n = n->next; } return n; } // Add a new node containing the given value before the node // pointed to by n. void addBefore(T item, Node* n) { Node* newNode = new Node(n->previous, item, n); newNode->previous->next = newNode; newNode->next->previous = newNode; size++; } // Remove the node pointed to by n. void remove(Node* n) { if (n == 0 || n == header) { throw runtime_error("The list class is screwed up"); } n->previous->next = n->next; n->next->previous = n->previous; size--; } }; #endif
// --------------------------------------------------------------------------- // testlinkedlist.cpp // // A test script for the SimpleLinkedList class. // --------------------------------------------------------------------------- #include <iostream> #include <strstream> #include <cassert> #include <cmath> #include <stdexcept> using namespace std; #include "SimpleLinkedList.h" // This helper allows much more concise assertion expressions. // Check them out in the body of main() below. NOTE: I'm using // a strstream (which takes in a char*) rather than a sstream // (which takes in a string) because when I wrote this my C++ // compiler (gcc 2.95.2) didn't have an sstream class! List<int> stringToIntList(const char* s) { List<int> result; istrstream stream(s); while (true) { int i; stream >> i; if (!stream) break; result.add(result.getSize(), i); } return result; } // Well, this isn't too complete. Add more tests for extra credit. int main(int argc, char** argv) { List<int> list; // Some tests of add, indexOf, isEmpty, getSize and == assert(list.isEmpty() && list.getSize() == 0); list.add(0, 5); list.add(1, 6); list.add(2, 7); list.add(1, 4); assert(!list.isEmpty() && list.getSize() == 4); assert(list.indexOf(7) == 3); assert(list == stringToIntList("5 4 6 7 ")); // Test that copy constructor produces equal lists and // does not share values. List<int> otherList(list); assert(list == otherList); otherList.set(1, 10); assert(list == stringToIntList("5 4 6 7 ")); assert(otherList == stringToIntList("5 10 6 7 ")); assert(! (list == otherList)); // Test assignment. Make sure assignment to self doesn't // crash, and that after assignment the lists are ==. otherList = otherList; list = list; list = otherList; assert(list == otherList); assert(list.get(1) == 10); // Test out_of_range errors are properly thrown. bool errorHappened = false; try { list.add(-4, 3); } catch (out_of_range e) { errorHappened = true; } assert(errorHappened); // ------------------------------------------------------------------ // TODO More tests here. Extra credit for you if you do them for me. // You have to test EVERYTHING. // ------------------------------------------------------------------ cout << "All tests have passed\n"; return 0; }