MP_LISTS: Linked Lists and Algorithms¶

• learn to manipulate linked memory by writing functions to modify linked lists;
• practice debugging more complex code;
• practice using templates;
• get familiar with iterators.

Background Information: Template Classes¶

template typename T;
class List {
	// implementation
};

template typename T;
List<T>::List() {
	// implementation
}

Background Information: Linked Lists¶

Part 1: Debugging & Implementing Linked Lists¶

• List.h
• List.hpp
• List-ListIterator.hpp
• List-given.h

Notes on testing¶

• Using make to make main.cpp into ./mp_lists, which allows you to write your own lists to test.
• Using make test to make ./test, which allows you to run the automated tests.

valgrind ./mp_lists
valgrind ./test [part=1]

./test "List::reverse"
./test "*insert*"
valgrind ./test "*insert*"
gdb --args ./test "*insert*"

List()¶

~List() and _destroy()¶

• You will need to implement the _destroy() helper function called by operator= (the assignment operator) and the destructor ~List()
• The _destroy() function should free all memory allocated for ListNode objects.

Insertion¶

The insertFront Function¶

• This function takes a data element and prepends it to the beginning of the list.
• If the List is empty before insertFront is called, the List should have one element with the same value as the parameter.
• You may allocate new ListNodes.

The insertBack Function¶

• This function takes a data element and appends it to the end of the list.
• If the List is empty before insertBack is called, the List should have one element with the same value as the parameter.
• You may allocate new ListNodes.

Testing Your insert Functions¶

make test
./test "List::insertFront*"
./test "List::insertBack*"
./test "List::insert*"

Iterator¶

• ListIterator& operator++()
• ListIterator operator++(int)
• ListIterator& operator--()
• ListIterator operator--(int)
• bool operator!=(const ListIterator& rhs)

The split Helper Function¶

• This function takes in a pointer start and an integer splitPoint and splits the chain of ListNodes into two completely distinct chains of ListNodes after splitPoint many nodes.
• The split happens after splitPoint number of nodes, making that the head of the new sublist, which should be returned. In effect, there will be splitPoint number of nodes remaining in the current list.
• You may NOT allocate new ListNodes

list1 ==  1 2
list2 ==  3 4 5 

Testing Your split Function¶

make test
./test "List::split*"

The tripleRotate Function¶

• This function will rotate every three elements once to the left.
• The rotation will be wrapped around for every three elements (Ex: 123 - 231).
• If the length of List is not a multiple of three, then it will do nothing for the last 1 or 2 elements.
• You may NOT allocate new ListNodes in this function.

• For example, if tripleRotate is called on the list of integers 1 2 3 4 5 6, then it should result in 2 3 1 5 6 4.

• If tripleRotate is called on the list of integers where the list length is not a multiple of 3: 1 2 3 4 5, then it should result in 2 3 1 4 5.

Testing Your tripleRotate Function¶

make test
./test "List::tripleRotate basic"
./test "List::triplerotate simple"

Testing Part 1¶

• These tests are deliberately insufficient. We strongly recommend augmenting these tests with your own.
• Be sure to think carefully about edge cases and reasonable behavior of each of the functions when called on an empty list, or when given an empty List as a parameter.
• It is highly advised to test with lists of integers before testing with lists of HSLAPixels.
• Printing out a List both forward and backwards (eg, using an iterator or a custom print function) is one way to check whether you have the double-linking correct, not just forward linking. Printing the size may also help debug other logical errors.

• Did I allocate new memory in functions that disallow it?
• Did I modify the data entry of any ListNode?
• Do I leak memory?

Part 2¶

Reversing¶

The reverse Helper Function¶

• This function will reverse a chain of linked memory beginning at startPoint and ending at endPoint.
• The startPoint and endPoint pointers should point at the new start and end of the chain of linked memory.
• The next member of the ListNode before the sequence should point at the new start, and the prev member of the ListNode after the sequence should point to the new end.
• You may NOT allocate new ListNodes.

The reverseNth Function¶

• This function accepts as a parameter an integer, n, and reverses blocks of n elements in the list.
• The order of the blocks should not be changed.
• If the final block (that is, the one containing the tail) is not long enough to have n elements, then just reverse what remains in the list. In particular, if n is larger than the length of the list, this will do the same thing as reverse.
• You may NOT allocate new ListNodes.

Testing Your reverse Functions¶

make test
./test "List::reverse"
./test "List::reverseNth #1"
./test "List::reverseNth #2"

Sorting¶

The merge Helper Function¶

• This function takes in two pointers to heads of sublists and merges the two lists into one in sorted order (increasing).
• You can assume both lists are sorted, and the final List should remain sorted.
• You should use operator< on the data fields of ListNode objects. This allows you to perform the comparisons necessary for maintaining the sorted order.
• You may NOT allocate new ListNodes!

list1 =   1 3 4 6  
list2 =   2 5 7  

list1 ==   1 2 3 4 5 6 7  
list2 ==    

Testing Your merge Function¶

make test
./test "List::merge"

The mergesort Helper Function¶

• This function sorts the List using the merge sort algorithm, explained below.
• You should use operator on the data fields of ListNode objects. This allows you to perform the comparisons necessary for sorting.
• You should use the private helper functions you wrote above to help you solve this problem.
• You may NOT allocate new ListNodes

Merge Sort — Algorithm Details¶

• Base Case: A List of size 1 is sorted. Return.
• Recursive Case:
• Split the current List into two smaller, more manageable parts
• Sort the two halves (this should be a recursive call)
• Merge the two sorted halves back together into a single list

Testing Part 2¶

• These tests are deliberately insufficient. We strongly recommend augmenting these tests with your own.
• Be sure to think carefully about reasonable behavior of each of the functions when called on an empty list, or when given an empty List as a parameter.
• It is highly advised to test with lists of integers before testing with lists of HSLAPixels.
• Printing out a List both forward and backwards is one way to check whether you have the double-linking correct, not just forward linking. Printing the size may also help debug other logical errors.

• Did I allocate new memory in functions that disallow it?
• Did I modify the data entry of any ListNode?
• Do I leak memory?

Good Luck!¶

Acknowledgments¶