LinkedList is an managed double linked list implementation. More...

#include <linkedlist.h>

Collaboration diagram for semf::LinkedList< T >:

Classes
class	ConstIterator
	Implementation of a bidirectional constant iterator for `LinkedList`. More...

class	Iterator
	Implementation of a bidirectional iterator for `LinkedList`. More...

class	Node
	Implements the `previous()` and `next()` functionality for every element in a list. More...

Public Member Functions
	LinkedList ()
	Creates an empty List. More...

T &	front ()
	Returns a reference to the first element in the list. More...

const T &	front () const
	Returns a reference to the first element in the list. More...

T &	back ()
	Returns a reference to the last element in the list. More...

const T &	back () const
	Returns a reference to the last element in the list. More...

Iterator	begin ()
	Returns an iterator pointing to the first element in the list. More...

ConstIterator	begin () const
	Returns an iterator pointing to the first element in the list. More...

ConstIterator	cbegin () const
	Returns an iterator pointing to the first element in the list. More...

Iterator	end ()
	Returns an iterator referring to the past-the-end element in the list. More...

ConstIterator	end () const
	Returns an iterator referring to the past-the-end element in the list. More...

ConstIterator	cend () const
	Returns an iterator referring to the past-the-end element in the list. More...

bool	empty () const
	Returns whether the list is empty (i.e. whether its size is 0). More...

size_t	size () const
	Returns the number of elements in the list. More...

void	clear ()
	Removes all elements from the list and leaving the list with a size of 0. More...

Iterator	insert (Iterator position, T &element)
	The list is extended by inserting new elements before the element at the specified position. More...

Iterator	erase (Iterator position)
	Removes a single element from the list. More...

Iterator	erase (Iterator first, Iterator last)
	Removes multiple elements from the list. More...

void	pushBack (T &element)
	Adds a new element to the end of the list, after its current last element. More...

void	pushFront (T &element)
	Adds a new element to the beginning of the list, before its current first element. More...

void	popBack ()
	Removes the last element in the list, effectively reducing the list size by one. More...

void	popFront ()
	Removes the first element in the list, effectively reducing the list size by one. More...

LinkedList< T > &	operator= (const LinkedList< T > &list)
	Assigns new contents to the list, replacing its current contents, and modifying its size accordingly. More...

Detailed Description

template<class T>
class semf::LinkedList< T >

LinkedList is an managed double linked list implementation.

It is similar to std::list, but works without dynamic storage allocation. Every element in the list has to inherit from LinkedList::Node and in case has the information of the previous() and the next() node.

Like std::list LinkedList also is a sequence of elements that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

List is implemented as doubly-linked lists. Double linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

Attention: A node is only allowed to be part of one list. Putting a node into a second list changes the references in the element. That causes to undefined behavior by iterating through the lists.

Template Parameters

T	class type inherits from `LinkedList::Node`

Definition at line 42 of file linkedlist.h.

Constructor & Destructor Documentation

◆ LinkedList()

template<class T >

semf::LinkedList< T >::LinkedList

Creates an empty List.

Definition at line 542 of file linkedlist.h.

Member Function Documentation

◆ back() [1/2]

template<class T >

T & semf::LinkedList< T >::back

Returns a reference to the last element in the list.

Unlike member LinkedList::end, which returns an iterator to this same element, this function returns a direct reference. Calling this function on a not existing element causes undefined behavior.

Returns: Reference to the last element.

Definition at line 560 of file linkedlist.h.

◆ back() [2/2]

template<class T >

const T & semf::LinkedList< T >::back

Returns a reference to the last element in the list.

Unlike member LinkedList::end, which returns an iterator to this same element, this function returns a direct reference. Calling this function on a not existing element causes undefined behavior.

Returns: For a const-qualified list object returns a const reference to the last element.

Definition at line 566 of file linkedlist.h.

◆ begin() [1/2]

template<class T >

LinkedList< T >::Iterator semf::LinkedList< T >::begin

Returns an iterator pointing to the first element in the list.

Attention: Notice that, unlike member LinkedList::front, which returns a reference to the first element, this function returns a bidirectional iterator pointing to it. If the list is empty, the returned iterator value shall not be dereferenced.

Returns: An iterator to the beginning of the sequence.

Definition at line 572 of file linkedlist.h.

◆ begin() [2/2]

template<class T >

LinkedList< T >::ConstIterator semf::LinkedList< T >::begin

Returns an iterator pointing to the first element in the list.

Attention: Notice that, unlike member LinkedList::front, which returns a reference to the first element, this function returns a bidirectional iterator pointing to it. If the list is empty, the returned iterator value shall not be dereferenced.

Returns: An iterator to the beginning of the sequence.

Definition at line 578 of file linkedlist.h.

◆ cbegin()

template<class T >

LinkedList< T >::ConstIterator semf::LinkedList< T >::cbegin

Returns an iterator pointing to the first element in the list.

Attention: Notice that, unlike member LinkedList::front, which returns a reference to the first element, this function returns a bidirectional iterator pointing to it. If the list is empty, the returned iterator value shall not be dereferenced.

Returns: An iterator to the beginning of the sequence.

Definition at line 584 of file linkedlist.h.

◆ cend()

template<class T >

LinkedList< T >::ConstIterator semf::LinkedList< T >::cend

Returns an iterator referring to the past-the-end element in the list.

The past-the-end element is the theoretical element that would follow the last element in the list. It does not point to any element, and thus shall not be dereferenced. This function is often used in combination with LinkedList::begin to specify a range including all the elements in the range. If LinkedList is empty, this function returns the same as LinkedList::begin.

