Assignments Office Hours Hall of Fame Notes
Assignments Office Hours Hall of Fame Notes

Lavish Linked Lists

Assigned: 2019-10-31
Due Date: 2019-11-05 by 11:59PM U.S. Central Time

If you're having some trouble on this assignment, click here for some pointers!

Machine learning is hot right now, but do you know what else big companies love? That's right: blockchain! Your managers at Minisoft heard rumors that Bookface are launching a new cryptocurrency; not to be upstaged, they have instructed you to implement a blockchain ledger in time for their cryptocurrency announcement next week. Fearing you won't have time, you Bing "What is blockchain?" and find some Quora answer that says it's basically a linked list.

Satisfied with your cursory search, you set out to implement the best linked list a big tech company has ever seen!

Assignment Spec

In this assignment, your task is to implement a templated linked list.

Getting Started

Get your copy of the assignment repo here: https://classroom.github.com/a/yBddPhuY

For this assignment, we have given you two files:

Background Knowledge

Linked Lists

A linked list is a very standard data structure in computer science. It is designed to efficiently use space when compared to an array. In a linked list, you can remove an element from the list without having to copy other data as you would need to do in an array.

The basic implementation of a linked list uses a head pointer which points to the first element of the list, with each element pointing to the next element, and finally the last element points to null. An illustration of this is shown below:

The most basic operation of a linked list is to insert a node at the front of the list. This is done using the following steps:

This process can be repeated several times to insert more nodes in a list.

The process to remove a node from the front of the list is similar:

Again, to empty the list, this can be repeated until the head pointer points to null. This will effectively empty the list and deallocate all of its memory.

To remove a node from later in this list, you simply traverse the list to find the node before the node you wish to delete, and then execute the removal procedure as if the next pointer in the node you have found was the head pointer. Similarly, to insert a node at the end of the list, you need to find the last node in the list and treat that node as the head node, executing the procedure for inserting at the head with the pointer in that node being treated as the head pointer.

The following website is a helpful tool for visualizing the behavior of these abstract data functions applied to a linked list: https://visualgo.net/en/list

C++ Templates

What good would a linked list be if we could only store one type of data in it? But then again, wouldn't we then have to define a ton of linked list node types to accommodate all the possible datatypes? Luckily, there is a better way: templates!

C++ templates are most similar to generics in Java, which you have already used with ArrayList e.g.: ArrayList<Double>, or ArrayList<Integer>. Templates/generics are a way to parameterize the type of a function or class. For instance, say we wanted to implement a function that returns the greater of its two parameters (the max function). We don't care what type the two parameters are; as long as they have some inherent ordering, they are valid candidates for our function. So we abstract the type away to a template type:

template <class T>

Now "T" represents some arbitrary type. From here, we just define the maximum function normally, except we use T as the type specifier:

template <class T>
T Max(T lhs, T rhs) {
    if (lhs > rhs) {
        return lhs;
    } else {
        return rhs;
    }
}

A question that might have crossed your mind is: why are we implementing the list in a header file that is included in another header file? And where is the cpp file? The reason we do this is to work around a C++ template restriction. Behind the scenes, when the compiler reads a section like:

int a = 8;
int b = 5;
int x = Max(a, b);

...it then creates an implementation for Max that accepts ints. If the template declaration for Max was in a cpp file, then the compiler could not read the source, and would have no idea how to make its int version of Max. But as long as Max is implemented in an included header, the compiler will be able to read it, and substitute int for T to make the requisite function.

Be warned: if you were to pass a type in to this function that did not have operator > overloaded, you would then get a compiler error, and would either have to overload operator > or find an other way of getting the max.

C++ Big 5

A large part of C++'s resource management model are the big five functions: the copy constructor, the move constructor, the destructor, the copy assignment operator, and the move assignment operator. The Rule of the Big 5 is that if any one of these are implemented in a C++ class, all of them must be implemented. The idea behind this is that C++ assumes very little when it comes to memory management. A lot of C++ objects manage sub-object memory, like our LinkedList that manages many Nodes' memory. The best C++ can do without further help is create the memory when the LinkedList is initialized, and destroy it when it goes out of scope. However, the larger object can be copied, moved around, and destroyed early, and C++ would have no idea what to do then. This is where the Big 5 come in to save the day. If you write proper Big 5 functions, you can expect your object's memory to be properly freed when the time comes.

1. Copy Constructor

MyObject(const MyObject &source);

The job of a copy constructor is to copy over all of the memory of source into this. The memory should not be shared, and should be brand new, belonging only to the new object.

2. Move Constructor

MyObject(MyObject &&source) noexcept;

Unlike the copy constructor, which keeps source intact, the move constructor will consume source, and move source's memory into this. This is why source is an rvalue reference, which is a reference to an object with no permanent memory address.

3. Destructor

~MyObject();

The destructor frees all of the memory associated with an instance of MyObject. Remember that any memory allocated on the heap (using the new keyword) must be freed once it's done being used, or else you will encounter a memory leak.

4. Copy Assignment Operator

MyObject& operator=(const MyObject &source);

The copy assignment operator does almost the exact same thing as the copy constructor, except it returns the copy of source.

5. Move Assignment Operator

MyObject& operator=(MyObject &&source) noexcept;

Again, this does the same as the move constructor, but it returns the object that source's memory was moved into.

Copy v.s. Move

Invoking a copy is something you might be quite familiar with already! Here's an example:

std::string string_to_copy = "Nobody likes a copycat!";
std::string new_string = string_to_copy; // Copy assignment invoked
// string_to_copy is not attached to new_string because it was a deep copy

Invoking move is a little less intuitive. The easiest way is to do the exact same thing you would do with a copy, but wrap the source in a std::move call:

std::string string_to_move = "Movin' out!";
std::string new_string = std::move(string_to_move); // Move assignment invoked
// string_to_move no longer owns that string; new_string does.

That example is helpful for tests, but feels a bit contrived. Here's a real world example of invoking a move:

std::string get_string_to_move() {
    std::string string_to_move = "Gotta move that gear up!";
    return string_to_move;
    // string_to_move is going out of scope with this return, so it no longer
    // needs a copy of its memory
}

std::string new_string = get_string_to_move(); // Move assignment invoked.

Grading and Deliverables

Restrictions

You are not allowed to use any STL classes other than vector in the vector constructor. You must handle all of the memory yourself using new and delete.

Hints

We would like to suggest that you implement the insertion and comparison operators to test before handling the operators that remove nodes from the list, since they have a higher chance of having bugs. Again, work in the smallest testable steps possible. Each function should be very small, and you should be testing them as you go. Finally, remember that as you implement each function, you may want to revisit those earlier tests, since you are adding more functionality as you go that could be relevant to those tests.