A class for doubly linked lists. More...

#include <AH/Containers/LinkedList.hpp>

Collaboration diagram for DoublyLinkedList< Node >:

Classes
class	node_iterator
	Forward bidirectional doubly linked list iterator. More...

class	node_iterator_base
	Base class for doubly linked list iterators. More...

class	reverse_node_iterator
	Reverse bidirectional doubly linked list iterator. More...

Public Types
using	iterator = node_iterator< Node >

using	const_iterator = node_iterator< const Node >

using	reverse_iterator = reverse_node_iterator< Node >

using	const_reverse_iterator = reverse_node_iterator< const Node >

Public Member Functions
void	append (Node *node)
	Append a node to a linked list. More...

void	append (Node &node)
	Append a node to a linked list. More...

void	insertBefore (Node toBeInserted, Node before)
	Insert a node before another node. More...

void	insertBefore (Node &toBeInserted, Node &before)

template<class Compare >
void	insertSorted (Node *node, Compare cmp)
	Insert a new node at the correct location into a sorted list. More...

void	insertSorted (Node *node)
	Insert a new node at the correct location into a sorted list, using `operator<`. More...

void	remove (Node *node)
	Remove a node from the linked list. More...

void	remove (Node &node)
	Remove a node from the linked list. More...

void	moveDown (Node *node)
	Move down the given node in the linked list. More...

void	moveDown (Node &node)
	Move down the given node in the linked list. More...

bool	couldContain (const Node *node) const
	Check if the linked list could contain the given node. More...

bool	couldContain (const Node &node) const
	Check if the linked list could contain the given node. More...

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

Node *	getFirst () const
	Get a pointer to the first node. More...

Node *	getLast () const
	Get a pointer to the last node. More...

Private Attributes
Node *	first = nullptr

Node *	last = nullptr

Detailed Description

template<class Node>
class DoublyLinkedList< Node >

A class for doubly linked lists.

Template Parameters

Node	The type of the nodes of the list.

Definition at line 25 of file LinkedList.hpp.

Member Typedef Documentation

◆ iterator

using iterator = node_iterator<Node>

Definition at line 104 of file LinkedList.hpp.

◆ const_iterator

using const_iterator = node_iterator<const Node>

Definition at line 105 of file LinkedList.hpp.

◆ reverse_iterator

using reverse_iterator = reverse_node_iterator<Node>

Definition at line 106 of file LinkedList.hpp.

◆ const_reverse_iterator

using const_reverse_iterator = reverse_node_iterator<const Node>

Definition at line 107 of file LinkedList.hpp.

Member Function Documentation

◆ append() [1/2]

void append ( Node * node )

inline

Append a node to a linked list.

Parameters

node	A pointer to the node to be appended.

Definition at line 115 of file LinkedList.hpp.

◆ append() [2/2]

void append ( Node & node )

inline

Append a node to a linked list.

Parameters

node	A reference to the node to be appended.

Definition at line 131 of file LinkedList.hpp.

◆ insertBefore() [1/2]

void insertBefore	(	Node *	toBeInserted,
		Node *	before
	)

inline

Insert a node before another node.

Parameters

toBeInserted	The new node to be inserted.
before	The node to insert the new node before. It must be in the list already.

Definition at line 142 of file LinkedList.hpp.

◆ insertBefore() [2/2]

void insertBefore	(	Node &	toBeInserted,
		Node &	before
	)

inline

See also: insertBefore(Node *, Node *)

Definition at line 153 of file LinkedList.hpp.

◆ insertSorted() [1/2]

void insertSorted	(	Node *	node,
		Compare	cmp
	)

inline

Insert a new node at the correct location into a sorted list.

Parameters

node	The new node to be inserted.
cmp	The function to order the nodes.

Template Parameters

Compare A functor that compares two Nodes and returns a boolean.

Definition at line 168 of file LinkedList.hpp.

◆ insertSorted() [2/2]

void insertSorted ( Node * node )

inline

Insert a new node at the correct location into a sorted list, using operator<.

Parameters

node	The new node to be inserted.

Definition at line 188 of file LinkedList.hpp.

◆ remove() [1/2]

void remove ( Node * node )

inline

Remove a node from the linked list.

Parameters

node	A pointer to the node to be removed.

Definition at line 198 of file LinkedList.hpp.

◆ remove() [2/2]

