******************************node1.h*********************

header file documentation (included as pics)

#ifndef MAIN_SAVITCH_NODE1_H

#define MAIN_SAVITCH_NODE1_H

#include // Provides size_t and NULL

namespace main_savitch_5

{

class node

{

public:

// TYPEDEF

typedef double value_type;

// CONSTRUCTOR

node(

const value_type& init_data = value_type( ),

node* init_link = NULL

)

{ data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields:

void set_data(const value_type& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data:

value_type data( ) const { return data_field; }

// Two slightly different member functions to retreive

// the current link:

const node* link( ) const { return link_field; }

node* link( ) { return link_field; }

private:

value_type data_field;

node* link_field;

};

// FUNCTIONS for the linked list toolkit

std::size_t list_length(const node* head_ptr);

void list_head_insert(node*& head_ptr, const node::value_type& entry);

void list_insert(node* previous_ptr, const node::value_type& entry);

node* list_search(node* head_ptr, const node::value_type& target);

const node* list_search

(const node* head_ptr, const node::value_type& target);

node* list_locate(node* head_ptr, std::size_t position);

const node* list_locate(const node* head_ptr, std::size_t position);

void list_head_remove(node*& head_ptr);

void list_remove(node* previous_ptr);

void list_clear(node*& head_ptr);

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

}

#endif

******************************node1.cpp*********************************

// FILE: node1.cxx

// IMPLEMENTS: The functions of the node class and the

// linked list toolkit (see node1.h for documentation).

// INVARIANT for the node class:

// The data of a node is stored in data_field, and the link in link_field.

#include "node1.h"

#include // Provides assert

#include // Provides NULL and size_t

using namespace std;

namespace main_savitch_5

{

size_t list_length(const node* head_ptr)

// Library facilities used: cstdlib

{

const node *cursor;

size_t answer;

answer = 0;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

++answer;

return answer;

}

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

head_ptr = new node(entry, head_ptr);

}

void list_insert(node* previous_ptr, const node::value_type& entry)

{

node *insert_ptr;

insert_ptr = new node(entry, previous_ptr->link( ));

previous_ptr->set_link(insert_ptr);

}

node* list_search(node* head_ptr, const node::value_type& target)

// Library facilities used: cstdlib

{

node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

if (target == cursor->data( ))

return cursor;

return NULL;

}

const node* list_search(const node* head_ptr, const node::value_type& target)

// Library facilities used: cstdlib

{

const node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

if (target == cursor->data( ))

return cursor;

return NULL;

}

node* list_locate(node* head_ptr, size_t position)

// Library facilities used: cassert, cstdlib

{

node *cursor;

size_t i;

assert (0

cursor = head_ptr;

for (i = 1; (i NULL); i++)

cursor = cursor->link( );

return cursor;

}

const node* list_locate(const node* head_ptr, size_t position)

// Library facilities used: cassert, cstdlib

{

const node *cursor;

size_t i;

assert (0

cursor = head_ptr;

for (i = 1; (i NULL); i++)

cursor = cursor->link( );

return cursor;

}

void list_head_remove(node*& head_ptr)

{

node *remove_ptr;

remove_ptr = head_ptr;

head_ptr = head_ptr->link( );

delete remove_ptr;

}

void list_remove(node* previous_ptr)

{

node *remove_ptr;

remove_ptr = previous_ptr->link( );

previous_ptr->set_link( remove_ptr->link( ) );

delete remove_ptr;

}

void list_clear(node*& head_ptr)

// Library facilities used: cstdlib

{

while (head_ptr != NULL)

list_head_remove(head_ptr);

}

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)

// Library facilities used: cstdlib

{

head_ptr = NULL;

tail_ptr = NULL;

// Handle the case of the empty list.

if (source_ptr == NULL)

return;

// Make the head node for the newly created list, and put data in it.

list_head_insert(head_ptr, source_ptr->data( ));

tail_ptr = head_ptr;

// Copy the rest of the nodes one at a time, adding at the tail of new list.

source_ptr = source_ptr->link( );

while (source_ptr != NULL)

{

list_insert(tail_ptr, source_ptr->data( ));

tail_ptr = tail_ptr->link( );

source_ptr = source_ptr->link( );

}

}

}

Use the Linked List toolkit provided in nodel.h and node1.cpp to perform the following operations. Your code should take an empty list into account and print appropriate messages as needed. You will be creating a main.cpp for the below listed operations: 1. Create a new list with the following values in order: 5, 4, 6, 8, 3 2. Print the values in the list separated by a space 3. Print the value stored in the 3"d node 4. Locate the 3d node in this list and change its value to 7 5. Delete the head node and print the updated list 6. Delete the tail node and print the list 7. Copy the remaining list into a new list pointed to by newHead ptr. Print the values in this new list //FILE: node1.h //PROVIDES: A class for a node in a linked list, and list manipulation // functions, all within the namespace main_savitch_5 ITYPEDEF for the node class: Each node of the list contains a piece of data and a pointer to the /ext node. The type of the data is defined as node::value_type in a typedef statement. The value_type may be any of the built-in C++ classes (int, char,or a class with a copy constructor, an assignment operator, and a test for equality xy) CONSTRUCTOR for the node class: ode ode* initlinkNULL IPostcondition: The node contains the specified data and link. const value-type& init-data value-type(), = /NOTE: The default value for the init_data is obtained from the default constructor of the value_type. In the ANSI/ISo standard, this notation //is also allowed for the built-in types, providing a default value of //zero. The init_link has a default value of NULL //NOTE: /Each of these functions comes in two versions: a non-const version (where Some of the functions have a return value which is a pointer to a node. the return value is nodex) and a const version (where the return value is const node*). EXAMPLES: /const node c // ->link( ) activates the const version of link //1ist search(c,... calls the const version of list search node *pi //p->link ) activates the non-const version of link //list_search(p, calls the non-const version of list search MEMBER FUNCTIONS for the node class: /void set_data(const value_type& new_data) Postcondition: The node now contains the specified new data. void set link(node* new 1ink) Postcondition: The node now contains the specified new link. 40 Ivoid set link(node* new link) Postcondition: The node now contains the specified new link. 42 / 43 value type data const 44 IIPostcondition: The return value is the data from this node. 46 Iconst node* link const 0. 86 IIvoid list head_remove (nodex& head ptr) Precondition: head ptr is the head pointer of a linked list, with at least one node. Postcondition: The head node has been removed and returned to the heap; head ptr is now the head pointer of the new, shorter linked list. 2 IIvoid list_remove(node previous_ptr) Precondition: previous ptr points to a node in a linked list, and this is not the tail node of the list. Postcondition: The node after previous ptr has been removed from the linked list. 7 II 8 IIvoid list clear (node*& head_ptr) Precondition: head_ptr is the head pointer of a linked list. Postcondition: A11 nodes of the list have been returned to the heap, and the head_ptr is now NULL 0 11 03 void list copy(const node* source ptr, node*&head ptr, node*& tail ptr) Precondition: source_ptr is the head pointer of a linked list. Postcondition: head_ptr and tail ptr are the head and tail pointers for a new list that contains the same items as the list pointed to by source_ptr. The original list is unaltered. 08 Ivoid list piece( 9IIconst nodex start ptr, const nodex end ptr, 0 IInodex& headptr, nodex& tail ptr 2 IIPrecondition: start_ptr and end_ptr are pointers to nodes on the same 13 IIlinked list, with the start_ptr node at or before the end_ptr node 4 IIPostcondition: head ptr and tail ptr are the head and tail pointers for a 15 IInew list that contains the items from start ptr up to but not including 16 // end-ptr. The end-ptr may also be NULL, n which case the new list 7 IIcontains elements from start ptr to the end of the list. 9// DYNAMIC MEMORY usage by the toolkit: 0 IIIf there is insufficient dynamic memory, then the following functions throw 21 IIbad_alloc: the constructor, list_head insert, list insert, list_copy