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.hpp
  Doubly-linked lists of ints
 */
#include <vector>

/* dlist
   Doubly-linked list class. 
*/
class dlist {
  public:
    struct node
    {
        int value;
        node* next;
        node* prev;
    };

    /* head(), tail()
       Returns the head/tail nodes of the list. These functions are provided
       for you.
    */
    node* head() const { return hd; }
    node* tail() const { return tl; }

    /* constructor
       You do not need to add any code to the constructor, since lists start
       as empty.
    */
    dlist() { }

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

    /* destructor
       Delete all nodes in the list.

       Must run in O(n) time.
    */
    ~dlist();

    /* copy constructor
       Construct a copy of the `original` list. The copy must not share any
       node pointers with the original list.

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

    /* a = b  (copy assignment)
       Copy all values in `b` into `a`. After the copy, `a` and `b` must not
       share any node pointers. 

       Must run in O(n) time.
    */
    dlist& operator= (const dlist& original);

    /* at(i)
       Returns a pointer to the i-th node (head = index 0, tail = size() - 1).
       If i < 0, return the head. If i >= size, return the tail.

       Must run in O(i) time.
    */
    node* at(int i) const;

    /* insert(a, value)
       Insert a new node after `a`, containing the `value`. If 
       `a == nullptr` then insert the new node *before* the head.

       Must run in O(1) time.
    */
    void insert(node *a, int value);

    /* erase(which)
       Delete the given node. If which == nullptr, then this function does 
       nothing.

       Must run in O(1) time.
    */
    void erase(node* which);

    /* erase(i)
       Erase the node at index i (indexes work as for at()). If i < 0, 
       erase the head, if i >= size(), erase the tail.

       Must run in O(i) time.
    */
    void erase(int i);

    /* remove(x)
       Remove the *first* node whose value is `x`. If `x` does not occur in the 
       list, then nothing should be removed. If multiple nodes have `x` as
       their values, only the first (closest to the head) should be removed.

       Must run in O(n) time.
    */
    void remove(int x);

    /* push_back(value)
       Add a new node containing value at the *end* of the list. 

       Must run in O(1) time.
    */
    void push_back(int value);

    /* push_front(value)
       Add a new node containing value before the head of the list. 

       Must run in O(1) time.
    */
    void push_front(int value);

    /* pop_front()
       Remove the first (head) element. If the list is empty, do nothing.

       Must run in O(1) time.
    */
    void pop_front();

    /* pop_back()
       Remove the last (tail) element. If the list is empty, do nothing.

       Must run in O(1) time.
    */
    void pop_back();

    /* size()
       Returns the size of the list. 

       Must run in O(n) in the worst case.
    */
    int size() const;

    /* empty()
       Returns true if the list is empty.

       Must run in O(1) time.
    */
    bool empty() const;

    /* to_vector()
       Converts the list to a vector containing the same values and returns it.

       Must run in O(n) time.
    */
    std::vector<int> to_vector() const;

  private:
    node* hd = nullptr; // Pointer to the first node
    node* tl = nullptr; // Pointer to the last node

    // Add any other private members you need
};

You can download this header file. On the server, you can find a copy of the above file in /usr/local/class/src/cs133/dlist.hpp.

As with other assignments, you can put the implementations for all the class methods into the .hpp file if you want, or you can put them in a separate .cpp file and compile that with the test file, assign2_test.cpp.

You can 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. Failed tests will include a link back to this webpage, pointing to a description of the test that was failed (see below).

Note: In this and all future assignments, memory leaks or errors count as failure, but the test-runner by itself cannot detect these. You must run your submission inside valgrind, or use the test-assignment script to check for memory leaks/errors.

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. (Ctrl-C can be used to kill a program in an infinite loop.)

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

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

Testing for big-O runtimes

The test-runner for assignment 2 contains some experimental code to check whether some of your functions have the required big-O runtime complexities. Due to the imprecise nature of timing software, failures in this area will be reported as warnings rather than hard failures. However, you will want to look into any warnings that are printed in this section; if I see any warnings about incorrect big-O complexities, I will look at your code and it won’t pass if you are using an algorithm with the incorrect runtime complexity.

Things to watch out for

Submission

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

Invariants

Because this is a doubly-linked list, the class invariants (statements which should always be true) are more extensive than for a singly-linked list:

Tests

The verify() function performs some basic checks on the structure of the list, to make sure that it is a correctly-formed doubly-linked list. verify() is called in many places, so you may see these tests pop up while testing other parts of the system.

Tests for “empty” lists

These tests apply when the verify() function thinks that your list is empty, typically because one or both of head, tail is nullptr.

