Header:

#ifndef LINKEDLIST_H #define LINKEDLIST_H

//********************************************* // The ListNode class creates a type used to * // store a node of the linked list. * //*********************************************

template class ListNode { public: T value; // Node value ListNode *next; // Pointer to the next node

// Constructor ListNode(T nodeValue) { value = nodeValue; next = NULL; } };

//********************************************* // LinkedList class * //*********************************************

template class LinkedList { private: ListNode *head; // List head pointer

public: // Constructor LinkedList() { head = NULL; }

//Copy constructor LinkedList(const LinkedList &obj);

// Destructor ~LinkedList();

// Linked list operations void appendNode(T); void insertNode(T); void deleteNode(T); void displayList() const;

int search(T) const;

//Operator overload void operator = (const LinkedList &); }; //************************************************** //Define copy constructor * //************************************************** template LinkedList::LinkedList(const LinkedList &obj) { ListNode *cursor;

//Traverse obj LinkedList cursor = obj.head; while (cursor != NULL) { this->appendNode(cursor->value); cursor = cursor->next; } } //************************************************** //Overload assignment operator //************************************************** template void LinkedList::operator=(const LinkedList &right) { ListNode *cursor; if (this->head != NULL) { cursor = head; while (cursor != NULL) { deleteNode(cursor->value); cursor = head; } }

cursor = right.head; while (cursor != NULL) { this->appendNode(cursor->value); cursor = cursor->next; }

}

// //Search() function // template int LinkedList::search(T target) const { ListNode *cursor; int location = -1; bool found = false;

cursor = head; while (cursor != NULL) { location++; if (cursor->value == target) { found = true; break; } cursor = cursor->next; } if (!found) location = -1;

return location; } //************************************************** // appendNode appends a node containing the value * // pased into newValue, to the end of the list. * //**************************************************

template void LinkedList::appendNode(T newValue) { ListNode *newNode; // To point to a new node ListNode *nodePtr; // To move through the list

// Allocate a new node and store newValue there. newNode = new ListNode(newValue);

// If there are no nodes in the list // make newNode the first node. if (!head) head = newNode; else // Otherwise, insert newNode at end. { // Initialize nodePtr to head of list. nodePtr = head;

// Find the last node in the list. while (nodePtr->next) nodePtr = nodePtr->next;

// Insert newNode as the last node. nodePtr->next = newNode; } }

//************************************************** // displayList shows the value stored in each node * // of the linked list pointed to by head. * //**************************************************

template void LinkedList::displayList() const { ListNode *nodePtr; // To move through the list

// Position nodePtr at the head of the list. nodePtr = head;

// While nodePtr points to a node, traverse // the list. while (nodePtr) { // Display the value in this node. cout << nodePtr->value << " ";

// Move to the next node. nodePtr = nodePtr->next; } }

//************************************************** // The insertNode function inserts a node with * // newValue copied to its value member. * //**************************************************

template void LinkedList::insertNode(T newValue) { ListNode *newNode; // A new node ListNode *nodePtr; // To traverse the list ListNode *previousNode = NULL; // The previous node

// Allocate a new node and store newValue there. newNode = new ListNode(newValue);

// If there are no nodes in the list // make newNode the first node if (!head) { head = newNode; newNode->next = NULL; } else // Otherwise, insert newNode { // Position nodePtr at the head of list. nodePtr = head;

// Initialize previousNode to NULL. previousNode = NULL;

// Skip all nodes whose value is less than newValue. while (nodePtr != NULL && nodePtr->value < newValue) { previousNode = nodePtr; nodePtr = nodePtr->next; }

// If the new node is to be the 1st in the list, // insert it before all other nodes. if (previousNode == NULL) { head = newNode; newNode->next = nodePtr; } else // Otherwise insert after the previous node. { previousNode->next = newNode; newNode->next = nodePtr; } } }

//***************************************************** // The deleteNode function searches for a node * // with searchValue as its value. The node, if found, * // is deleted from the list and from memory. * //*****************************************************

template void LinkedList::deleteNode(T searchValue) { ListNode *nodePtr; // To traverse the list ListNode *previousNode = NULL; // To point to the previous node

// If the list is empty, do nothing. if (!head) return;

// Determine if the first node is the one. if (head->value == searchValue) { nodePtr = head->next; delete head; head = nodePtr; } else { // Initialize nodePtr to head of list nodePtr = head;

// Skip all nodes whose value member is // not equal to num. while (nodePtr != NULL && nodePtr->value != searchValue) { previousNode = nodePtr; nodePtr = nodePtr->next; }

// If nodePtr is not at the end of the list, // link the previous node to the node after // nodePtr, then delete nodePtr. if (nodePtr) { previousNode->next = nodePtr->next; delete nodePtr; } } }

//************************************************** // Destructor * // This function deletes every node in the list. * //**************************************************

template LinkedList::~LinkedList() { ListNode *nodePtr; // To traverse the list ListNode *nextNode; // To point to the next node

// Position nodePtr at the head of the list. nodePtr = head;

// While nodePtr is not at the end of the list... while (nodePtr != NULL) { // Save a pointer to the next node. nextNode = nodePtr->next;

// Delete the current node. delete nodePtr;

// Position nodePtr at the next node. nodePtr = nextNode; } } #endif

-------------------------------------------------------------------------

cpp file

#include #include using namespace std;

#include "LinkedList.h"

int main() { LinkedListmyList;

for (int i = 1; i <= 10; i++) myList.appendNode(i); cout << "The list is: "; myList.displayList(); cout << endl; cout << endl;

cout << "List2 is "; LinkedList list2(myList); list2.deleteNode(5); list2.deleteNode(7); list2.deleteNode(2); list2.displayList(); cout << endl; cout << endl;

cout << "myList is "; myList.displayList(); cout << endl;

cout << endl; cout << "------ test '=' operator ------ ";

LinkedList list3; list3 = list2;

cout << "list3 is : "; list3.displayList(); cout << endl; cout << endl; //------test search()-------- cout << "----test search function----" << endl; int input; int location; do { cout << "Enter a number to search for: "; cin >> input; location = list3.search(input); if (location == -1) cout << input << " is not found "; else cout << input << " is at location " << location << endl; } while (input != -1);

list2->reversedLinkedList(); list2->displayList();

system("Pause"); return 0; }

-------------------------------------------------

Use the LinkedList template class (defined in LinkedList.h version 2), add following template member functions: 1. LinkedList reverse function The reverse function will put the linked list in reverse order. For example: if the list is

1 -> 2 -> 3 -> 4 after calling the reverse() function, the linked list should be: 4 -> 3 -> 2-> 1

Test these functions using an appropriate driver program.