Returns: An iterator to the element past the end of the sequence.

Definition at line 602 of file linkedlist.h.

◆ clear()

template<class T >

void semf::LinkedList< T >::clear

Removes all elements from the list and leaving the list with a size of 0.

Definition at line 620 of file linkedlist.h.

◆ empty()

template<class T >

bool semf::LinkedList< T >::empty

Returns whether the list is empty (i.e. whether its size is 0).

This function does not modify the list in any way. To clear the content of a list container, see LinkedList::clear.

Returns: true if the list size is 0, false otherwise.

Definition at line 608 of file linkedlist.h.

◆ end() [1/2]

template<class T >

LinkedList< T >::Iterator semf::LinkedList< T >::end

Returns an iterator referring to the past-the-end element in the list.

The past-the-end element is the theoretical element that would follow the last element in the list. It does not point to any element, and thus shall not be dereferenced. This function is often used in combination with LinkedList::begin to specify a range including all the elements in the range. If LinkedList is empty, this function returns the same as LinkedList::begin.

Returns: An iterator to the element past the end of the sequence.

Definition at line 590 of file linkedlist.h.

◆ end() [2/2]

template<class T >

LinkedList< T >::ConstIterator semf::LinkedList< T >::end

Returns an iterator referring to the past-the-end element in the list.

The past-the-end element is the theoretical element that would follow the last element in the list. It does not point to any element, and thus shall not be dereferenced. This function is often used in combination with LinkedList::begin to specify a range including all the elements in the range. If LinkedList is empty, this function returns the same as LinkedList::begin.

Returns: An iterator to the element past the end of the sequence.

Definition at line 596 of file linkedlist.h.

◆ erase() [1/2]

template<class T >

LinkedList< T >::Iterator semf::LinkedList< T >::erase	(	Iterator	first,
		Iterator	last
	)

Removes multiple elements from the list.

This effectively reduces the list size by the number if erased elements.

Attention: This function does not check whether position points to an element inside this.

Parameters

first	First element of a sequence to remove from the list.
last	Last element of a sequence to remove from the list.

Returns: An iterator pointing to the element that followed the last element erased by the function call.

Definition at line 679 of file linkedlist.h.

◆ erase() [2/2]

template<class T >

LinkedList< T >::Iterator semf::LinkedList< T >::erase ( Iterator position )

Removes a single element from the list.

This effectively reduces the list size by one.

Attention: This function does not check whether the given range points to this.

Parameters

position Position to erase from the list. Position has to have a exiting element.

Returns: An iterator pointing to the element that followed the node erased by the function call.

Definition at line 654 of file linkedlist.h.

Here is the call graph for this function:

◆ front() [1/2]

template<class T >

T & semf::LinkedList< T >::front

Returns a reference to the first element in the list.

Unlike member LinkedList::begin, which returns an iterator to this same element, this function returns a direct reference. Calling this function on a not existing element causes undefined behavior.

Returns: Reference to the first element.

Definition at line 548 of file linkedlist.h.

◆ front() [2/2]

template<class T >

const T & semf::LinkedList< T >::front

Returns a reference to the first element in the list.

Unlike member LinkedList::begin, which returns an iterator to this same element, this function returns a direct reference. Calling this function on a not existing element causes undefined behavior.

Returns: For a const-qualified list object returns a const reference to the first element.

Definition at line 554 of file linkedlist.h.

◆ insert()

template<class T >

LinkedList< T >::Iterator semf::LinkedList< T >::insert	(	Iterator	position,
		T &	element
	)

The list is extended by inserting new elements before the element at the specified position.

Parameters

position	Position in the list where the new element is inserted.
element	Element to be inserted into the list.

Returns: An iterator that points to the newly inserted element.

Definition at line 628 of file linkedlist.h.

◆ operator=()

template<class T >

LinkedList< T > & semf::LinkedList< T >::operator= ( const LinkedList< T > & list )

Assigns new contents to the list, replacing its current contents, and modifying its size accordingly.

Parameters

list	A list object of the same type (i.e., with the same template parameter).

Returns: Reference to this list.

Definition at line 755 of file linkedlist.h.

◆ popBack()

template<class T >

void semf::LinkedList< T >::popBack

Removes the last element in the list, effectively reducing the list size by one.

Definition at line 725 of file linkedlist.h.

◆ popFront()

template<class T >

void semf::LinkedList< T >::popFront

Removes the first element in the list, effectively reducing the list size by one.

Definition at line 741 of file linkedlist.h.

◆ pushBack()

template<class T >

void semf::LinkedList< T >::pushBack ( T & element )

Adds a new element to the end of the list, after its current last element.

The content of element is moved into the list. This effectively increases the list size by one.

Parameters

element Element to add to the end of the list.

Definition at line 689 of file linkedlist.h.

◆ pushFront()

template<class T >

void semf::LinkedList< T >::pushFront ( T & element )

Adds a new element to the beginning of the list, before its current first element.

The content of element is moved into the list. This effectively increases the list size by one.

Parameters

element Element to add to the beginning of the list.

Definition at line 708 of file linkedlist.h.

◆ size()

template<class T >

size_t semf::LinkedList< T >::size

Returns the number of elements in the list.

Returns: Number of elements in the list.

Definition at line 614 of file linkedlist.h.

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LinkedList()

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ insert()

◆ operator=()

◆ popBack()

◆ popFront()

◆ pushBack()

◆ pushFront()

◆ size()