Requirements

In this sub-project, you will implement two classes:

1. Doubly linked lists: Double_list, and
2. Doubly linked nodes: Double_node.

A doubly linked list with three nodes is shown in Figure 1. The empty doubly linked list is shown in Figure 2.

Figure 1. A doubly linked list with a header and three nodes.

Figure 2. An empty doubly linked list.

Class Specifications

UML Class Diagram

Double_list
- list_head:Double_node - list_tail:Double_node - list_size:Integer
+ create():Double_list + create( in dl:Double_list ):Double_list + size():Integer + empty():Boolean + front():Type + back():Type + head():Double_node + tail():Double_node + count( in obj:Type ):Integer + swap( inout list:Double_list ) + =( in rhs:Double_list ):Double_list + push_front( in obj:Type ) + push_back( in obj:Type ) + pop_front():Type + pop_back():Type + erase( in obj:Type ):Integer + destroy()

Description

This class stores a finite list of n (zero or more) elements stored in doubly linked nodes. If there are zero elements in the list, the list is said to be empty. Each element is stored in an instance of the Double_node<Type> class. If the list is empty, the head and tail pointers are assigned nullptr. Otherwise, the head pointer points to the first node, the tail pointer points to the nth node, the next pointer of the ith node (1 ≤ i < n) points to the (i + 1)st node, the next pointer of the nth is assigned nullptr, the previous pointer of the ith node (2 ≤ i ≤ n) points to the (i − 1)st node, and the previous pointer of the first node is assigned nullptr.

Member Variables

The three member variables are:

• Two pointers to Double_node<Type> objects, referred to as the head pointer and tail pointer, respectively, and
• An integer referred to as the list size which equals the number of elements in the list.

Member Functions

Constructors

Double_list()

This constructor sets all member variables to 0 or nullptr, as appropriate. (O(1))

Destructor

The destructor must delete each of the nodes in the linked list. (O(n))

Copy Constructor

The copy constructor must create a new doubly linked list with a copy of all of the nodes within the linked list with the elements stored in the same order. Once a copy is made, any change to the original linked list must not affect the copy. (O(n))

Accessors

This class has seven accessors:

int size() const;

Returns the number of items in the list. (O(1))

bool empty() const;

Returns true if the list is empty, false otherwise. (O(1))

Type front() const;

Retrieves the object stored in the node pointed to by the head pointer. This function throws a underflow if the list is empty. (O(1))

Type back() const;

Retrieves the object stored in the node pointed to by the tail pointer. This function throws a underflow if the list is empty. (O(1))

Double_node<Type> *head() const;

Returns the head pointer. (O(1))

Double_node<Type> *tail() const;

Returns the tail pointer. (O(1))

int count( Type const & ) const;

Returns the number of nodes in the linked list storing a value equal to the argument. (O(n))

Mutators

This class has seven mutators:

void swap( Double_list & );

The swap function swaps all the member variables of this linked list with those of the argument. (O(1))

Double_list &operator=( Double_list & );

The assignment operator makes a copy of the argument and then swaps the member variables of this doubly linked list with those of the copy. (O(n_lhs + n_rhs))

void push_front( Type const & );

Creates a new Double_node<Type> storing the argument, the next pointer of which is set to the current head pointer and the previous pointer is set to nullptr. The head pointer and the previous pointer of what was the first node is set to the new node. If the list was originally empty, the tail pointer is set to point to the new node. (O(1))

void push_back( Type const & );

Similar to push_front, this places a new node at the back of the list. (O(1))

Type pop_front();

Delete the node at the front of the linked list and, as necessary, update the head and tail pointers and the previous pointer of any other node within the list. Return the object stored in the node being popped. Throw an underflow exception if the list is empty. (O(1))

Type pop_back();

Similar to pop_front, delete the last node in the list. This function throws a underflow if the list is empty. (O(1))

int erase( Type const & );

Delete the first node (from the front) in the linked list that contains the object equal to the argument (use == to to test for equality with the retrieved element). As necessary, update the head and tail pointers and the previous and next pointers of any other node within the list. Return the number of nodes that were deleted (0 or 1). (O(n))

