Assignment 2: Doubly-linked lists

In this assignment, you will implement a doubly-linked list class, together with some list operations. To make things easier, you’ll implement a list of int, rather than a template class.

#pragma once
/*
  dlist.h
  Doubly-linked lists of ints
 */
class dlist {
  public:
    dlist() { }

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* head() const { return _head; }
    node* tail() const { return _tail; }

    // **** Implement ALL the following methods ****

    // Returns the node at a particular index (0 is the head). If n >= size()
    // return nullptr; if n < 0, return the head of the list.
    // Must run in O(n) time.
    node* at(int n) const;

    // Insert a new value, after an existing one. If previous == nullptr, then
    // the list is assumed to be empty.
    // Must run in O(1) time.
    void insert(node *previous, int value);

    // Delete the given node. Should do nothing if which == nullptr.
    // Must run in O(1) time.
    void remove(node* which);

    // Add a new element to the *end* of the list
    // Must run in O(1) time.
    void push_back(int value);

    // Add a new element to the *beginning* of the list
    // Must run in O(1) time.
    void push_front(int value);

    // Remove the first element. 
    // If the list is empty, do nothing.
    // Must run in O(1) time
    void pop_front();

    // Remove the last element. 
    // If the list is empty, do nothing.
    // Must run in O(1) time
    void pop_back();

    // Get the size of the list
    // Should run in O(n) time at the worst
    int size() const;

    // Returns true if the list is empty
    // Must run in O(1) time
    bool empty() const;

  private:
    node* _head = nullptr;
    node* _tail = nullptr;

    // Add any other private members you need
};

// **** Implement ALL the following functions ****

/* a == b
   Compares two lists for equality, returning true if they have the same
   elements in the same positions. (Hint: it is *not* enough to just compare
   pointers! You have to compare the values stored in the nodes.)

   Must run in O(m) time, where m is the length of the shorter of the two lists.
*/ 
bool operator== (const dlist& a, const dlist& b);

/* a + b
   Returns a new list consisting of all the elements of a, followed by all the
   elements of b (i.e., the list concatenation).

   Must run in O(n) time in the length of the result (i.e., the length of a
   plus the length of b).
*/
dlist operator+ (const dlist& a, const dlist& b);

/* reverse(l)
   Returns a new list that is the *reversal* of l; that is, a new list 
   containing the same elements as l but in the reverse order.

   Must run in O(n) time. 
*/
dlist reverse(const dlist& l);

(You can download this header file.)

You should save the above into dlist.hpp, and put the implementations of the functions (and any methods that you don’t want to implement in the class body) into dlist.cpp. (If you want to, you can implement everything in dlist.hpp by writing the functions as inline, thus creating a “header-only” list library.)

You should download assign2_test.cpp, the test-runner for this assignment, and use it to test your code. As before, it provides a main which will run all the different functions and make sure they are implemented correctly. However, it’s possible in this assignment that some mistakes might show up not as failing tests, but as segment violations (or null-pointer dereferences); i.e., your program will crash instead of the test printing a FAILED message.

You can find both these files on the server in the path /usr/local/class/src. E.g. you could create the directory and copy the files with

mkdir ~/cs133/assign2/
cp /usr/local/class/src/assign2_test.cpp ~/cs133/assign2/
cp /usr/local/class/src/dlist.hpp ~/cs133/assign2/

On the server, you can diagnose segfaults by running your program like this:

catchsegv ./assign2_test

If your program crashes, this will print out a backtrace which shows, among other things, the line number on which the error occurred.

Of course, it’s also possible that your code might mess up the list structure to the point where the test runner gets into an infinite loop. If that happens, look at the most recent message printed for a clue as to where the problem is.

Things to watch out for

Implementations that do not meet the time complexity requirements. E.g., an \(O(n^2)\) implementation where \(O(n)\) is required.
Failing to update the prev pointers when modifying the list structure. Almost every list-modifying method will have to update the prev pointer in an existing node.
Modifying the input lists in operator+ or reverse. Both of these must leave their input lists totally unchanged!

Submission

Save your work in a directory on the server named cs133/assign2/.