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. You will then use this data structure to implement two very important algorithms in graph search, breadth-first search and depth-first search, applied to 2D mazes.

You can obtain the code by typing

git clone https://github.com/ursinus-cs174-f2022/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
• Implement depth-first search and breadth-first search

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.

Linked List Programming Tasks (36 Points)

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++.

Maze Programming Tasks (14 Points)

Now that we have a doubly linked list implementation, let's do something with it! The ability to add and remove efficiently from both the beginning and end allows the linked list to be used both as a queue (first in first out) and a stack (last in first out). You will use this to implement two important graph traversal algorithms known as breadth-first search and depth-first search, respectively. For more info on these algorithms in general, see my class notes from artificial intelligence (best viewed in Chrome). For now, I'll give a brief overview of each of these algorithms.

Breadth-First Search

Below is pseudocode for breadth-first search. It maintains a "frontier" of locations to visit next, and it visits them in the order that they were added to the list. Upon visiting each location, it adds that location's neighbors to the list, until everything has been visited

Depth-First Search

Below is pseudocode for depth-first search. It is incredibly similar to breadth-first search, but only a single line is different! But this makes all the difference as a search strategy

Your Task

Fill in the traverse method in maze.cpp to implement breadth-first search and depth-first search, as applied to 2D mazes. This code stores the maze as a 2D array of chars, where

• An at symbol @ means occupied (this is the darkest character we can make)
• A space means unoccupied and unvisited
• A period . means unoccupied but visited

Your code will go through and changed unoccupied cells to visited according to the BFS and DFS algorithms. For each cell at location [i, j], you want to check the 4 neighbors

• left: [i, j-1]
• right: [i, j+1]
• up: [i-1, j]
• down: [i+1, j]

You should only add a neighbor to the list if it is within the bounds of the array and a space (unvisited/unoccupied).

To keep things simple, you can used a LinkedList<int> for your frontier and refer to each location by a unique number, instead of by both a row and column index. If the maze has rows number of rows and columns, then one possible scheme to convert a row/column index [i, j] into a unique number is

• Location [i, j] can be represented by the int i*rows+j
• An int idx can be converted back to a location by the equations:
  • i = idx / rows; //(floor divide)
  • j = idx % rows;

The entry point for the code is in mazetester.cpp. It takes a single command line argument which is a path to the maze. I've provided one maze with this homework

but you may want to try your own! Below is a working implementation of breadth-first search

Below is a working implementation of depth-first search