Coding strategy

You will note that the template compiles. It does nothing correctly, but it does compile.

• First, implement the member functions of the Double_ndoe class. Make sure that it continues to compile.
• Next, implement the simple member functions such as size, empty, head, tail, front, and back. Again, make sure that it compiles.
• Next, start with push_front. Make sure it compiles.

Now you have the opporunity to run a simple test:

new
// Empty should return true, size should return 0, both
// front and back should throw exceptions, and both
// head and tail should return nullptr.
empty 1
size 0
front!
back!
head0
tail0
// Push one object onto the linked list
push_front 42
// Empty should return false, size should return 1, both
// front and back should return 42
empty 0
size 1
front 42
back 42
// Calling head now will retrieve the head and allow us to
// execute functions on the node pointed to by head
//  - when we call retrieve on that node, it should return 42
//  - when we call next, it should return nullptr
// We call exit to return to testing the linked list class
head
    retrieve 42
    next0
exit
// Calling tail now will retrieve the tail and allow us to
// execute functions on the node pointed to by tail
//  - when we call retrieve on that node, it should return 42
//  - when we call previous, it should return nullptr
// We call exit to return to testing the linked list class
tail
    retrieve 42
    previous0
exit
delete
summary
exit

You don't have to write and save such tests, but it might be easier.

Testing cases

Our default test scripts (int.in.txt and double.in.txt) cover some of the required functionality, but you may ask yourself whether or not your code works in all possible cases. For this, you should realize that:

• The const member functions, or accessors, are not going to change the internal structure of the linked list;
• Issues will arise when calling mutators, those functions that manipulate the structure of the linked list.

Consequently, you are interested in testing all possible cases where a mutator changes the state of the linked list and you want to ensure that the list structure remains consistent. As the contents of the nodes really doesn't affect your linked list, the only thing you have to consider is the number of nodes in the list. We will call the number of nodes in the linked list the state.

In testing, our interest is in looking at the transitions between the states: for example:

• Going from a linked list with one object to one with two, or
• Going from a linked list with three objects to one with two.

What operations do the first? push_front and push_back. What operations do the second? pop_front, pop_back, and calling erase on one item in the linked list.

How large of a linked list do we have to test? If all our algorithms are tested on a linked list of size 1000, does that guarantee that it will work on a list of size 1001? Most likely, however, we don't need even that much: if all our algorithms work on a list of size three, this should guarantee that the algorithms work on all lists with more than three nodes. Thus, we only have to consider the states where the size is 0, 1, 2, and 3, and then we have to consider all transitions between these states. If you take a look at Figure 3, you will see such a state transition diagram. Those of you in computer engineering will see such diagrams in ECE 254 Operating Systems. Each transition is marked with the operations that may take you from one state to the next. For the case of erase, one could remove any of the nodes in the list, so there are multiple possible cases one would have to consider in the transitions.

Figure 3. A state transition diagram.

For example, you may wish to test erase when there are three elements in the list. This could be done as follows:

// Create a new linked list
new
// Insert three elements by calling push_front three times
push_front 43
push_front 42
push_front 41
// Right now, the list should contain    0<-(41)<=>(42)<=>(43)->0
//                                      head-^           ^-tail
// Erase the middle node--the erase should be successful
erase 42 1
// Right now, the list should contain head->(41)->(43)->0
// Check that everything is still okay
front 41
back 43
size 2
empty 0
// Walk through the linked list from the front
// 'head' starts a tester on the node at the front of the linked list.
// You can now call the member functions on the node, including retrieve(), next() and previous()
// Once you're finished walking though the linked list, call 'exit'
head
   retrieve 41
   next
   retrieve 43
   next0
exit
// Walk through the linked list from the back
// Details are similar to that of the previous section
tail
   retrieve 43
   previous
   retrieve 41
   previous0
exit
delete
summary
exit

You could create similar tests to ensure that all of your member functions perform correctly as you transition from one state to another.