The goal of this assignment is to reinforce linked lists in C++.

Your job is to supply the implementations of the functions in list.h by creating a file list.cpp and including the implementations in that file.

If you are successful, the output from try_list_methods.cpp will look like the following output sample.

[1, 2, 3, 4, 5, 6, 7]

1

[2, 3, 4, 5, 6, 7]

0

[-22, 1, 2, 3, 4, 5, 6, 7]

[1, 2, 3, 4, 5, 6, 7]

1

[1, 2, 3, 4, 5, 6, 7, 238]

[1, 2, 3, 4, 5, 6, 7]

[1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 238]

[1, 2, 3, 4, 5, 6, 7, 238]

[1, 2, 3, 4, 5, 6, 7]

[1, 9, 2, 9, 9, 3, 9, 4, 5, 6, 9, 9, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8]

[1, 9, 2, 9, 9, 3, 9, 4, 5, 6, 9, 9, 7, 8, 9]

8

[1, 2, 3, 4, 5, 6, 7, 8]

[1, 2, 3, 4, 5, 6, 7]

[1, 2, 3, 4, 5, 6, 7, 8]

0

0

The linked list toolkit with node is included in the files provided. Also, there is a package of utility functions used in try_list_methods.cpp.

There are some important points you should observe in your work:

- The list parameters are const, so your implementations should not attempt to change the parameters.

- The first few functions, tail, head, list_is_empty and cons, will be implemented working directly with nodes or using the toolbox as you see fit.

- The remaining functions, from the two append methods onward, should be implemented just using the first four functions. You may also use NULL when an empty list is needed.

- Algorithms are provided below (equals method) for these latter functions. While you dont have to use them, they are about as straightforward as possible.

equals

As an illustration of how to interpret the algorithms, here is the method equals which compares two lists for equality. See the code below for the function header and the implementation. We could describe the algorithm used as follows:

- If list1 is empty then return true if list2 is also empty, return false if list2 is not empty.

- Otherwise, if list2 is empty, return false (because list1 is not)

- Otherwise, if the head of list1 is not equal to the head of list2 then return false

- Otherwise, compare the tail of list1 with the tail of list2 for equality and return the result.

 bool equals(const list list1, const list list2) { if(list_is_empty(list1)) { 

 return list_is_empty(list2); } else if(list_is_empty(list2)) 

 return false; else if(head(list1) != head(list2)){ 

 return false; } else { 

 return equals(tail(list1), tail(list2)); } 

}

Methods in list.cpp:

list append(const list lst, value_type val)

- if lst is empty, return a list consisting of just val

- Otherwise, cons the head of lst to the result of appending val to the tail of lst

list append(const list list_first, const list list_second)

- If list_first is empty, just return list_second

- Otherwise, append the tail of list_first to list_second and cons the head of list_firstto that

list remove_all_of(const list lst, value_type val)

- If lst is empty, return it

- If the first element of lst is equal to val then return the result of removing all instances of val from the tail of lst

- Otherwise, get the result of removing all instances of val from the tail of lstand cons the head of lst to that

list remove_last(const list lst)

- Use assert to check that lst is not empty

- If the tail of lst is empty, return the empty list

Otherwise, remove the last element from the tail of lst and cons the head of lstto that

value_type last(const list lst)

- Use assert to check that lst is not empty

- If the tail of lst is empty, return the head of lst

- Otherwise, return the last element of the tail of lst

node.h file

#ifndef ASSIGN04_LINKED_LISTS_LIST_H #define ASSIGN04_LINKED_LISTS_LIST_H

#include "node1.h"

typedef node::value_type value_type;

typedef node *list;

list tail(list lst);

/* Return a list consisting of the list pointed by head_ptr without the first * element. * It is acceptable to use part or all of the argument list provided that no * change is made to the list. * * precondition: the list pointed to by head_ptr is not empty. */

value_type head(list lst);

/* Return the first element of the list pointed to by head_ptr. * * precondition: the list pointed by head_ptr is not empty. */

bool list_is_empty(list lst);

/* Return true if and only if the list 'head' is empty. */

list cons(value_type val, const list lst);

/* Return a list that consists of 'val' followed by the list pointed to by head_ptr. * It is acceptable to use part or all of the argument list provided that no * change is made to the list. */