Empty list (head == tail == nullptr) but list.size() != 0.

If a list has both its head and tail null, then it should be the empty list and should have a size of 0, but the size() method returned a non-zero value (the actual value returned will be printed with the test message). This most likely indicates a problem with your .size() method.

head is nullptr but tail is not

If one of head or tail is nullptr, then they both should be; there is no valid list where the head does not exist but the tail does. This is probably a problem with either insert or remove, as those are the only functions that could mutate the head and/or the tail.

tail is nullptr but head is not

If one of head or tail is nullptr, then they both should be; there is no valid list where the tail does not exist but the head does. Again, this is probably a problem in insert or remove.

Tests for single-element lists

These tests apply when verify thinks that your list has one element, typically because head == tail, with neither == nullptr.

head->next == nullptr, but head != tail

If head->next == nullptr, then head should be the last node in the list; i.e., the list has only one element, which should also be the tail of the list. But in this list, head != tail. This is probably a problem in insert or remove.

tail->prev == nullptr, but head != tail <

Similar to the previous, if tail->prev == nullptr then tail is the first node of the list, and hence there should only be one node, and it would be both the head and the tail. But somehow, head != tail. This is probably a problem in insert or remove.

head == tail (!= nullptr), but size() != 1

If head == tail and neither is nullptr, then the list should have a single element, but the size() method is not returning 1. This is probably a problem in size().

head == tail (!= nullptr), but node->next != nullptr

If head == tail and neither is nullptr, then the list should have a single element, and both its next and prev should be nullptr (because if it is the only element, then there is nothing before it, and nothing after it). But in this case, the single node’s ->next is non-null. This is probably a problem in insert or remove.

head == tail (!= nullptr), but node->prev != nullptr

If head == tail and neither is nullptr, then the list should have a single element, and both its next and prev should be nullptr (because if it is the only element, then there is nothing before it, and nothing after it). But in this case, the single node’s ->prev is non-null. This is probably a problem in insert or remove.

Tests on lists with ≥ 2 elements

These tests apply when verify thinks that your list has at least two elements, usually because head != tail and neither is nullptr.

head != tail, but list.size() ≤ 1

If head != tail (neither null), then the list should have at least two elements, but the value returned by size() is 1 or 0. This could be a problem with insert or remove, or with size.

head->prev != nullptr

If head is non-null, its ->prev should always be nullptr (there is nothing before the head). This is probably a problem with insert or remove not correctly updating head->prev when inserting before or removing the head.

tail->next != nullptr

If tail is non-null, its ->next should always be nullptr (there is nothing after the tail). This is probably a problem with insert or remove not updating tail->next when adding or removing the tail.

head != tail, but head->next == nullptr

If head != tail then the list should have at least two elements, but head->next == nullptr, as if there was nothing after the head. This is probably a problem with insert or remove.

head != tail, but tail->prev == nullptr

If head != tail then the list should have at least two elements, but tail->prev == nullptr, as if there was nothing before the tail. This is probably a problem with insert or remove.

Found a non-tail node with n->next == nullptr

Only the tail node should have its ->next == nullptr; this indicates that it is not possible to traverse the list in a forward direction (starting at the head and following the ->next pointers) and reach the tail. This is probably a problem with insert or remove.

Found a non-head node with n->prev == nullptr

Only the head node should have its ->prev == nullptr; this indicates that it is not possible to traverse the list in a reverse direction (starting at the tail and following the ->prev pointers) and reach the head. This is probably a problem with insert or remove.

n->prev->next does not point back to n

For any internal node (node which is not the head or the tail) n, n->prev->next should always point back to n itself. This is probably a problem with insert or remove.

n->next->prev does not point back to n

For any internal node (node which is not the head or the tail) n, n->next->prev should always point back to n itself. This is probably a problem with insert or remove.

Found a node x where next == prev

It should never be the case at any node that ->next points to the same node as ->prev (no node can be both before and after something). This is probably a problem with insert or remove.

Found a node x where n->prev == n

This indicates that there is a node whose ->prev pointer points back to the node itself; this should never happen in a well-formed list. This is probably a problem with insert or remove.

Found a node x where n->next == n

This indicates that there is a node whose ->next pointer points back to the node itself; this should never happen in a well-formed list. This is probably a problem with insert or remove.

Could not traverse the list from head to tail

The test code attempted to use a loop of the form

for(dlist::node* n = l.head(); n != l.tail(); n = n->next)

to traverse the list from head to tail, but it reached a point where n == nullptr before reaching the tail. This is probably a problem with insert or remove.

Could not traverse the list from tail to head

The test code attempted to use a loop of the form

