CSCI373 Sentinel Singly Linked List

Problem Description

The Linked List ADT extends the notion of array by storing a sequence of objects. It uses an array to store the elements of linear list.

You will implement the singly linked list with the sentinel nodes.

A singly linked list with a sentinel and three nodes, the node marked S being the sentinel node. see image.

The empty singly linked list with a sentinel, the node marked S being the sentinel node. see image.

Runtime:

The run time of each member function is specified in parentheses at the end of the description.

Class Specifications

SinglyLinkedNode

UML Class Diagram

Description

A class which stores an object and a pointer to the next node in a linked list.

Member Variables

The two member variables are:

• An Type, referred to as the element of the node, and
• A pointer to a SinglyLinkedNode object, referred to as the next node pointer.

Member Functions

Constructors

SinglyLinkedNode( const Type &, SinglyLinkedNode * )

This constructor takes two arguments: a constant reference to an Type (by default, a new instance of the type Type) and a pointer to a SinglyLinkedNode (by default nullptr). These are assigned to the member variables, respectively. (O(1))

Destructor

This class uses the default destructor.

Copy Constructor

This class uses the default copy constructor.

Accessors

This class has two accessors, one to get each of the two associated member variables:

Type value() const

• Returns the element of the node. (O(1))

SinglyLinkedNode* next() const

• Returns the next pointer. (O(1))

Mutators

This class has no member functions which modify the member variables.

Friends

The class SentinelList< Type> is a friend of this class.

SentinelList

UML Class Diagram

A skeleton for this class is provided in the source directory in the file SentinelList.h.

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 SinglyLinkedNode< Type> class, see SinglyLinkedNode. At all times, the head pointer points to a sentinel node. If the list is empty, the tail pointer points to the sentinel node.

Member Variables

The three member variables are:

• Two pointers to SinglyLinkedNode< 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

SentinelList()

• The constructor creates an instance of a SinglyLinkedNode< Type> (called the sentinel). The value stored in this node is not important, you can use the default value or whatever value you want. The next pointer of the sentinel should be nullptr. The head and tail pointers are set to point at the sentinel. The node count is set to 0. (O(1))

Destructor

~SentinelList()

• The destructor must delete each of the nodes in the linked list. (O(n))

Copy Constructor

SentinelList(const SentinelList &)

• The copy constructor must create a new singly 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 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 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 tail pointer. This function throws a underflow if the list is empty. (O(1))

SinglyLinkedNode< Type>* begin() const

• Returns the head pointer. (O(1))

SinglyLinkedNode< Type>* end() const

• Returns the tail pointer. (O(1))

int count( const Type & ) const

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

Mutators

This class has five mutators:

void swap( SentinelList & )

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

void push_front( const Type & )

• Creates a new SinglyLinkedNode< Type> object, storing the argument, the next pointer of which is set to the next pointer of the sentinel. The next pointer of the sentinel is set to the new node. If the list was originally empty, the tail pointer is set to point to the new node. (O(1))

void push_back( Type const & )

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

Type pop_front();

• Delete the node at the front of the linked list and, as necessary, update the tail pointer and the next pointer of the sentinel. Return the object stored in the node being popped. Throw an underflow exception if the list is empty. (O(1))

int erase( const Type & )

• Delete all nodes (other than the sentinels) 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 next pointer of any other node (including possibly the sentinel) within the list. Return the number of nodes that were deleted. (O(n))

Tasks

• Implement SentinelList class