Overview / Logistics

The purpose of this assignment is to give you practice designing collections, and to demonstrate mastery of object references and pointers in C++ while implementing a doubly-linked list data structure from scratch. In the next part of this assignment, you will use this data structure to solve mazes.

You can obtain the code by typing

git clone https://github.com/ursinus-cs174-s2022/HW4_DoublyLinkedList.git

When you are finished, upload your linkedlist.h and linkedlist.cpp files to canvas.

Learning Objectives

• Gain experience using information hiding and object references to implement a user-friendly collection class.
• Use object references to perform efficient lookups yielding constant time operations in a collection
• Manage dynamic memory in C++
• Use templates in C++ to write general purpose code

Background

In class, we showed how it is possible to remove an item from the front of a singly-linked list in "constant time" (i.e. no loops) by simply referencing the head (click here to review that code). We then showed that if we want to be able to remove a node from the end of the list in constant time, we instead have to store a tail with arrows going backwards instead of forwards. To get the best of both worlds, we can implement a doubly-linked list in which every node has both a pointer to the previous node and to the next node, and there's both a head and a tail:

This data structure makes it possible to add/remove from the beginning/end of the list int constant time. We now have to maintain two arrows for every node, which makes some of the operations more complicated, but this is a relatively small cost to pay for the functionality it affords.

Programming Tasks

Your job will be to fill in methods to create a functional doubly-linked list and to maintain its structure. All operations should run in constant time (i.e. no loops) except for toArray() and remove(Item value) methods. You will have to maintain the proper object references to enable this efficiency. You should refer to the linkedlist.cpp file we wrote in class, though your implementation will differ in several key ways:

• The inner node class will have to have both a next and a prev reference (for forward and backwards arrows, respectively)
• The main doubly-linked list class will need to have both a head and a tail.
• This code uses templates instead of void* pointers. Refer to myvector.cpp from the last lab to see how to define class methods with templates, and how to declare which types will be used with them at the bottom of the C++ file.

Methods To Implement

Lots of information and hints have been provided in the header file linkedlist.h, but they are repeated below for completeness. Each method is worth 4 points.

• void addFirst(Item value): Add an item to the beginning of the doubly-linked list. This method should run in constant time
• void addLast(Item value): Add an item to the end of the doubly-linked list. This method should run in constant time
• Item removeFirst(): Remove and return the first item from the doubly-linked list, if it exists. This method should run in constant time.
• Item removeLast(): Remove and return the last item from the doubly-linked list, if it exists. This method should run in constant time.
• Item* toArray(size_t* N): Return an array representation of the items in the doubly-linked list, and return their length by reference.
• void print(): Print out the linked list using ==> to separate items. For instance, if the list has 1, 2, 3, it should be printed out as

  1 ==> 2 ==> 3 ==>

• ~LinkedList(): The destructor should clean up all dynamically allocated node wrappers so that there are no memory leaks from this class. As a hint, you can use your removeFirst() or removeLast() methods as helper methods here to make this easier.
• Item remove(Item value): Remove and return the first occurrence of an item from the doubly-linked list, if it exists. This method does not have to run in constant time, and should probably use a while or do while loop)
• size_t size(): Return how many elements are currently stored in the doubly-linked list. This method should run in constant time. The easiest way to do this is by storing a private variable that tracks the size as different operations are performed. It should be fairly trivial if you've been updating that variable in your other methods as you've been going along.

Testing

You are encouraged to write simple tests to test your methods in driver.cpp. You can build just this file by typing make driver. In the spirit of incremental development, you should test one method at a time.

Once you are confident they are working, you can use a rigorous tester I provided that's similar to the one on lab 5. For instance, you can run the tester with ./tester 1000 0, and it will try out 1000 operations with the pseudorandom seed 0. It will compare your implementation of a doubly-linked list to the STL List class in C++.