Requirements

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

1. Singly linked lists: Single_list, and
2. Singly linked nodes: Single_node.

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

Figure 1. A singly linked list three nodes.

Figure 2. An empty singly linked list.

Class Specification

UML Class Diagram

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

Description

This class stores a finite list of n (zero or more) elements stored in singly 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 Single_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, and the next pointer of the nth is assigned 0.

Member Variables

The three member variables are:

• Two pointers to Single_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

Single_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 creates a new instance of the linked list. (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))

Single_node<Type> *head() const;

Returns the head pointer. (O(1))

Single_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 six mutators:

void swap( Single_list & );

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

Single_list &operator=( Single_list & );

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

void push_front( Type const & );

Creates a new Single_node<Type> storing the argument, the next pointer of which is set to the current head pointer. The head pointer is set to this 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. Return the object stored in the node being popped. Throw an underflow exception 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 next pointer of any other node within the list. Return the number of nodes that were deleted. (O(n))

Testing

Our default test scripts (int.in.txt and double.in.txt) cover some of your 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 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--all should be successful
push_front 3
push_front 2
push_front 1
// erase the middle node
erase 2 1
// check that everything is still okay
front 1
back 3
size 2
empty 0
// walk through the linked list
head
   value 1
   next
   value 3
   next0
exit
delete
summary
exit