This is in C++

NOTE:: PLEASE, MAKE SURE TO INCLUDE --->>>> COMMENTS, HEADING FILES (To identify each content belongs to), AND OUTPUT (Including the menu and selection) Thanks

==================================== List.h =======================

#ifndef LINKEDLIST_LIST_H #define LINKEDLIST_LIST_H // constants // -------------------------------------------------------- const int LIST_HEAD = 0; // list position of head node const int LIST_TAIL = -1; // specify current tail position

class List { private: // internal storage structure for a Node struct Node { int value; Node* next; };

Node* head; // hold reference to head of the list (Node[0]) int size; // current size of the list (empty==0)

public: List(); ~List(); int getSize(); bool isEmpty(); void insert(int value, int position=LIST_TAIL); int remove(int position=LIST_TAIL); int read(int position); void modify(int value, int position); int findIndex(int);

private: Node* traverse(int position); };

#endif //LINKEDLIST_LIST_H

========================= List.cpp ===============================

#include #include #include

#include "List.h"

// -------------------------------------------------------- // Types // --------------------------------------------------------

// simulated menu choice operations on the list enum ListOp { LIST_APPEND = 'A', LIST_INSERT = 'I', LIST_UPDATE = 'U', LIST_DELETE = 'D', LIST_EXIT = 'E' };

// -------------------------------------------------------- // Function Declarations (proto-types) // -------------------------------------------------------- char getMenuOption(); void appendList(List* list); void insertList(List* list); void updateList(List* list); void deleteList(List* list); void printList(List* list);

// -------------------------------------------------------- // Function Definitions // -------------------------------------------------------- int main() { srand(time(NULL)); // refresh random numbers

List list; // the one and only List

ListOp operation; // user choice to continue do {

// menu operations operation = static_cast(getMenuOption()); switch(operation) { case LIST_APPEND: appendList(&list); break; case LIST_INSERT: insertList(&list); break; case LIST_UPDATE: updateList(&list); break; case LIST_DELETE: deleteList(&list);

}

// print the current list printList(&list);

} while(operation != LIST_EXIT);

return 0; // return success to OS } // main

/** * Prompt user for operation to perform next * @return 1st letter of menu option (E to exit) */ char getMenuOption() { char menuChoice;

std::cout "; std::cin >> menuChoice;

// force menu choice to uppercase menuChoice &= ~32; // turn off bit 5

return menuChoice; } // getMenuChoice

