Requirements

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

Single linked lists: SingleList, and
Singly-linked nodes: SingleNode.

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

SingleList
`-` list_head:SingleNode `-` list_tail:SingleNode `-` count:Integer
`+` create():SingleList `+` create( in sl:SingleList ):SingleList `+` =( in rhs:SingleList ):SingleList `+` size():Integer `+` empty():Boolean `+` front():Type `+` back():Type `+` head():SingleNode `+` tail():SingleNode `+` member( in obj:Type ):Boolean `+` push_front( in obj:Type ) `+` push_back( in obj:Type ) `+` pop_front():Type `+` remove( in obj:Type ):Boolean `+` 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 SingleNode<Object> class. If the list is empty, the head and tail pointers are assigned 0. 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 class members are:

Two pointers to SingleNode<Object> objects, referred to as the head pointer and tail pointer, respectively, and
An integer referred to as the count which equals the number of elements in the list.

Member Functions

Constructors

SingleList()

This constructor sets all class members to 0. (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))

Assignment Operator `=`

The assignment operator, if necessary, must delete all the nodes within the linked list being assigned to and add copies of the nodes in the linked list being assigned in the same order. (O(max{n_lhs, n_rhs}))

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))
Object 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))
Object 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))
SingleNode<Object> *head() const;: Returns the head pointer. (O(1))
SingleNode<Object> *tail() const;: Returns the tail pointer. (O(1))
bool member( Object const & ) const;: Returns true if the argument is stored by one of the nodes in the linked list and false otherwise. (O(n))

Mutators

This class has four mutators:

void push_front( Object const & );: Creates a new SingleNode<Object> 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( Object const & );: Similar to push_front, this places a new node at the back of the list. (O(1))
Object 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))
bool remove( Object const & );: Delete the first node in the linked list which 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 true if a node was deleted and false otherwise. (O(n))

Singly-Linked List