/* Implement these using just the functions above: */

list append(const list lst, value_type val);

/* Create a new list that starts with the elements in the list pointed * to by head_ptr and ends with 'val'. * Return a pointer to the head of the new list. */

list append(const list lst_first, const list lst_second);

/* Return a new list that consists of the two lists combined * into one list. * It is acceptable to use part or all of one or both argument lists provided that * no change is made to them. */

list remove_all_of(const list lst, value_type val);

/* Create and return a new list that contains the elements of head_ptr that * are not equal to val. */

list remove_last(const list lst);

/* Create a new list with the same values as the list pointed to by * head_ptr but omitting the last element. * * precondition: the list pointed to by head_ptr is not empty. */

value_type last(const list lst);

/* Return the last value in the list pointed to by head_ptr.

* precondition: the list pointed to by head_ptr is not empty. */

bool equals(const list list1, const list list2);

#endif //ASSIGN04_LINKED_LISTS_LIST_H

node1.cpp file

#include "node1.h" #include // Provides assert #include // Provides NULL and size_t

using namespace std;

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 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != 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 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != 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(); } }

node1.h file

#ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H

#include // Provides size_t and NULL

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

try_list_methods.cpp file

#include "list.h" #include "utility.h" #include using namespace std;

int main() { double data1[] = {1,2,3,4,5,6,7,0}; list lst = build_list(data1); print_list(lst);

cout << head(lst) << endl;

cout << tail(lst) << endl;

cout << list_is_empty(lst) << endl;

list lst2 = cons(-22, lst); cout << lst2 << endl; cout << lst << endl;

cout << list_is_empty(NULL) << endl;

lst2 = append(lst, 238); cout << lst2 << endl; cout << lst << endl;

list lst3 = append(lst, lst2); cout << lst3 << endl; cout << lst2 << endl; cout << lst << endl;

double data4[] = {1, 9, 2, 9, 9, 3, 9, 4, 5, 6, 9, 9, 7, 8, 9, 0}; list lst4 = build_list(data4); cout << lst4 << endl; list lst5 = remove_all_of(lst4, 9); cout << lst5 << endl; cout << lst4 << endl;

cout << last(lst5) << endl; cout << lst5 << endl;

list lst6 = remove_last(lst5); cout << lst6 << endl; cout << lst5 << endl;

double data7[] = {1, 2, 3, 4, 5, 0}; double data8[] = {1, 2, 3, 0}; double data9[] = {1, 2, 3, 5, 4, 0}; list lst7 = build_list(data7); list lst8 = build_list(data8); list lst9 = build_list(data9); cout << equals(lst7, lst8) << endl; cout << equals(lst7, lst9) << endl; cout << equals(lst7, lst7) << endl; }

utility.cpp file

#include "utility.h" #include using namespace std;

node *list1() { double data[] = {2, 3, 2, 3, 3, 2, 3, 3}; int size = 8; return build_list(data, size); }

/** * Assumes that values is a list that is 0 terminated. */ node *build_list(node::value_type values[]) { int num = 0; while(values[num] != 0) num++; return build_list(values, num); }

node *build_list(node::value_type values[], int number) { if(number == 0) return NULL; else { node *head = NULL; list_head_insert(head, values[0]); //cout << "initial build list: "; //print_list(head); node *tail = head; for(int i = 1; i < number; i++ ) { list_insert(tail, values[i]); //cout << "after insert "; //print_list(head); tail = tail->link(); } return head; } }

void print_list(node* head) { cout << "["; while(head != NULL) { cout << head->data(); if(head->link() != NULL) cout << ", "; head = head->link(); } cout << "]" << endl; }

std::ostream & operator<<(std::ostream &str, const node* head) { str << "["; while(head != NULL) { str << head->data(); if(head->link() != NULL) str << ", "; head = head->link(); } str << "]";

return str; }

utility.h file

#ifndef ASSIGN04_LINKED_LISTS_UTILITY_H #define ASSIGN04_LINKED_LISTS_UTILITY_H

#include "node1.h" #include

node *list1(); node *build_list(node::value_type values[], int number); node *build_list(node::value_type values[]); void print_list(node* head); std::ostream & operator<<(std::ostream &str, const node* head);

#endif //ASSIGN04_LINKED_LISTS_UTILITY_H