20.7 (Adding set-like operations in LinkedList) Add and implement the following functions in LinkedList: // Add the elements in otherList to this list. void addAll(LinkedList& otherList) // Remove all the elements in otherList from this list void removeAll(LinkedList& otherList) // Retain the elements in this list if they are also in otherList void retainAll(LinkedList& otherList) #include using namespace std;

template class Node { public: T element; // Element contained in the node Node* next; // Pointer to the next node

Node() // No-arg constructor { next = NULL; }

Node(T element) // Constructor { this->element = element; next = NULL; } };

template class Iterator: public std::iterator { public: Iterator(Node* p) { current = p; };

Iterator operator++() // Prefix ++ { current = current->next; return *this; }

Iterator operator++(int dummy) // Postfix ++ { Iterator temp(current); current = current->next; return temp; }

T& operator*() { return current->element; }

bool operator==(const Iterator& iterator) { return current == iterator.current; }

bool operator!=(const Iterator& iterator) { return current != iterator.current; }

private: Node* current; };

template class LinkedList { public: LinkedList(); LinkedList(LinkedList& list); virtual ~LinkedList(); void addFirst(T element); void addLast(T element); T getFirst() const; T getLast() const; T removeFirst() throw (runtime_error); T removeLast(); void add(T element); void add(int index, T element); void clear(); bool contains(T element) const; T get(int index) const; int indexOf(T element) const; bool isEmpty() const; int lastIndexOf(T element) const; void remove(T element); int getSize() const; T removeAt(int index); T set(int index, T element);

Iterator begin() const { return Iterator(head); };

Iterator end() const { return Iterator(tail->next); };

private: Node* head; Node* tail; int size; };

template LinkedList::LinkedList() { head = tail = NULL; size = 0; }

template LinkedList::LinkedList(LinkedList& list) { head = tail = NULL; size = 0;

Node* current = list.head; while (current != NULL) { this->add(current->element); current = current->next; } }

template LinkedList::~LinkedList() { clear(); }

template void LinkedList::addFirst(T element) { Node* newNode = new Node(element); newNode->next = head; head = newNode; size++;

if (tail == NULL) tail = head; }

template void LinkedList::addLast(T element) { if (tail == NULL) { head = tail = new Node(element); } else { tail->next = new Node(element); tail = tail->next; }

size++; }

template T LinkedList::getFirst() const { if (size == 0) throw runtime_error("Index out of range"); else return head->element; }

template T LinkedList::getLast() const { if (size == 0) throw runtime_error("Index out of range"); else return tail->element; }

template T LinkedList::removeFirst() throw (runtime_error) { if (size == 0) throw runtime_error("No elements in the list"); else { Node* temp = head; head = head->next; if (head == NULL) tail = NULL; size--; T element = temp->element; delete temp; return element; } }

template T LinkedList::removeLast() { if (size == 0) throw runtime_error("No elements in the list"); else if (size == 1) { Node* temp = head; head = tail = NULL; size = 0; T element = temp->element; delete temp; return element; } else { Node* current = head;

for (int i = 0; i < size - 2; i++) current = current->next;

Node* temp = tail; tail = current; tail->next = NULL; size--; T element = temp->element; delete temp; return element; } }

template void LinkedList::add(T element) { addLast(element); }

template void LinkedList::add(int index, T element) { if (index == 0) addFirst(element); else if (index >= size) addLast(element); else { Node* current = head; for (int i = 1; i < index; i++) current = current->next; Node* temp = current->next; current->next = new Node(element); (current->next)->next = temp; size++; } }

template void LinkedList::clear() { while (head != NULL) { Node* temp = head; head = head->next; delete temp; }

tail = NULL; size = 0; }

template T LinkedList::get(int index) const { if (index < 0 || index > size - 1) throw runtime_error("Index out of range");

Node* current = head; for (int i = 0; i < index; i++) current = current->next;

return current->element; }

template int LinkedList::indexOf(T element) const { // Implement it in this exercise Node* current = head; for (int i = 0; i < size; i++) { if (current->element == element) return i; current = current->next; }

return -1; }

template bool LinkedList::isEmpty() const { return head == NULL; }

template int LinkedList::getSize() const { return size; }

template T LinkedList::removeAt(int index) { if (index < 0 || index >= size) throw runtime_error("Index out of range"); else if (index == 0) return removeFirst(); else if (index == size - 1) return removeLast(); else { Node* previous = head;

for (int i = 1; i < index; i++) { previous = previous->next; }

Node* current = previous->next; previous->next = current->next; size--; T element = current->element; delete current; return element; } }

// The functions remove(T element), lastIndexOf(T element), // contains(T element), and set(int index, T element) are // left as an exercise

(Adding set-like operations in LinkedList) Add and implement the following functions in LinkedList: // Add the elements in otherList to this list. void addAll(LinkedList& otherList) // Remove all the elements in otherList from this list void removeAll(LinkedList& otherList) // Retain the elements in this list if they are also in otherList void retainAll(LinkedList& otherList)

Add three function operators: +, -, and ^ for set union, difference, and intersection. Overload the = operator to perform a deep copy of a list. Add the [] operator for accessing/modifying an element. Use the following code to test your program: #include #include #include "LinkedList.h" using namespace std; template void printList(const LinkedList& list) { Iterator current = list.begin(); while (current != list.end()) { cout << *current << " "; current++; } cout << endl; } int main() { // Create a list for strings LinkedList list; list.add("Beijing"); list.add("Tokyo"); list.add("New York"); list.add("London"); list.add("Paris"); // Create a list for strings LinkedList list2; list2.add("Beijing"); list2.add("Shanghai"); list2.add("Paris"); list2.add("Berlin"); list2.add("Rome"); LinkedList list1(list); cout << "list1: "; printList(list1); cout << "list2: "; printList(list2); list1.addAll(list2); cout << "list is : "; printList(list); cout << "After list1.addAll(list2), list1 is "; printList(list1);

list1 = list; cout << "list1: "; printList(list1); cout << "list2: "; printList(list2); list1.removeAll(list2); cout << "After list1.removeAll(list2), list1 is "; printList(list1); list1 = list; cout << "list1: "; printList(list1); cout << "list2: "; printList(list2); list1.retainAll(list2); cout << "After list1.retainAll(list2), list1 is "; printList(list1); list1 = list; cout << "list1: "; printList(list1); cout << "list2: "; printList(list2); list1 = list1 + list2; cout << "After list1 = list1 + list2, list1 is "; printList(list1); list1 = list; cout << "list1: "; printList(list1); cout << "list2: "; printList(list2); list1 = list1 - list2; cout << "After list1 = list1 - list2, list1 is "; printList(list1); list1 = list; cout << "list1: "; printList(list1); cout << "list2: "; list1 = list1 ^ list2; cout << "After list1 = list1 ^ list2, list1 is "; printList(list1); list1 = list; cout << list1[0] << endl; list1[0] = "Paris"; cout << list1[0] << endl; return 0; }

LinkedList.h: