This assignment and the next (#5) involve design and development of a sequential non contiguous and dynamic datastructure called LinkedList. A linked list object is a container consisting of connected ListNode objects. As before, we are not going to use pre-fabricated classes from the c++ library, but construct the LinkedList ADT from scratch. The first step is construction and testing of the ListNode class. A ListNode object contains a data field and a pointer to the next ListNode object (note the recursive definition). #This assignment requires you to 1. Read the Assignment 4 Notes 2. Watch the Assignment 4 Support video 3. Implement the following methods of the ListNode class -custom constructor -setters for next pointer and data 4. Implement the insert and remove method in the main program 5. Scan the given template to find the above //TODO and implement the code needed //TODO in ListNodecpp.h file public: ListNode(T idata, ListNode * newNext); public: void setNext(ListNode * newNext); public: void setData(T newData);

// TODO in main program void remove(ListNode * &front,int value) void insert(ListNode * &front,int value) # The driver is given ListNodeMain.cpp is given to you that does the following tests 1. Declares a pointer called front to point to a ListNode of datatype integer 2. Constructs four ListNodes with data 1,2,4 and adds them to form a linked list. 3. Inserts ListNode with data 3 to the list 4. Removes node 1 and adds it back to test removing and adding the first element 5. Removes node 3 to test removing a middle node 6. Removes node 4 to test removing the last node 7. Attempt to remove a non existent node 8. Remove all existing nodes to empty the list 9. Insert node 4 and then node 1 to test if insertions preserve order 10.Print the list

Main.cpp

#include

#include "ListNodecpp.h" // REMEMBER each ListNode has two parts : a data field // and an address field. The address is either null or points to the next node //in the chain //Requires: integer value for searching, address of front //Effects: traverses the list node chain starting from front until the end comparing search value with listnode getData. Returns the original search value if found, if not adds +1 to indicate not found //Modifies: Nothing int search(ListNode * front, int value); //Requires: integer value for inserting, address of front //Effects: creates a new ListNode with value and inserts in proper position (increasing order)in the chain. If chain is empty, adds to the beginning //Modifies: front, if node is added at the beginning. //Also changes the next pointer of the previous node to point to the //newly inserted list node. the next pointer of the newly inserted pointer //points to what was the next of the previous node. //This way both previous and current links are adjusted

//******** NOTE the use of & in passing pointer to front as parameter - // Why do you think this is needed ?**********

void insert(ListNode * &front,int value); //Requires: integer value for adding, address of front //Effects:creates a new ListNode with value and inserts at the beginning //Modifies:front, if node is added at the beginning.

void addNode(ListNode * &front,int value);

//Requires: integer value for removing, address of front //Effects: removes a node, if list is empty or node not found, removes nothing. //Modifies: If the first node is removed, front is adjusted. // if removal is at the end or middle, makes sure all nececssary links are updated. void remove(ListNode* & front, int value); //Requires: address of front //Effects: prints data of each node, by traversing the chain starting from the front using next pointers. //Modifies: nothing void printList(ListNode * front);

//GIVEN int main() { // Add 3 Nodes to the chain of ListNodes //note AddNode method appends to the end so this will be out of order // the order of the nodes is 1,2 , 4 //Create a daisy chain aka Linked List // ListNode * front = nullptr; printList(front); std::cout<<"********************** "; addNode(front,1); printList(front); std::cout<<"********************** "; addNode(front,2); printList(front); std::cout<<"********************** "; addNode(front,4); printList(front); std::cout<<"********************** "; // the insert method inserts node with value 3 in place insert(front,3); printList(front); std::cout<<"********************** "; // remove the first, so front needs to point to second remove(front, 1); printList(front); std::cout<<"********************** "; // insert it back insert(front,1); printList(front); std::cout<<"********************** "; //remove from the middle remove(front, 3); printList(front); std::cout<<"********************** "; // remove at the end remove(front, 4); printList(front); std::cout<<"********************** "; //remove a non existent node remove(front, 5); printList(front); std::cout<<"********************** "; // remove all nodes one by one leaving only front pointing to null pointer remove(front, 2); printList(front); std::cout<<"********************** "; remove(front, 1); printList(front); std::cout<<"********************** "; // insert at the beginning of the empty list a larger value insert(front, 4); printList(front); std::cout<<"********************** ";

// insert the smaller value at correct position in the front of the chain and change front insert(front, 1); printList(front); std::cout<<"********************** "; }

//GIVEN void printList(ListNode * front){ ListNode * current = front; while (current!=nullptr){ std::cout<getData()<<" "; current=current->getNext(); } if (front ==nullptr) std::cout<<"EMPTY LIST "; }

//GIVEN //searches the nodes starting from front, all the way to the end // trying to match the given value with the data in the node. // if found, it returns the value indicting found //other wise it returns value +1 as a signal that item is not found int search(ListNode * front,int value){ ListNode * current = front; while (current!=nullptr&& current->getData()!=value){ // std::cout<getData()<<" "; current=current->getNext(); } if (current!= nullptr) return current->getData(); return value+1 ; // // to indicate not found. //The calling program checks if return value is the same as search value // to know if its found; I was using *-1 but if search value is 0, then that does not work; }

//GIVEN //creates a new node with data == value void addNode(ListNode * & front ,int value){ ListNode * current = front; ListNode * temp = new ListNode(value); if (front ==nullptr) front=temp; else { while (current->getNext()!=nullptr){ // std::cout<getData()<<" "; current=current->getNext(); } //ListNode * temp = new ListNode(value); current->setNext(temp); }

} //GIVEN TO YOU //remove the node that has the given integer value in its data field void remove(ListNode * &front,int value){ // we NEVER change front, unless the first item is deleted or //an item is added to the front of the list ListNode * current = front; // save the front in current ListNode * previous=current;// save the front as previous //initially both current and previous will point to front //then previous will lag behind current //keep moving along the list by following the next pointer //until either the item is found or we reach the end of the list while (current!=nullptr&& current->getData()!=value){ previous = current; current=current->getNext(); } //if the item is found in the middle or end of the list //then remove the item by skipping over it //is setting the next of the previous to the next of the current if (current!= nullptr&¤t->getData()==value) { previous->setNext(current->getNext()); //if found at the beginning, front needs to be changed to next of current if (current->getData()==front->getData()){ front=current->getNext(); delete current;//release and deallocate the deleted note current=nullptr;//set the pointer to null so its not pointing to junk

} } } //TODO //TODO - USE THE REMOVE ALGORITHM to help you // to set current and previous links according

