Requirements

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

1. Sorted doubly linked lists with a sentinel: Sorted_double_sentinel_list, and
2. Doubly linked nodes: Double_node.

A doubly linked list with a sentinel and three nodes is shown in Figure 1. The empty doubly linked list with a sentinel is shown in Figure 2, the node marked S being the sentinel node.

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

Figure 2. An empty doubly linked list with a sentinel.

Class Specifications

UML Class Diagram

Sorted_double_sentinel_list
- list_head:Double_node - list_tail:Double_node - list_size:Integer
+ create():Sorted_double_sentinel_list + create( in dsl:Sorted_double_sentinel_list ):Sorted_double_sentinel_list + size():Integer + empty():Boolean + front():Type + back():Type + head():Double_node + tail():Double_node + count( in obj:Type ):Integer + swap( inout list:Sorted_double_sentinel_list ) + =( in rhs:Sorted_double_sentinel_list ):Sorted_double_sentinel_list + insert( 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) linearly ordered elements in that order 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. At all times, the head and tail pointers point to head and tail sentinel nodes, respectively. If the list is empty, the tail pointer points to the tail sentinel node and the next pointer the tail sentinel is assigned nullptr while the previous pointer of the tail sentinel is assigned the address of the head sentinel. Otherwise, the next pointer of the head sentinel 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 is assigned to the address of the tail sentinel, 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 points to the sentinel.

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

Sorted_double_sentinel_list()

The constructor creates two instances of a Double_node<Type> (called the sentinels). The head and tail pointers are set to point to one of the sentinels, each. The values stored in these nodes is not important, you can use the default value or whatever values you want. The previous and next pointers of the head sentinel should be nullptr and the address of the tail sentinel, respectively. The previous and next pointers of the tail sentinel should be address of the head sentinel and nullptr, respectively. The node count is set to 0. (O(1))

Destructor

The destructor must delete each of the nodes in the list including the sentinels. (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) 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 next pointer of the head sentinel. 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 previous pointer of the tail sentinel. 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( Sorted_double_sentinel_list & );

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

Sorted_double_sentinel_list &operator=( Sorted_double_sentinel_list & );

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

void insert( Type const & );

Creates a new Double_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. (O(n))

Type pop_front();

Delete the first non-sentinel node at the front of the linked list and, as necessary, update the tail pointer and the previous and next pointers of any other node (including the sentinel) 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 non-sentinel 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 and other than the sentinals) 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 tail pointer and the previous and next pointers of any other node (including possibly the sentinels) within the list. Return the number of nodes that were deleted. (O(n))