Doubly-Linked List Warmup

Assignment written by Keith Schwarz

Part Two: Doubly-Linked List Warmup

A common variant on the traditional linked list is the doubly-linked list. Unlike a traditional linked list, in a doubly-linked list each cell contains a pointer both to the cell that comes after it in the sequence and a pointer to the cell that comes before it in the sequence. This is shown here:

struct Cell {
    string value; // Or whatever type of data you'd like, really
    Cell*  next;  // Pointer to the next cell in the list
    Cell*  prev;  // Pointer to the previous cell in the list
};

Here's how we might draw a doubly-linked list:

A picture of a doubly-linked list containing the cells Marissa, Megan, and Angela, in that order. Marissa's next pointer is to Megan, Megan's is to Angela, and Angela's is nullptr. Angela's prev pointer is to Megan, Megan's is to Marissa, and Marissa's is to nullptr. There is a pointer 'list' that points to Marissa, the first cell in the list

The mechanics for working with doubly-linked lists are, in many ways, similar to those for working with singly-linked lists. There's a distinction between pointers to cells and cells themselves. We form sequences by wiring cells together, as before, though we have to do a bit more bookkeeping to keep track of the prev pointers in addition to the next pointers.

We'd like to give you some practice working with doubly-linked lists before you move on to the core of this assignment. Specifically, we'd like you to write these three functions:

int  lengthOf(Cell* list);
void freeDoublyLinkedList(Cell* list);
void prependTo(Cell*& list, string value);

The first of these takes in a pointer to the first cell in a doubly-linked list, then returns how many cells are in the list. You should implement this function iteratively. The second cleans up all memory used by the given doubly-linked list, and should also be implemented iteratively. The third function function prepends a new cell onto the front of a doubly-linked list.

Feel free to use lecture code from Friday as a reference. If you do, we strongly encourage you to reflect on what parts of the code you could use unmodified, which parts you needed to change, and why.

To summarize, here's what you need to do:

Part Two Requirements

  1. Implement the lengthOf function in DoublyLinkedLists.cpp. Use the “Run Tests” button to confirm you’re passing all the tests for that function.

  2. Implement the freeDoublyLinkedList function in DoublyLinkedLists.cpp. Use the “Run Tests” button to confirm you’re passing all the tests for that function.

  3. Implement the prependTo function in DoublyLinkedLists.cpp. Use the “Run Tests” button to confirm you’re passing all the tests for that function.

Some notes on this problem:

  • All three of these functions assume that the pointer provided is a pointer to the first cell in the linked list (or nullptr if the list has no cells). You do not need to handle the case where you're given a pointer into the middle of the list.

  • You don't need to write your own tests for this section, but you may find it useful to do so.

  • Draw pictures! You don't need to write much code here, but it'll be very important to make sure you know what code you need to write.