for(dlist::node* n = l.tail(); n != l.head(); n = n->prev)

to traverse the list from tail to head, but it reached a point where n == nullptr before reaching the head. This is probably a problem with insert or remove.

List has a cycle

A cycle is a list where some node’s ->next points back to an earlier node in the list, or the node’s ->prev points forward to a later node in the list. If we try to loop over the nodes in this list, we will get stuck in an infinite loop, visiting the same nodes over and over. This is probably a problem with insert or remove.

The remaining tests apply to either specific kinds of lists, or specific operations.

Tests on the empty list

There is really only one possible test on the empty list.

empty list is not .empty()

When we first construct a list, it should contain no nodes, so .empty() should return true, but it is returning false.

Insertion tests

To test the insert() method, we test inserting a series of values at the head (since the head will be nullptr initially, this also tests insert(nullptr)), inserting a series of values at the tail, and finally inserting a series of values in the middle of a list. After each insert, the verify function is run, so any of the above verification tests may trigger at this stage.

size() != 1 after inserting one element into an empty list

If we insert a single element into an empty list, the size() of the resulting list should be 1, but it is not.

After inserting one element into an empty list, head() is nullptr

If we insert a single element into an empty list, then head() should return a non-nullptr value (i.e., a pointer to the newly-inserted node). Since the head() function is provided for you, this probably means that your insert() is failing to update the hd member.

After inserting one element into an empty list, tail() is nullptr

If we insert a single element into an empty list, then tail() should return a non-nullptr value (i.e., a pointer to the newly-inserted node). Since the head() function is provided for you, this probably means that your insert() is failing to update the tl member.

After inserting one element into an empty list, head() != at(0)

After inserting a single element into the empty list, at(0) should return a pointer to this new element, which should also be the head() of the list. This may indicate a problem with your insert(), or with your at() functions.

After inserting one element into an empty list, tail() != at(0)

After inserting a single element into the empty list, at(0) should return a pointer to this new element, which should also be the tail() of the list. This may indicate a problem with your insert(), or with your at() functions.

After inserting one element into an empty list, .at(0) is nullptr

After inserting a single element into the empty list, at(0) should return a pointer to this new element. This most likely indicates a problem with your at() function.

After inserting 100 into an empty list, l.at(0) ≠ 100

If we insert 100 into an empty list, then the value of the head (and tail) should be equal to 100. This could be a problem with insert, or with your at() method, since the test accesses the head as l.at(0). It might also indicate that you are not correctly setting the ->value of the node when you create it.

After inserting n elements, list.size() ≠n

(After insert(nullptr,x)) Starting from the empty list, we insert n elements. The resulting list should have size n, but it does not. This may indicate a problem with your size() function; if you added a sz data member, this may indicate that you forgot to increment it in insert().

After inserting x, the contents of the list are incorrect

