Termbank
  1. A
    1. API
    2. ASAN
    3. Access specifiers
  2. C
    1. Constructor
    2. const
  3. G
    1. GDB
    2. g++
  4. M
    1. Make
    2. Memory Leak
  5. P
    1. Pointer
  6. R
    1. Recursion
  7. S
    1. std
  8. V
    1. Valgrind
Completed: / exercises

MP_LISTS: Linked Lists and Algorithms

Due date: 2024-04-25 23:59.
In this MP you will:
You can download the files for this MP here: mp_lists.zip

Background Information: Template Classes

Identical to what you saw in lecture, template classes provide the ability to create generic container classes. In this MP, you will be writing a List class.
template typename T;
class List {
	// implementation
};
This simply says that our class List has a parametrized type that we will call T. Similarly, the constructor will look like this:
template typename T;
List<T>::List() {
	// implementation
}
We need the template typename T or template class T above all of our functions—it becomes part of the function signature. The keywords class and typename can be interchanged.
Template classes need access to the implementation for compilation. Every time a different class is used as the template, the code must be compiled to support containing it. For example, if you want to make a List int, the compiler must take the generic List T implementation code and replace all the Ts with ints inside it, and compile the result (this process is called template instantiation). Our solution to this is to #include "List.hpp" at the bottom of our List.h file, and not include List.h in our List.hpp file. This ensures that whenever a client includes our header file, he/she also gets the implementation as well for compilation purposes (there are other solutions, but this is how we will solve it in this course).

Background Information: Linked Lists

The interface of this List class is slightly different from what you have seen in lecture. This List has no sentinel nodes; the first node’s prev pointer, and the last node’s next pointer, are both NULL. In lieu of these sentinels, we keep a pointer head to the first node, and a pointer tail to the last node in the List. (In an empty list, both head and tail are NULL.) The List class also has an integer member variable, length, which represents the number of nodes in the List; you will need to maintain this variable.
We use iterators to figure out where we currently are in the list, what is the next/previous node, and to access the data. Iterator class has one member variable, namely a pointer to the node in the list. Some of the core functionality includes moving the pointer, getting current location, and checking the location of the iterator.

Part 1: Debugging & Implementing Linked Lists

In your mp_lists folder, you will find that the List class is split into four .h or .hpp files:
We have provided a partial implementation of a few List functions for this part of the MP. Some functions are written, and some are unwritten. Those functions which are already coded may have a few bugs in them! This part of the MP is to help get you used to debugging certain kinds of logical and memory related bugs, as well as writing pointer manipulation code. All the functions are specified in List.h, and their (potentially empty) implementations are in List.hpp or List-ListIterator.hpp for you to write.
You should use GDB, valgrind, and any other debugging tools or techniques you’re comfortable with to complete the first part of this MP (as well as general debugging in Part 2 and beyond).

Notes on testing

There are two ways to test this MP:
You’re free to run Valgrind (or other tools) on the executables:
valgrind ./mp_lists
valgrind ./test [part=1]
You can also select test cases to run by their names, and run those under valgrind or gdb as well:
./test "List::reverse"
./test "*insert*"
valgrind ./test "*insert*"
gdb --args ./test "*insert*"

List()

This should default construct the list. Keep in mind everything mentioned in the background for the Linked List class.

~List() and _destroy()

Since the List class has dynamic memory associated with it, we need to define all of the Rule of Three. We have provided you with the Copy Constructor and the overloaded operator=.

Insertion

The insertFront Function

Example
For example, if insertFront is called on the List of integers 5 4 7 with the parameter 6, then the resultant List should be 6 5 4 7

The insertBack Function

Example
For example, if insertBack is called on the List of integers 5 4 7 with the parameter 6, then the resultant List should be 5 4 7 6

Testing Your insert Functions

Once you have completed insertFront and insertBack, you should compile and test them. These tests do not rely on your iterator
make test
./test "List::insertFront*"
./test "List::insertBack*"
./test "List::insert*"

Iterator

