Requirements

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

1. Sorted singly linked lists: Sorted_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

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

Description

This class stores a finite list of n (zero or more) linearly ordered elements in that order 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 nullptr.

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

Sorted_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) and note that using insert will result in an O(n²) run-time)

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( Sorted_single_list & );

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

Sorted_single_list &operator=( Sorted_single_list & );

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

void insert( Type const & );

Creates a new Single_node<Type> storing the argument, placing it into the correct location in the linked list such that the element in the previous node (if any) is less than or equal to the element stored in the current node, and that element is less than or equal to the element stroed in the next node. The head and tail pointers may have be updated if the new node is placed at the head or tail of the linked list. (O(n))

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))