// Lab Problem 6.2 (also Lab Exam 7A.2) // CS211 ADS2 // T Naughton, CS NUIM // Last updated 10 Apr 2000 #include /* This program illustrates a class to maintain an ordered linked list ** of integers. Integers are to be sorted in ascending order. ** The following methods are supported: ** -OrdIntList::Add // Add an int to the list at an appropriate pos ** -OrdIntList::PrintList // Print out the contents of the list ** -OrdIntList::Contains // Return true/false if an int is in the list ** -OrdIntList::DeleteList // Delete the entire list ** -OrdIntList::Remove // Remove a given integer from the list */ class ListElement { // A very simple class describing each node of the list public: int element; ListElement * next; }; class OrdIntList { public: OrdIntList(); // constructor ~OrdIntList(); // destructor // methods that act on IntList void Add(int newdata); void PrintList(); void DeleteList(); bool Contains(int element); void Remove(int element); private: ListElement * head; // a pointer to the head of the list }; OrdIntList::OrdIntList(){ head = NULL; // Initialise the list (mark the end of the list // with NULL). } OrdIntList::~OrdIntList(){ DeleteList(); // Clean up when finished with the variable } void OrdIntList::Add(int newdata){ // This method creates a new node with the data that is passed to // it, adding it in to the list in such a position as to maintain // an ascending order. ListElement * current; // pointer used to traverse list ListElement * temp; // pointer to the new node temp = new ListElement; temp->element = newdata; // There are three cases to take care of here. One, the list is // empty, two, the list is not empty, but new node must be // inserted at the beginning of the list, and three, the node // must be inserted somewhere else in the list. if (head == NULL) { temp->next = head; head = temp; } else if (newdata < head->element) { // Although these two lines of code are identical to those above, // using a separate condition is safer: evaluating head->element // when head==NULL will cause a runtime error. temp->next = head; head = temp; } else { current = head; while ((newdata > current->next->element) && (current->next != NULL)) { current = current->next; } // At this point, current is pointing at the last element with // a value less than newdata temp->next = current->next; current->next = temp; } } void OrdIntList::PrintList(){ // This method prints out the list. It does so by printing out the // contents of the head of the list and then each subsequent element // in turn. It repeats this until the end of the // list (a NULL) is found. The function returns a pointer to the // head of the list. Note: this function will work if an empty // list is passed to it. ListElement * current; cout << endl << "List: "; current = head; // set current to point to the head of the list while (current != NULL) { cout << current->element << ' '; current = current->next; } } void OrdIntList::DeleteList(){ // Delete the entire list ListElement * temp; // pointer to element to be deleted while (head != NULL) { temp = head; head = head->next; delete temp; } // head will have been set to NULL when loop terminates. } bool OrdIntList::Contains(int element){ // Return true if element is in the list, false if not. ListElement * current; bool found; current = head; found = false; while ((current != NULL) && !found) { if (current->element == element) { found = true; } current = current->next; } return found; } void OrdIntList::Remove(int element){ // Remove any elements in list that have the key 'element'. // This means that after deleting an element the program must // search the remainder of the list for more elements with the // same key. // There are four cases to take account of here: // i) The list is empty // ii) The element is at the head of the list // iii) The element is in the middle of the list // iv) The element is at the end of the list // In our method, we have three algorithms, one for the first // case, one for the second case, and one to take care of the // last two cases. ListElement * current; // used to traverse the list ListElement * temp; // used to mark a node for deletion bool keepgoing; current = head; if (current == NULL) { // do nothing } else { // delete all contiguous occurances of element at the // beginning of the list keepgoing = (current->element == element); while (keepgoing) { // delete head of the list head = current->next; delete current; current = head; // if not NULL compare current->element again if (current != NULL) { keepgoing = (current->element == element); } else { keepgoing = false; } } } if (current != NULL) { // make sure not at end of list // at this point we are guaranteed that current is not NULL // and does not point to an element we would want to delete while (current->next != NULL) { if (current->next->element == element) { // delete current->next node temp = current->next; current->next = current->next->next; delete temp; } else { // Because removing a node implicitly advances current->next // we will only advance if we do not remove a node current = current->next; // Putting this in an 'else' serves two purposes. Firstly, // if we advance after removing an element we will skip // our test of the next element, thereby failing to remove // multiples next to each other. Secondly, if we have just // deleted the last element of the list then advancing // current will cause a runtime error when we check the // condition of the while loop above. } } } } void main(void){ OrdIntList list; // the ordered list int tempint; // temporary storage list.Add(5); list.Add(2); list.Add(5); list.Add(9); list.Add(5); list.Add(15); list.PrintList(); tempint = 99; cout << endl << tempint << " is "; if (!list.Contains(tempint)) { cout << "not "; } cout << "in the list."; tempint = 9; cout << endl << tempint << " is "; if (!list.Contains(tempint)) { cout << "not "; } cout << "in the list."; list.Remove(5); list.PrintList(); }