In order to provide the client code with the ability to read the data from the list in a uniform way, we need to have an iterator. We have provided a list iterator class List-ListIterator.hpp which has some functionality implemented. However, there are a few functions yet to be written as well as some functions with buggy implementations! You will need to worry about all the functions with a @TODO comment:
You will also need to implement the begin() and end() functions in List.hpp to have a way of obtaining an iterator from a List.
Many of the more advanced functionality will be tested by using your iterator. So, you should make sure to debug and implement these after you have finished your insert functions but before you start working too much on the later functionality.

The split Helper Function

Example
For example, if split is called on the List of integers list1 = 1 2 3 4 5, then after calling list2 = list1.split(2) the lists will look like
list1 ==  1 2
list2 ==  3 4 5 

Testing Your split Function

Once you have completed split, you should compile and test it.
make test
./test "List::split*"
You should see images actual-split_*.png created in the working directory (these are generated by repeatedly splitting split.png). Compare them against expected-split_*.png.

The tripleRotate Function

Examples

Testing Your tripleRotate Function

Once you have completed tripleRotate, you should compile and test it.
make test
./test "List::tripleRotate basic"
./test "List::triplerotate simple"

Testing Part 1

Compile your code using the following command:
make test
After compiling, you can run all of the part one tests at once with the following command:
./test [part=1]
Notes
DOUBLE CHECK that you can confidently answer “no” to the following questions:

Part 2

Part 2 is optional and can be completed for extra credit. It requires implementing somewhat challenging functions, but if you made it this far, you can make it all the way!

Reversing

The reverse Helper Function

In List.hpp you will see that a public reverse method is already defined and given to you. You are to write the helper function that the method calls.
Example
For example, if we have a List of integers 1 2 3 4 5 6 7 (with head pointing at 1 and tail pointing at 7) and call the public function reverse(), the resulting List should be 7 6 5 4 3 2 1 (with head pointing at 7 and tail pointing at 1)
Your helper function should be as general as possible! In other words, do not assume your reverse() helper function is called only to reverse the entire list—it may be called to reverse only parts of a given list.
Additionally, the pointers startPoint and endPoint that are parameters to this function should at its completion point to the beginning and end of the new, reversed sublist.
We highly recommend you write this function iteratively. It is possible that you may run out of stack space if you write this function recursively.

The reverseNth Function

Example
For example, if reverseNth is called on the List of integers 1 2 3 4 5 6 7 8 9,
then the call to reverseNth(3) should result in 3 2 1 6 5 4 9 8 7
For the List of integers 1 2 3 4 5 6 the call to
reverseNth(4) should result in 4 3 2 1 6 5
Hint
You should try to use your reverse() helper function here.

Testing Your reverse Functions

Once you have completed reverse and reverseNth, you should compile and test them.
make test
./test "List::reverse"
./test "List::reverseNth #1"
./test "List::reverseNth #2"

Sorting

You will be implementing the helper functions for one more member function of the List template class: sort. This is designed to help you practice pointer manipulation and solve an interesting algorithm problem. In the process of solving this problem, you will implement several helper functions along the way—we have provided public interfaces for these helper functions to help you test your code.

The merge Helper Function

Example
For example, if we have the following lists
list1 =   1 3 4 6  
list2 =   2 5 7  
then after calling list1.mergeWith(list2) the lists will look like
list1 ==   1 2 3 4 5 6 7  
list2 ==    

Testing Your merge Function

Once you have completed merge, you should compile and test it.
make test
./test "List::merge"
You should see the image actual-merge.png created in the working directory if your program terminates properly. This is generated by merging the images tests/merge1.png and tests/merge2.png. Compare this against expected-merge.png.

The mergesort Helper Function

Example
For example, if sort is called on the List of integers 6 1 5 8 4 3 7 2 9
the resulting List should be 1 2 3 4 5 6 7 8 9

Merge Sort — Algorithm Details

Merge Sort is a recursive sorting algorithm that behaves as follows:
In other words, Merge Sort operates on the principle of breaking the problem into smaller and smaller pieces, and merging the sorted, smaller lists together to finally end up at a completely sorted list.

Testing Part 2

