Requirements

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

1. Cyclic doubly linked lists: Cyclic_double_list, and
2. Doubly linked nodes: Double_node.

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

Figure 1. A cyclic doubly linked list and three nodes.

Figure 2. An empty cyclic doubly linked list.

Class Specification

UML Class Diagram

Cyclic_double_list
- list_head:Double_node - list_size:Integer
+ create():Cyclic_double_list + create( in cdl:Cyclic_double_list ):Cyclic_double_list + size():Integer + empty():Boolean + front():Type + back():Type + head():Double_node + count( in obj:Type ):Integer + swap( inout list:Cyclic_double_list ) + =( in rhs:Cyclic_double_list ):Cyclic_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 pointer points to nullptr. Otherwise, the head pointer points to the first node, the next pointer of the ith node (1 ≤ i < n) points to the (i + 1)st node, the next pointer of the nth node points to the first node, the previous pointer of the ith node (2 ≤ i ≤ n) points to the (i − 1)st node, the previous pointer of the first node points to the nth node.

Member Variables

The two member variables are:

• A pointer to a Double_node<Type> referred to as the head pointer, and
• An integer referred to as the list size which equals the number of elements in the list.

Member Functions

Constructors

Cyclic_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 cyclic 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 six 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 last node in the list (the node previous to the head). This function throws a underflow if the list is empty. (O(1))

Double_node<Type> *head() const;

Returns the head 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( Cyclic_double_list & );

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

Cyclic_double_list &operator=( Cyclic_double_list & );

The assignment operator makes a copy of the argument and then swaps the member variables of this cyclic 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 of which is set to the node previous to the current head pointer. The previous pointer of what was the first node as well as the next pointer of the last node in the list are also set to the new node. The head pointer is set to this new node. If the list was originally empty, both the next and previous pointers of the new node are set to itself. (O(1))

void push_back( Type const & );

Similar to push_front, this places a new node at the back of the list (it does the same as push_front but does not update the head pointer). (O(1))

Type pop_front();

Delete the node at the front of the linked list and, as necessary, update the head pointer and the previous and next pointers 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 pointer and the previous and next pointers of any other node within the list. Return the number of nodes that were deleted. (O(n))