Requirements

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

1. a doubly linked list class with sentinels: Double_sentinel_list, and
2. a nested doubly linked node class: Double_node.

A doubly linked list bound by two sentinels and containing three nodes is shown in Figure 1. The empty doubly linked list bounded by two sentinels is shown in Figure 2, the nodes marked S being the sentinel nodes.

Figure 1. A doubly linked list with three nodes bounded by two sentinels.

Figure 2. An empty doubly linked list with two sentinels.

Class Specifications

UML Class Diagram

Double_sentinel_list
- list_head:Double_node - list_tail:Double_node - list_size:Integer
+ create():Double_sentinel_list + create( in dsl:Double_sentinel_list ):Double_sentinel_list + size():Integer + empty():Boolean + front():Type + back():Type + begin():Double_node + end():Double_node + rbegin():Double_node + rend():Double_node + find( in obj:Type ):Double_node + count( in obj:Type ):Integer + swap( inout list:Double_sentinel_list ) + =( in rhs:Double_sentinel_list ):Double_sentinel_list + push_front( in obj:Type ) + push_back( in obj:Type ) + pop_front() + pop_back():Type + erase( in obj:Type ):Integer + destroy()

A skeleton for this class is provided in the source directory linked to in the left-hand menu.

Description

This class stores a finite list of n (zero or more) elements stored in doubly linked nodes. The following are properties of this class:

• 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 store the addresses of the head and tail sentinel nodes, respectively.
• The previous pointer of the head sentinel always points to nullptr.
• The next pointer of the tail sentinel always points to nullptr.
• If the list is empty, the next pointer of the head sentinel node is assigned the address of the tail sentinel; otherwise, the next pointer of the head sentinel node is assigned the address of the first node in the linked list (the front node).
• If the list is empty, the previous pointer of the tail sentinel node is assigned the address of the head sentinel; otherwise, the previous pointer of the tail sentinel node is assigned the address of the last node in the linked list (the back node).
• The next pointer of the kth node (1 ≤ k < n) stores the address of the (k + 1)st node, the next pointer of the nth is assigned to the address of the tail sentinel.
• The previous pointer of the kth node (1 < k ≤ n) stores the address of the (k − 1)st node, and the previous pointer of the first node is assigned the address of the head 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

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

~Double_sentinel_list()

The destructor must delete each of the nodes in the list including the sentinels. (O(n))

Copy Constructor

Double_sentinel_list( Double_sentinel_list const &list )

The copy constructor must create a new doubly linked list with a copy of all of the nodes within the linked list pass as the argument list with the values stored in the same order. The linked list passed as an argument may not be changed. Once a copy is made, any change to the original linked list must not affect the copy. (O(n))

Move Constructor

Double_sentinel_list( Double_sentinel_list &&list )

The move constructor must create a new doubly linked list with all the nodes found within the linked list passed as an argument list with the values stored in the same order. It is assumed that the destructor will immediately be called on the argument linked list as soon as this constructor finishes, so all the nodes in the argument linked list can be used in this newly created linked list. The argument linked list should be updated to one that is empty. (This is most easily done by initializing this linked list as an empty linked list and then calling swap.)

(O(1))

Accessors

This class has these 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_sentinel_list<Type>::Double_node *begin() const;

Returns the address stored by the next pointer of the head sentinel node. (O(1))

Double_sentinel_list<Type>::Double_node *end() const;

Returns the address of the tail sentinel node. (O(1))

Double_sentinel_list<Type>::Double_node *rbegin() const;

Returns the address stored by the previous pointer of the tail sentinel node. (O(1))

Double_sentinel_list<Type>::Double_node *rend() const;

Returns the address of the head sentinel node. (O(1))

Double_sentinel_list<Type>::Double_node find( Type const & ) const;

Returns the address of the first node in the linked list storing a value equal to the argument; if none is found, return end(). (O(n))

int count( Type const & ) const;

Returns the number of nodes in the linked list storing a value equal to the argument. (O(n))

The member functions begin() and end() allows a user to iterate through the entries of a linked list as follows:

	List<int> my_list;
	list.push_front( 0 );
	// Insert and possibly remove other entries into the list

	// Iterate through the linked list from the first entry to the last
	//  - the type 'auto' lets the compiler determine the type for you!
        for ( auto *ptr = list.begin(); ptr != list.end(); ptr = ptr->next() ) {
                std::cout << ptr->value() << ' ';
        }

The member functions rbegin() and rend() allows a user to iterate through the entries of a linked list in reverse order as follows:

	// Iterate through the linked list in reverse order
	// from the last entry back down to teh first entry
	//  - the type 'auto' lets the compiler determine the type for you!
        for ( auto *ptr = list.rbegin(); ptr != list.rend(); ptr = ptr->previous() ) {
                std::cout << ptr->value() << ' ';
        }

If you did not use auto (short for automatic type declarations), you would have to explicitly state that the type is typename Double_sentinel_list<int>::Double_node. In this case, because the compiler knows the return type of the begin() member function, it can use the signature of that member function to deduce the appropriate type for ptr.

Mutators

This class has these mutators:

void swap( Double_sentinel_list &list );

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

Double_sentinel_list &operator=( Double_sentinel_list const &rhs );

The assignment operator makes a copy of the argument (the right-hand side of the assignment) and then swaps the member variables of this node doubly linked sentinel list those of the copy. (O(n_lhs + n_rhs))

Double_sentinel_list &operator=( Double_sentinel_list &&rhs );

The move operator moves the nodes in the argument (the right-hand side of the assignment) linked list to this linked list, changing the argument linked list into an empty list. (O(1))

void push_front( Type const &new_value );

Creates a new Double_node<Type> storing the argument new_value, the next pointer of which is set to the next pointer of the sentinel and the previous pointer is set to point to the sentinel. The next pointer of the sentinel and the previous pointer of what was the first node are set to this new node. (O(1))

void push_back( Type const &new_value );

Similar to push_front, this places a new node at the back of the list storing the argument new_value. (O(1))

void pop_front();

Delete the first non-sentinel node at the front of the linked list and update the previous and next pointers of any other node (including possibly the sentinels) within the list as necessary. Throw an underflow exception if the list is empty. (O(1))

void 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 &value );

Delete all the nodes in the linked list that have a value equal to the argument value (use == to to test for equality with the retrieved element). Update 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))

Compilation

In Linux, you will have to use g++ -std=c++11 Double_sentinel_list_driver.cpp.