void insert(ListNode * &front,int value){

//TODO }

ListNode.h

#include #include template // We can create a linked list wich contains items of type T // in our assignments T will be either integer or Song //template class ListNode{ public: T data; // the data field in our case would contain //either an integer a Song public: ListNode * next; // this is a pointer to the next integer or Song

// default constructor constructs a node with //data value as the default data value for T and null link public: ListNode(); // custom constructor #1 constructs a node with data value == data // and next== null public: ListNode(T data); //custom constructor #2 //constructs a node with data value = idata and next == newNext public: ListNode(T idata, ListNode * newNext); public:std::string toString(); //get the address of the next integer or Song public: ListNode * getNext(); //change the next address to newNext public: void setNext(ListNode * newNext); //return the integer or Song public: T getData(); //change the Song to newData public: void setData(T newData); };

Listnodecpp.h

#include #include template // We can create a linked list wich contains items of type T // in our assignments T will be either integer or Song //template class ListNode{ public: T data; // the data field in our case would contain //either an integer a Song public: ListNode * next; // this is a pointer to the next integer or Song

// default constructor constructs a node with //data value as the default data value for T and null link public: ListNode(); // custom constructor #1 constructs a node with data value == data // and next== null public: ListNode(T data); //custom constructor #2 //constructs a node with data value = idata and next == newNext public: ListNode(T idata, ListNode * newNext); public:std::string toString(); //get the address of the next integer or Song public: ListNode * getNext(); //change the next address to newNext public: void setNext(ListNode * newNext); //return the integer or Song public: T getData(); //change the Song to newData public: void setData(T newData); };

makefile

all: g++ main.cpp ListNode.h ListNodecpp.h -o ListNodeChain

output.txt

EMPTY LIST ********************** 1 ********************** 1 2 ********************** 1 2 4 ********************** 1 2 3 4 ********************** 2 3 4 ********************** 1 2 3 4 ********************** 1 2 4 ********************** 1 2 ********************** 1 2 ********************** 1 ********************** EMPTY LIST ********************** 4 ********************** 1 4 **********************