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

Assignment Spec

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

The rubric can be found here: https://courses.grainger.illinois.edu/cs126/sp2020/assignments/linked-lists-rubric.pdf.

Solutions can be found here: https://github.com/CS126SP20/linked-list-solutions.

Goals

• Memory Management
• Templates
• Iterators
• Linked Lists

Gradescope

You will need to submit your GitHub repository to Gradescope. There is a linter which is run on each submission; the results of the linter will be viewable by your code moderator when grading.

Getting Started

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

For this assignment, we have given you two files:

• ll.h - This header contains all of the declarations for the linked list interface. You may not change the public interface of this class. You are free to add any private methods, as well as constructors to the iterator and const_iterator classes.
• ll.hpp - This file is where all of your function implementations will go.

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:

• Create the new list node containing the data to be inserted.
• Update the next pointer in the new list node to point at the same node the head pointed to.
• Change the head pointer to point at the new node.

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:

• If the list is empty, do nothing and stop.
• Create a temp pointer that points to the current head node.
• Update the head pointer to point to the next node.
• Delete the temp node.

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 <typename T>
T Max(T lhs, T rhs) {
  return lhs > rhs ? lhs : 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 .cc 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 .cc 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 GetStringToMove() {
  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

• Implement all of the public functions of the linked list class:
  • LinkedList() - The default constructor which should construct an empty list.
  • explicit LinkedList(const std::vector<ElementType>& values) - A constructor that creates a linked list containing, in order, all of the elements from the values vector.
  • LinkedList(const LinkedList& source) - Deep copy constructor for a linked list.
  • LinkedList(LinkedList&& source) noexcept - Move constructor for a linked list.
  • ~LinkedList() - Destructor for a linked list.
  • LinkedList& operator=(const LinkedList& source) - Copy assignment operator for a linked list.
  • LinkedList& operator=(LinkedList&& source) noexcept - Move assignment operator for a linked list.
  • void push_front(const ElementType& value) - Add a new element to the front of the linked list.
  • void push_back(const ElementType& value) - Add a new element to the end of the linked list.
  • void pop_front() - Remove the front element from the linked list and de-allocate its data. If the list is empty, do nothing.
  • void pop_back() - Remove the back element from the linked list and de-allocate its data. If the list is empty, do nothing.
  • RemoveOdd() - Remove all odd-indexed elements from the list. Remember that the list is zero-indexed, meaning the first element is even-indexed.
  • RemoveNth() - Remove the nth element from the list.
  • void clear() - Delete all data in the linked list, returning the list to the same state as the default constructor.
  • ElementType front() const - Return a copy of the ElementType element stored in the front of the list. This does not modify the list at all. If the list is empty, you can throw an exception.
  • ElementType back() const - Return a copy of the ElementType element stored in the back of the list. This does not modify the list at all. If the list is empty, you can throw an exception.
  • int size() const - Return the number of elements in the list.
  • bool empty() const - Return true if the list has no elements, otherwise false.
  • bool operator==(const LinkedList& rhs) const - This function compares the list element by element, returning true if each element pair was equal, else false.
  • iterator begin() and const_iterator begin() const - These functions return an iterator and const_iterator respectively that points to the start of the list.
  • iterator end() and const_iterator end() const - These functions return an iterator and const_iterator respectively that points to one past the end of the list.
• Implement external methods that operate on LinkedLists:
  • std::ostream& operator<<(std::ostream& os, const LinkedList& list) - This should print the ElementType elements stored in the list using the << operator from the ElementType class to print the list with a comma and space separating each element. For example, a list containing 3->2->5 should print out as 3, 2, 5.
  • bool operator !=(const LinkedList& lhs, const LinkedList& rhs) - This function will compare the list element by element, returning false if they are all equal, otherwise true.
• Implement both the const and nonconst forms of the iterator interface found in ll.h.
• Write tests of the functions you have implemented.

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.