If we insert the values 0, 1, …, 8, 9 into an empty list at nullptr (i.e., insert(nullptr,x), we should end up with a list containing

9, 8, 7, 6, 5, 4, 3, 2, 1, 0

(insert(nullptr,x) is equivalent to push_front(x), hence the reverse order.)

After inserting n elements, list.size() ≠n

(After insert(head(), x)) Starting from the empty list, we insert n elements. The resulting list should have size n, but it does not. This may indicate a problem with your size() function; if you added a sz data member, this may indicate that you forgot to increment it in insert().

After inserting x, the contents of the list are incorrect

If we insert the values 0, 1, …, 8, 9 into an empty list at the head(), we should end up with a list containing

0, 9, 8, 7, 6, 5, 4, 3, 2, 1

(The odd order is because the first insert will insert the 0, but subsequent inserts will add new values after the head.) However, the resulting list does not contain these element (the actual test message will include the contents of the list, for comparison).

After inserting n elements, list.size() ≠n

(After insert(tail(), x)) Starting from the empty list, we insert n elements. The resulting list should have size n, but it does not. This may indicate a problem with your size() function; if you added a sz data member, this may indicate that you forgot to increment it in insert().

After inserting x, the contents of the list are incorrect

If we start from an empty list and insert 0, 1, … 8, 9 at the tail, the resulting list should contain

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

but it does not. (The actual test message will include the contents of the list, for comparison.)

After inserting x, the contents of the list are incorrect

If we start from the list

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

and we insert 100, 101, …, 118, 119 between elements 5 and 6, then the resulting list should contain

0, 1, 2, 3, 4, 5, 100, 101, … 118, 119, 6, 7, 8, 9, 10

but it does not.

After inserting 31 elements, list.size() ≠ 31

The list 

0, 1, 2, 3, 4, 5, 100, 101, … 118, 119, 6, 7, 8, 9, 10

should have size 31, but size() returned some other value.

Tests of erase(node*)

These tests begin by constructing the list 0, 1, 2, ..., 28, 29.

After erasing x at head, list contents are incorrect

(In this step, we try to erase elements 0 through 9 of the list.)

We called erase(head()) and afterwards the contents of the list are not what they should be. This usually indicates a problem with your erase(node*) function, possibly the case where the head is erased.

After erasing x at tail, list contents are incorrect

(In this step, we try to erase elements 20 through 29 of the list.)

We called erase(tail()) and afterwards the contents of the list are not what they should be. This usually indicates a problem with your erase(node*) function, possibly the case where the tail is erased.

After erasing x in the middle, list contents are incorrect

(If the previous two tests were successful, we are left with the list 10, 11, …, 19.)

We called erase() on a node in the middle of the list (value = 15) and afterwards the contents of the list are not what they should be. This usually indicates a problem with your erase(node*) function.

After erasing all elements, list is not empty()

We constructed a list containing 10 elements, and then called erase(head()) 10 times. The resulting list should be empty, but it is not.

Tests of erase(index)

As above, we begin by constructing a list containing values 0, 1, 2, …, 29.

After erasing x at head, list contents are incorrect

We call erase(0) 10 times; after one of these times (given by x), the list contents were not correct.

After erasing x at tail, list contents are incorrect

We call erase(size()-1) 10 times; after one of these times, the list contents were not correct.

After erasing 15 in the middle, list contents are incorrect

If the previous two tests were successful, we should be left with a list containing 10, 11, 12, …, 19. We call erase(5), which should erase the node containing 15, but the resulting list is incorrect.

After erasing all elements, list is not empty()

We call erase(0) until the list should be empty, but when we’re done, the list is not empty.

After erasing at index i list contents are incorrect

We construct a new list containing 0, 1, 2, …, 29. Then we erase various negative indexes; the specification for erase(i) states that if i < 0 then the head should be erased. However, the list contents are not correct.

After erasing at index i list contents are incorrect

Again, we construct a new list and then erase(i) for various i ≥ size(). The specification for erase states that if i ≥ size() then the tail should be erased. However, the list contents are not correct.

Tests of remove(x)

After removing x at head, list contents are incorrect

If we start from the list 0, 1, 2, …, 28, 29 and remove 10 elements from the head, the resulting list should contain

10, 11, 12, … 28, 29

but it does not. (The test will print the actual contents of the list, for comparison.)

After removing x at tail, list contents are incorrect

If we start from the list 10, 11, …, 28, 29 and remove 10 elements from the tail, the resulting list should contain

10, 11, ..., 18, 19

but it does not.

After removing x in the middle, list contents are incorrect

If we start from the list 10, 11, …, 18, 19 and remove 15, the resulting list should contain

10, 11, 12, 13, 14, 16, 17, 18, 19

but it does not.

After removing all elements, list is not empty()

If we start with the list 10, 11, 12, 13, 14, 16, 17, 18, 19 and we remove the 9 remaining elements, the resulting list should be empty, but somehow it is not.

After removing x (which does not exist), list contents are incorrect

remove(x) for an x which does not exist in the list should not change the list contents, but it did.

After removing 2, list contents are incorrect

We construct a list containing

1, 2, 3, 2, 4

and then call remove(2). This should remove only the first instance of 2, leaving the list as 1, 3, 2, 4 but the list contents are incorrect.

push_back, push_front tests

Last push_back’d value = x, but tail ≠x

The tail’s value should always equal the most-recently push_back‘d value, but it does not.

After push_back'ing n values, size ≠n

If we start from an empty list and push_back n values, the size of the resulting list should be n, but it is not.

After push_back'ing 0, 1, 2, …, 18, 19, list does not contain correct elements

If we start with the empty list and push_back the values 0, 1, …, 18, 19, the resulting list should contain

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19

but it does not. The actual test message will include a print-out of the list, for comparison.

After push_front'ing x, head->value ≠x

After every push_front(x), the value of the head should be equal to x, but it is not.

After push_front'ing n values, size() ≠n

If we start from an empty list and push_front n values, the resulting list should have size n, but it does not.

After push_front'ing 0, 1, 2, …, 18, 19, list does not contain correct elements

If we start from the empty list and push_front the values 0, 1, 2, …, 18, 19, the resulting list should contain

19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0

but it does not. The actual test message will include a print-out of the list contents for comparison.

pop_front, pop_back tests

List should have n elements, but size() ≠n

If we start from the list 

0,1,2,3,4,5,6,7,8,9

and we pop_front n elements, then the resulting list should have size 10 - n, but it does not.

After pop_front'ing all elements, the list is not empty().

If we pop_front() all 10 elements from a list of size 10, the resulting list should be empty() but it is not.

List should have n elements, but size() ≠n

If we start with a list of 10 elements and perform n pop_back()s, the resulting list should have 10 - n elements, but it does not.

Tests for the to_vector function

After running to_vector() on the empty list, the resulting vector is not empty

We create an empty list and then call to_vector(); the resulting vector should be empty, but it is not.

to_vector()` did not return 0, 1, 2, … 9

We construct a list containing 0, 1, 2, …, 9 and then call to_vector() on it; the resulting vector contains the wrong values.

Tests for copy-construction

Note: “Testing” for memory leaks/corruption is done by the test-assignment script, which will run the test-runner inside valgrind.

After copy-constructing a copy of 0, 1, 2, …, 9, copy has the wrong values

We construct a list a containing 0, 1, 2, …, 9, and then we copy-construct b:

dlist b = a;

b should contain the same values as a, but it does not.

After copy-constructing a copy of 0, 1, 2, …, 9, copy shares node* with the original

As above, we construct b as a copy of 0, 1, 2, …, 9. The copy should have its own nodes, not sharing any with the original, but at least one node* occurs in both the copy and the original. (This will probably also result in a crash with a double-free error.)

After copy-construction, size of copy is m but size of the original is n (m != n)

As above, we copy-construct a copy of 0, 1, 2, …, 9. size() on the copy should return 10 (same as the size of the original) but it did not.

Tests for copy-assignment

We begin by constructing a list a containing 0, 1, 2, …, 9, and a list b containing 10, 11, 12, …, 19.

After a = b, a is different from b

After performing the copy-assignment statement a = b;, a should contain the same elements as b, but it does not.

After a = b, a and b share some node pointers.

No node* should be shared between a and b after the copy-assignment, but at least one node* occurs in both lists. (This will probably also result in a crash with a double-free error.)

After a = b, a and b have different sizes

After copy-assignment a.size() should be equal to b.size() but they are different. (Note that in this case, a and b had the same size before the copy.)

After a = b, a should contain 10, 11, 12, …, 19 but does not

After a = b;, a should contain 10, 11, 12, .., 19, but its elements are incorrect (the test will print the contents of a for comparison).

The next four tests are performed with a = 0, 1, 2, .., 9, b = 0, 1, ..., 19, i.e., a.size() == 10 but b.size() == 20.

After a = b, a is different from b

After performing the copy-assignment statement a = b;, a should contain the same elements as b, but it does not.

After a = b, a and b share some node pointers.

No node* should be shared between a and b after the copy-assignment, but at least one node* occurs in both lists. (This will probably also result in a crash with a double-free error.)

After a = b, a and b have different sizes

After copy-assignment a.size() should be equal to b.size() but they are different. (Note that in this case, a and b had the same size before the copy.)

After a = b, a should contain 0, 1, 2, …, 19 but does not

After a = b;, a should contain 0, 1, 2, .., 19, but its elements are incorrect (the test will print the contents of a for comparison).

After self-assignment (a = a), size is incorrect; expected size 10

We construct a list a = 0, 1, 2, ..., 9 and then perform

a = a;

This should leave a unchanged, but the size has changed from the original.

After self-assignment (a = a), a is empty

Again, we construct a = 0, 1, 2, ..., 9 and then perform a = a;. This should leave a unchanged, but afterwards a is empty.

Tests for big-O complexity (O(1))

These tests attempt to check insert, push_back and push_front to see if they run in O(1) time. This is somewhat imprecise, so failures in this area are reported as warnings. If you get a warning that an operation does not run in O(1) time, try re-running the tests; only consistent failures should warrant more investigation.

Only three operations are tested for O(1)-ness: insert, push_front and push_back. We only test these three because they all increase the size of the list, so we can simply run them in a loop and see if they get slower as the size of the list increases.

insert() does not appear to run in O(1) time

insert() was called repeatedly, measuring the time taken for each call. As the size of the list increases, the runtime of insert should not change, but it appears to getting slower (increasing linearly with the size of the list).

push_back() does not appear to run in O(1) time

push_back() was called repeatedly, measuring the time taken for each call. As the size of the list increases, the runtime of insert should not change, but it appears to getting slower (increasing linearly with the size of the list).

push_front() does not appear to run in O(1) time

push_front() was called repeatedly, measuring the time taken for each call. As the size of the list increases, the runtime of insert should not change, but it appears to getting slower (increasing linearly with the size of the list).

Total tests: 83 (some tests are performed more than once)