CS5040 Linked List

Requirements

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

The archive list_methods.zip is not a project but provides the files to start a project. 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_first to 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 lst and 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 lst to 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 l
• If the tail of lst is empty, return the head of lst
• Otherwise, return the last element of the tail of lst