#include "stdstuff.h" #include "List.h" // private copy method used by copy constructor and operator= // creates a duplicate of the given linked list void List::copy (const List &otherList) { Node *c, *tail, *n; // so far the list we're creating does not have a last node tail = head = NULL; // for all nodes in the other stack's list for (c = otherList.head; c != NULL; c = c -> next) { // create a copy of the node n = new Node(c -> data, NULL); // make the last node in the list being created point to it if (tail == NULL) { // no last node yet head = n; // new node goes at the start of the list } else { tail -> next = n; } // our new node is now the last node tail = n; } } // private deleteAll method used by destructor and operator= // deletes nodes, one at a time void List::deleteAll () { Node *t; while (head != NULL) { t = head; head = head -> next; delete t; } } // copy constructor just copies list List::List (const List &otherList) { copy(otherList); } // the destructor deletes all nodes List::~List () { deleteAll(); } // prints the list to cout one node at a time, starting with the head void List::outputList () const { Node *c = head; int i = 0; cout << "The list contains:" << endl; while (c != NULL) { cout << " " << c -> data; if (++i == 10) { cout << endl; i = 0; } c = c -> next; } if (i != 0) cout << endl; } // inserts a node into the list at the head of the list void List::insert (int data) { head = new Node (data, head); } // assigns one linked list to another List& List::operator= (const List &otherList) { deleteAll (); // nix the linked list for the object being assigned to copy (otherList); // copy the other list return *this; // as always for operator=, so a=b=c works } // Method sumGreaterThan(n) returns the sum of the values in the given list that are greater than n. // Note that "greater than" refers to the contents (value) of the node *not* its position in the list. // If there are no values greater than n, this method returns 0. // This method does *not* change the list. int List::sumGreaterThan(int n) const { return subSumGreaterThan(n,head); } // recursive sub-method to calculate the sum of values greater than n int List::subSumGreaterThan(int n, Node* subHead) const { if (subHead==NULL) return 0; // empty list has no values > n // if this value is greater than n, add it to the sum of the values greater than n in the rest of the list if (subHead->data > n) return subHead->data + subSumGreaterThan(n,subHead->next); // otherwise return the sum of the values greater than n in the rest of the list return subSumGreaterThan(n,subHead->next); } // Method hasValueLessThan(m) returns true if the list contains a value less than m, false otherwise. // Note that "less than" refers to the contents (value) of the node *not* its position in the list. // If there are no values in the list, this method returns false. // This method does *not* change the list. bool List::hasValueLessThan(int m) const { return subHasValueLessThan(m,head); } // recursive sub-method to see if the list contains a value less than m. bool List::subHasValueLessThan(int m, Node* subHead) const { if (subHead==NULL) return false; // empty list has no values less than m if (subHead->data < m) return true; // found a value < m // otherwise list has a value less than m if the rest of the list has a value less than m return subHasValueLessThan(m,subHead->next); } // Method hasDoubleValueAfter() returns true if the list contains a node directly followed by a node containing // double the value of the first node, and false otherwise. // If there are no values in the list, this method returns false. // This method does *not* change the list. bool List::hasDoubleValueAfter() const { return subHasDoubleValueAfter(head); } // recursive sub-method to see if the list contains a node directly followed by a node containing // double the value of the first node. bool List::subHasDoubleValueAfter(Node* subHead) const { // empty list or list with one value has no nodes followed by double their value if (subHead==NULL || subHead->next==NULL) return false; // if second value is twice the first one, return true if (subHead->data*2 == subHead->next->data) return true; // otherwise list has a node followed by double its value only if that occurs in the rest of the list return subHasDoubleValueAfter(subHead->next); }