Template Class DoublyLinkedList

• Defined in File doubly_linked_list.h

Nested Relationships

Nested Types

• Struct DoublyLinkedList::Node

Class Documentation

template<typename T>
class DoublyLinkedList

Doubly linked list class with all related functionality.

Template Parameters:

T – Type of the implementation class.

Public Functions

inline DoublyLinkedList()

Constructor for the DoublyLinkedList class.

Initializes the head and tail pointers by linking them to each other.

inline ~DoublyLinkedList()

Destructor for the DoublyLinkedList class.

Clears the doubly 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 doubly linked list.

This is achieved by first linking the new node before the currently first node and then consequently linking the head to this new start node. The size of the doubly linked list is incremented by unity.

Parameters:

data – The data of the node.

inline void add_last(const T &data)

Adds a new node at the end of a doubly linked list.

This is achieved by first linking the new node after the currently last node and then consequently linking the tail to this new end node. The size of the doubly linked list is incremented by unity.

Parameters:

data – The data of the node.

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. If its the last valid position then we directly use the add_last() function, otherwise we link the node before the node at the desired position to the our new node and then link the new node to the original node that was at its position.

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()

Delete the first node in the list.

This is achieved by first checking that the doubly linked list is not empty and then linking the head to the next node after the first node. Memory of the node is freed, the size is updated and its data returned.

Returns:

The data of the first node that will be deleted.

inline T del_last()

Delete the last node in the list.

This is achieved by first checking that the doubly linked list is not empty and then linking the second last node to the tail. Memory of the node is freed, the size is updated and its data is returned.

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 first checking if the index is valid and then linking the node previous to the node in concern and the node next to it. Memory of the node to be deleted is freed, its size updated and 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)

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

Uses the private get_node() function to check if the node 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, 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 doubly linked list.

Returns:

Current size of the doubly linked list.

inline bool is_empty() const

Check if the doubly 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 doubly linked list.