void remove ( Node & node )

inline

Remove a node from the linked list.

Parameters

node	A reference to the node to be removed.

Definition at line 217 of file LinkedList.hpp.

◆ moveDown() [1/2]

void moveDown ( Node * node )

inline

Move down the given node in the linked list.

For example: moving down node C:

Before: ... → A → B → C → D → ...

After: ... → A → C → B → D → ...

Parameters

node	A pointer to the node to be moved down.

Definition at line 230 of file LinkedList.hpp.

◆ moveDown() [2/2]

void moveDown ( Node & node )

inline

Move down the given node in the linked list.

For example: moving down node C:

Before: ... → A → B → C → D → ...

After: ... → A → C → B → D → ...

Parameters

node	A reference to the node to be moved down.

Definition at line 262 of file LinkedList.hpp.

◆ couldContain() [1/2]

bool couldContain ( const Node * node ) const

inline

Check if the linked list could contain the given node.

Return values

true	The given node is part of some linked list or it is the first node of the given linked list. It could be that the node is part of a different linked list if it was ever added to a different list. However, if this function returns true and the node was never added to another linked list, it means that this linked list contains the given node.
false	The given node is not part of any linked list, or it is the only element of a different linked list.

Definition at line 281 of file LinkedList.hpp.

◆ couldContain() [2/2]

bool couldContain ( const Node & node ) const

inline

Check if the linked list could contain the given node.

Return values

true	The given node is part of some linked list or it is the first node of the given linked list. It could be that the node is part of a different linked list if it was ever added to a different list. However, if this function returns true and the node was never added to another linked list, it means that this linked list contains the given node.
false	The given node is not part of any linked list, or it is the only element of a different linked list.

Definition at line 287 of file LinkedList.hpp.

◆ begin() [1/2]

iterator begin ( )

inline

Definition at line 291 of file LinkedList.hpp.

◆ end() [1/2]

iterator end ( )

inline

Definition at line 292 of file LinkedList.hpp.

◆ begin() [2/2]

const_iterator begin ( ) const

inline

Definition at line 294 of file LinkedList.hpp.

◆ end() [2/2]

const_iterator end ( ) const

inline

Definition at line 295 of file LinkedList.hpp.

◆ rbegin() [1/2]

reverse_iterator rbegin ( )

inline

Definition at line 297 of file LinkedList.hpp.

◆ rend() [1/2]

reverse_iterator rend ( )

inline

Definition at line 298 of file LinkedList.hpp.

◆ rbegin() [2/2]

const_reverse_iterator rbegin ( ) const

inline

Definition at line 300 of file LinkedList.hpp.

◆ rend() [2/2]

const_reverse_iterator rend ( ) const

inline

Definition at line 301 of file LinkedList.hpp.

◆ getFirst()

Node* getFirst ( ) const

inline

Get a pointer to the first node.

Definition at line 304 of file LinkedList.hpp.

◆ getLast()

Node* getLast ( ) const

inline

Get a pointer to the last node.

Definition at line 306 of file LinkedList.hpp.

Member Data Documentation

◆ first

Node* first = nullptr

private

Definition at line 309 of file LinkedList.hpp.

◆ last

Node* last = nullptr

private

Definition at line 310 of file LinkedList.hpp.

The documentation for this class was generated from the following file:

LinkedList.hpp

Classes

Public Types

Public Member Functions

Private Attributes

Detailed Description

template<class Node> class DoublyLinkedList< Node >

Member Typedef Documentation

◆ iterator

◆ const_iterator

◆ reverse_iterator

◆ const_reverse_iterator

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ insertBefore() [1/2]

◆ insertBefore() [2/2]

◆ insertSorted() [1/2]

◆ insertSorted() [2/2]

◆ remove() [1/2]

◆ remove() [2/2]

◆ moveDown() [1/2]

◆ moveDown() [2/2]

◆ couldContain() [1/2]

◆ couldContain() [2/2]

◆ begin() [1/2]

◆ end() [1/2]

◆ begin() [2/2]

◆ end() [2/2]

◆ rbegin() [1/2]

◆ rend() [1/2]

◆ rbegin() [2/2]

◆ rend() [2/2]

◆ getFirst()

◆ getLast()

Member Data Documentation

◆ first

◆ last

template<class Node>
class DoublyLinkedList< Node >