Template Class SinglyLinkedList

• Defined in File singly_linked_list.h

Nested Relationships

Nested Types

• Struct SinglyLinkedList::Node

Class Documentation

template<typename T>
class SinglyLinkedList

Singly linked list class with all related functionality.

Template Parameters:

T – Type of the implementation class.

Public Functions

inline SinglyLinkedList()

Constructor for the SinglyLinkedList class.

Initializes the head node and points the tail to the head. Size is initialized to zero.

inline ~SinglyLinkedList()

Destructor for the SinglyLinkedList class.

Clears the singly linked list and deletes the head and tail pointers.

inline void add_first(const T &data)

Adds a new node at the start of the list.

This is achieved by linking the new node to the node pointed by head and updating head to point to the new node. If the list was empty earlier then the tail is updated. The size is incremented by unity.

Parameters:

data – The data of the node to be added.

inline void add_last(const T &data)

Adds a new node at the end of the list.

This is achieved by linking the node pointed by the tail to the new node and then updating the tail to point to the new node. The size is incremented by unity.

Parameters:

data – The data of the node to be added.

inline void add(int pos_index, const T &data)

Adds a new node at a valid position index.

This is achieved by first checking the position index to make sure its valid using the private check_position_index() function. If its the last valid position then we directly use the add_last() function, otherwise we link the node before the position we want to add at to the new node and then link the new node to the node after it. The size is incremented by unity.

Parameters:

• pos_index – Position index at which the new node is to be added.

• data – Data of the node to be added.

inline T del_first()

Deletes the first node in the list.

This is achieved by first using the utility is_empty() function to check that the singly linked list is not empty and then linking the head to the node after the first node and updating the tail if the list contains only a single node after the operation. The size is updated, the node’s memory freed and its old value returned.

Throws:

std::out_of_range – if the list is empty. The exception message states that there are “No nodes to remove”.

Returns:

The data of the first node that will be deleted.

inline T del_last()

Deletes the last node in the list.

This is achieved by first using the utility is_empty() function to check that the singly linked list is not empty and then getting the data of the last node, freeing its memory and linking the node before it nullptr. The size and tail pointer are updated and the old data returned.

Throws:

std::out_of_range – if the list is empty. The exception message states that there are “No nodes to remove”.

Returns:

The data of the ending node that will be deleted.

inline T del(int index)

Delete a node at a particular index.

This is achieved by using the private check_element_index() function to first check if the index is valid and then linking the node before the node to be deleted to the node after the node to be deleted. If the index happens to be the last index of the list then the tail pointer is updated. Lastly, the size is decremented by unity, the node’s memory freed and its old data returned.

Returns:

The data of the node that will be deleted.

inline T get_first() const

Get the data stored in the first node.

Uses the utility is_empty() function to check if the first element exists and if it does, returns the data in the first node.

Throws:

std::out_of_range – when the list is empty. The exception message states that there are “No nodes in the list”.

Returns:

The data in the first node.

inline T get_last() const

Get the data stored in the last node.

Uses the utility is_empty() function to check if the last element exists and if it does, returns the data in the last node.

Throws:

std::out_of_range – when the list is empty. The exception message states that there are “No nodes in the list”.

Returns:

The data in the last node.

inline T get(int index) const

Get the data stored in a node at a particular index.

Uses the private get_node() function to check if the index is valid and returns the requested node’s data.

Parameters:

index – Index of the element.

Returns:

The data of the requested node.

inline T set(int index, const T &data)

Set the data in a node at a particular index.

Uses the private get_node() function to check if the index given is valid, sets its data and returns the old data.

Parameters:

• index – Index of the node to be set.

• data – Value to be set to.

inline size_t get_size() const

Get the current size of the singly linked list.

Returns:

Current size of the singly linked list.

inline bool is_empty() const

Check if the singly linked list is empty.

Returns:

true if the list contains no elements, false otherwise.

inline void display() const

Display the values in the nodes of the singly linked list.