/** * Append a random number to the end of the list * @param list -- pointer to a list ADT */ void appendList(List* list) {

srand(time(NULL)); // refresh random numbers

int value = rand() % 100; // calc random number value list->insert(value); // test 1-parameter insert w/ default position

std::cout getSize() - 1

/** * Insert a random number at a random position * @param list -- pointer to a list ADT */ void insertList(List* list) { int value = rand() % 100; // calc random number value int position = list->getSize(); // init to size in case list is empty

if(list->isEmpty()) { list->insert(value); // test 1-parameter insert w/ default position } else { position = rand() % list->getSize(); // calc random position (0 (size - 1)) list->insert(value, position); // test 2-parameter insert }

std::cout

/** * Update a random list position with a new random number * @param list -- pointer to a list ADT */ void updateList(List* list) { if (list->isEmpty()) { std::cout getSize();

list->modify(value, position); // test modify method

std::cout

/** * Delete 1 value at a random position in the list * @param list -- pointer to a list ADT */ void deleteList(List* list) { if (list->isEmpty()) { std::cout getSize(); // calc random position

int value = list->remove(position); // test remove method

std::cout

/** * Print the current list to the console * @param list -- pointer to a list ADT */ void printList(List* list) { int size =list->getSize();

if (size) { std::cout read(i); if (i

} // default constructor

/** * Destructor - clean up nodes */ List::~List() { // if list is not empty if (head) {

// repeat until head moved past end of list while (head->next) { Node* temp = head; // hold reference to current head Node head = head->next; // move head pointer to next node in list delete temp; // delete old head Node }

} // is list empty } // destructor

/** * Accessor for the list size property * @return int size (empty = 0) */ int List::getSize() { return size; } // getSize

/** * Signifies if the list is empty or not * @return bool True if empty (size==0) */ bool List::isEmpty() { return size == 0; } // isEmpty

/** * Add a new value into the list at the head, a * specified position, or at the tail if position * is -1 or invalid position * @param value - int value to store * @param position - position in list to store value (default -1) */ void List::insert(int value, int position) { Node* temp = new Node{value, nullptr};

if (position = size) position = size;

// determine where in list to insert if( size == 0 || position == LIST_HEAD) { temp->next = head; // new node points to head head = temp; // move head pointer to new node } else { // middle or tail of list Node* pNode = head; // traverse list to node - 1 pNode = traverse(position - 1);

// insert node between current and next node temp->next = pNode->next; // new node points to next node pNode->next = temp; // current node points to new node

} // where in list

// increment size of the list size++;

} // insert

/** * Remove a value from the list at a specified position and * return it to the caller * @param position - position in the list or tail if -1 * or invalid position * @return - value removed from the list */ int List::remove(int position) { int value = -1;

if(isEmpty()) return value; Node* temp; if(position == LIST_HEAD || size == 1){ //remove head temp = head; head = temp->next; } else{ // middle or tail if(position == LIST_TAIL || position == size) position= size-1;

Node* pNode = traverse(position-1); temp = pNode->next; pNode->next = temp->next; }// where are we removing from value = temp->value; delete temp; size--; return value; } // remove

/** * Return a value from the list at a specified position without * removing it * @param position - position in the list * @return - value found at position (-1 if not found or invalid position) */ int List::read(int position) { int value = -1;

if (size > 0) { Node* pNode = traverse(position); value = pNode->value; }

return value; } // read

/** * Modify a value at a specified position in the list * @param value - new value * @param position - position in the list */ void List::modify(int value, int position) { if (size > 0) { Node* pNode = traverse(position); pNode->value = value; }

} // modify

// Private methods /** * Iterate node pointer to specified position in the list * @param position - 0 to size-1 * @return pointer to Node at List[position] (or null if empty) */ List::Node* List::traverse(int position) { Node* pNode = head; // start at head of list (null if empty)

int counter = 0; // zero indexed list // (don't move if position == 0) while(counter next) { pNode = pNode->next; counter++; } // traversal

return pNode; }

========================= Assignment ============================

So far, we have created a Single Linked-List ADT. It's called a Single because there is only one pointer in each node to link it to a next node. This gives us a list that we can transverse in one direction only, from the head to the tail. With a previous pointer added to the Node structure, traversal of the list could proceed in either direction. A tail pointer could be used to hold the location of the last node in the list. Traversal could begin at the head and move down the list using the next pointers, or the tail and move up the list using the previous pointers. One major benefit is that new nodes can be appended to the end of the list by referencing the tail pointer directly. This cuts down on the traversal of the list from the head across all nodes to append a new node. Inscrting a new node inside the list requircs traversing to the node prior to the inscrtion spot, and then breaking and reassigning the previous and next pointers of the current node and the new node. Removing a node requires traversing to the prior node, and then breaking and reassigning the next and pervious pointers of the nodes that will remain in the list. Assignment - Create a Double Linked List ADT by copying and modifying the Single Linked List ADT. (5pts) - Add a previous pointer to the Node structure, and a tail pointer to the List class. (5pts) - Modify Insert and Remove methods to handle the tail, previous and next pointers. (5pts) - Modify the traversal method to move from tail towards the head if a negative position is given (5pts) - Modify Insert and remove to accept positive and negative positions (5pts extra credit) - Currently 1 is used to signal to insert or remove from the tail. Add a bool parameter that is true if insert should append to the tail (default to true), and true if remove should be from the tail (default to true). - You can ignore position if the new bool parameter is true, otherwise the position will be 0 or positive to traverse from the head, and negative to traverse from the tail So far, we have created a Single Linked-List ADT. It's called a Single because there is only one pointer in each node to link it to a next node. This gives us a list that we can transverse in one direction only, from the head to the tail. With a previous pointer added to the Node structure, traversal of the list could proceed in either direction. A tail pointer could be used to hold the location of the last node in the list. Traversal could begin at the head and move down the list using the next pointers, or the tail and move up the list using the previous pointers. One major benefit is that new nodes can be appended to the end of the list by referencing the tail pointer directly. This cuts down on the traversal of the list from the head across all nodes to append a new node. Inscrting a new node inside the list requircs traversing to the node prior to the inscrtion spot, and then breaking and reassigning the previous and next pointers of the current node and the new node. Removing a node requires traversing to the prior node, and then breaking and reassigning the next and pervious pointers of the nodes that will remain in the list. Assignment - Create a Double Linked List ADT by copying and modifying the Single Linked List ADT. (5pts) - Add a previous pointer to the Node structure, and a tail pointer to the List class. (5pts) - Modify Insert and Remove methods to handle the tail, previous and next pointers. (5pts) - Modify the traversal method to move from tail towards the head if a negative position is given (5pts) - Modify Insert and remove to accept positive and negative positions (5pts extra credit) - Currently 1 is used to signal to insert or remove from the tail. Add a bool parameter that is true if insert should append to the tail (default to true), and true if remove should be from the tail (default to true). - You can ignore position if the new bool parameter is true, otherwise the position will be 0 or positive to traverse from the head, and negative to traverse from the tail