Compile your code using the following command:
make test
After compiling, you can run the part two tests at once with the following command:
./test [part=2]
Hint: Comparing similar images
Occasionally diff may tell you that the 2 images differ, but you cannot easily tell the difference with the naked eye. In these scenarios, you could use something like paint.net and put images in different layers, then use difference blend mode, or simply swap back and forth between the layers to see how the image changes when the 2 images are perfectly aligned.
Notes
DOUBLE CHECK that you can confidently answer “no” to the following questions:

Good Luck!

LISTS

Part 1 includes:
  • Constructor, destructor
  • InsertFront, InsertBack
  • Iterator
  • split
  • tripleRotate
Part 2 is extra credit and includes:
  • reverse, reverse Nth
  • merge, mergesort
Note that the autograder does not use the "test" program, but tests in main.cpp.

Allowed filenames: List.h, List.hpp, List-ListIterator.hpp

Warning: You have not logged in. You cannot answer.

Acknowledgments

We would like to express our gratitude to prof. Cinda Heeren and the student staff of the UIUC CS Data Structures course for creating and sharing the programming exercise materials that have served as the basis for the labs used in this course.
Revised by: Elmeri Uotila and Anna LaValle
?
API stands for Application Programming Interface. In the context of this course, you can consider the header files to be such interfaces, as they determine what class functions and properties are public and thus accessible from anywhere.
AddressSanitizer (ASAN) is a memory error detector for C/C++. In this course, the makefiles will typically compile an executable that uses ASAN, with "-asan" at the end of its name.
The two notable access specifiers are:
  • public: class members defined after the public keyword are accessible from outside the class.
  • private: class members are generally private by default and thus not accessible from the outside
Constructor is a special non-static member function of a class that is used to initialize objects of its class type. A constructor is called upon initialization of an object. A constructor without arguments is a default constructor, but constructors that take arguments can be defined.
GDB, the GNU Project debugger, allows you to see what is going on `inside' another program while it executes -- or what another program was doing at the moment it crashed.
GDB can do four main kinds of things (plus other things in support of these) to help you catch bugs in the act:
  • Start your program, specifying anything that might affect its behavior.
  • Make your program stop on specified conditions.
  • Examine what has happened, when your program has stopped.
  • Change things in your program, so you can experiment with correcting the effects of one bug and go on to learn about another.
GNU Make is a tool which controls the generation of executables and other non-source files of a program from the program's source files. Make gets its knowledge of how to build your program from a file called the makefile, which lists each of the non-source files and how to compute it from other files. When you write a program, you should write a makefile for it, so that it is possible to use Make to build and install the program.
Memory leak means that the program is not freeing up memory it reserves. The memory will be freed when the program terminates, but if a program keeps leaking more and more memory without terminating, it can become a huge issue!
A typical way for memory leaks to occur is reserving memory with new and not calling delete before the pointer goes out of scope.
Pointer variables store a memory address as their value. In other words, they point to some data. The data can be accessed by dereferencing the pointer. (Either like *p or p->...)
A recursive function calls itself from within it. The recursion call must be conditional or it would lead to an infinite loop.
Valgrind is another tool besides ASAN that you can use in this course. It can detect many memory-related errors that are common in C and C++ programs and that can lead to crashes and unpredictable behaviour.
const is a keyword meant to mark something as immutable
  • A const object cannot be modified: attempt to do so directly is a compile-time error, and attempt to do so indirectly (e.g., by modifying the const object through a reference or pointer to non-const type) results in undefined behavior.
  • const keyword on an object's member function prevents the object from being modified in the function
  • Pointer declarations can have 2 const keywords, one to make the data that's pointed at unable to be modified and one to make the pointer itself unable to be modified
Using const improves code readability and prevents accidental modification of objects.
g++ is a C++ compiler that we primarily use for this course. It is the C++ compiler for the GNU compiler collection. You may sometimes see gcc being used instead of g++, which was originally the GNU C compiler, but calling gcc generally also compiles .cpp files as C++. However, calling g++ is preferred.
In C++, std stands for Standard Library, which is a collection of commonly useful classes and functions. Typically, these are defined in the std namespace.