It is a concrete class that defines a fast double linked list. This is a standard data structure that may be used with First-In-First-Out or Last-In-First-Out policies. Use it if you need O(1) time costs for insertions and deletions at head and tail, but can afford O(n) for searching. You must use gcgDOUBLELINK or its specializations in all methods. A drawback of using linked lists is their tendency to fragment memory and have low cache hits during searches. These problems can be avoided using arrays. This class can iterate from first to last element and vice-versa. Use the gcgDOUBLELINKEDLIST::getIterator() method to obtain an iterator for the list to span the nodes from head to tail or vice-versa. Use gcgLINKEDLIST if you need a simpler single linked lists which can be only spanned from head to tail. More...

#include <gcg.h>

Inheritance diagram for gcgDOUBLELINKEDLIST:

Public Member Functions
	gcgDOUBLELINKEDLIST ()
	Constructs a valid and empty linked list. More...

virtual	~gcgDOUBLELINKEDLIST ()
	Destroys the linked list, releasing the list of nodes. All entries are deleted. More...

gcgLINK *	dequeueFirst ()
	Returns the first entry stored in the linked list. The entry is removed from the top of the list. This is a O(1) operation. More...

gcgLINK *	dequeueLast ()
	Returns the last entry stored in the linked list. The entry is removed from the end of the list. This is a O(1) operation. More...

uintptr_t	getCounter ()
	Returns the number of elements stored in the list. More...

bool	deleteAll ()
	Deletes and removes all entries from the linked list. All list resources are also released. More...

gcgITERATOR *	getIterator (int traversemode=0)
	Returns an iterator for traversing the nodes of the linked list. The traversal order is defined by the parameter traversemode. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head. The linked list must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the data structure. Note that deleting a iterator does not affect the nodes. More...

gcgITERATOR *	detach (int traversemode=0)
	Force the list to be empty. It has the same effect as removing all entries from the linked list but keeping their chaining (which will used by the returned iterator). The nodes are NOT deleted. In order to retrieve the detached nodes, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying data strucuture. Thus, the gcgITERATOR returned by gcgDOUBLELINKEDLIST::detach() MUST be used to delete all the nodes or reinsert them in another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head. All resources currently used by the gcgDOUBLELINKEDLIST are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use. More...

bool	insertFirst (gcgLINK *node)
	Inserts a new entry node at the HEAD of the list. The node will have a NULL left/previous link. More...

bool	insertLast (gcgLINK *node)
	Inserts a new entry node at the TAIL of the list. The node will have a NULL right/next link. More...

bool	insertAfter (gcgLINK newnode, gcgLINK node)
	Inserts a new entry newnode in the list, after an existent entry pointed by node. This is a O(1) operation. More...

bool	insertBefore (gcgLINK newnode, gcgLINK node)
	Inserts a new entry newnode in the list, before an existent entry pointed by node. This is a O(1) operation. More...

bool	moveToFirst (gcgLINK *node)
	Move an entry node that is already in the list to its first position. The node will have a NULL previous link. This is a O(1) operation. More...

bool	moveToLast (gcgLINK *node)
	Move an entry node that is already in the list to its last position. The node will have a NULL next link. This is a O(1) operation. More...

bool	switchNodes (gcgLINK node1, gcgLINK node2)
	Switches the position of two existent elements of the linked list. The two nodes must be part of the list. This is a O(1) operation. More...

bool	remove (gcgLINK *node)
	Removes an entry node from the linked list. The node is not deleted. This is a O(1) operation. More...

Public Member Functions inherited from gcgCLASS
void *	operator new (size_t size)
	Defines a new operator to be used by instatiations of GCGlib classes instead the global one. More...

void *	operator new (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by instantiations of GCGlib classes instead the global one. Returns a NULL pointer instead of throwing an exception if an error occurs. More...

void *	operator new[] (size_t size)
	Defines a new operator to be used by GCGlib array allocations instead the global one. More...

void *	operator new[] (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by vector allocations instead the global one. More...

void	operator delete (void *p)
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete[] (void *p)
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

void	operator delete[] (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

Public Attributes
gcgLINK *	first
	Points to the first gcgLINK node in the list. Read-only.

gcgLINK *	last
	Points to the last gcgLINK node in the list. Read-only.

uintptr_t	counter
	Number of elements in this list. Read-only.

Detailed Description

It is a concrete class that defines a fast double linked list. This is a standard data structure that may be used with First-In-First-Out or Last-In-First-Out policies. Use it if you need O(1) time costs for insertions and deletions at head and tail, but can afford O(n) for searching. You must use gcgDOUBLELINK or its specializations in all methods. A drawback of using linked lists is their tendency to fragment memory and have low cache hits during searches. These problems can be avoided using arrays. This class can iterate from first to last element and vice-versa. Use the gcgDOUBLELINKEDLIST::getIterator() method to obtain an iterator for the list to span the nodes from head to tail or vice-versa. Use gcgLINKEDLIST if you need a simpler single linked lists which can be only spanned from head to tail.

Since: 0.02.113

Constructor & Destructor Documentation

◆ gcgDOUBLELINKEDLIST()

gcgDOUBLELINKEDLIST::gcgDOUBLELINKEDLIST ( )

Constructs a valid and empty linked list.

See also: insertFirst(); insertLast(); remove(); gcgLINK

◆ ~gcgDOUBLELINKEDLIST()

virtual gcgDOUBLELINKEDLIST::~gcgDOUBLELINKEDLIST ( )

virtual

Destroys the linked list, releasing the list of nodes. All entries are deleted.

See also: insertFirst(); insertLast(); dequeueHead(); dequeueTail(); insertAfter(); insertBefore(); remove()

Member Function Documentation

◆ deleteAll()

bool gcgDOUBLELINKEDLIST::deleteAll ( )

virtual

Deletes and removes all entries from the linked list. All list resources are also released.

Returns: Returns true if all entries were deleted and removed. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ dequeueFirst()

gcgLINK* gcgDOUBLELINKEDLIST::dequeueFirst ( )

Returns the first entry stored in the linked list. The entry is removed from the top of the list. This is a O(1) operation.

Returns: returns the pointer of the head entry. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); insertLast(); dequeueLast(); insertAfter(); insertBefore(); remove()

◆ dequeueLast()

gcgLINK* gcgDOUBLELINKEDLIST::dequeueLast ( )

Returns the last entry stored in the linked list. The entry is removed from the end of the list. This is a O(1) operation.

Returns: returns the pointer of the tail entry. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); insertLast(); dequeueFirst(); insertAfter(); insertBefore(); remove()

◆ detach()

gcgITERATOR* gcgDOUBLELINKEDLIST::detach ( int traversemode = 0 )

virtual

Force the list to be empty. It has the same effect as removing all entries from the linked list but keeping their chaining (which will used by the returned iterator). The nodes are NOT deleted. In order to retrieve the detached nodes, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying data strucuture. Thus, the gcgITERATOR returned by gcgDOUBLELINKEDLIST::detach() MUST be used to delete all the nodes or reinsert them in another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head. All resources currently used by the gcgDOUBLELINKEDLIST are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use.

Parameters

traversemode Specifies the order that the available elements in the list must be traversed by the returned iterator. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head.

Returns: Returns a iterator for traversing the elements that were detached from the linked list. The linked list becomes empty and can be reused. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: deleteAll(); getIterator()

Implements gcgDATASTRUCTURE.

◆ getCounter()

uintptr_t gcgDOUBLELINKEDLIST::getCounter ( )

virtual

Returns the number of elements stored in the list.

Returns: Returns the number of elements currently in the list.

Implements gcgDATASTRUCTURE.

◆ getIterator()

gcgITERATOR* gcgDOUBLELINKEDLIST::getIterator ( int traversemode = 0 )

virtual

Returns an iterator for traversing the nodes of the linked list. The traversal order is defined by the parameter traversemode. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head. The linked list must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the data structure. Note that deleting a iterator does not affect the nodes.

Parameters

traversemode Specifies the order that the available elements in the list must be traversed. Currently, there are two modes implemented: traversemode = 0, for head to tail iteration (default); and traversemode = 1, to iterate from tail to head.

Returns: Returns an iterator for traversing the list from head to tail nodes in the order defined by traversemode. The list must not be changed by insertions, removals or moves while the iterator is being used. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ insertAfter()

bool gcgDOUBLELINKEDLIST::insertAfter	(	gcgLINK *	newnode,
		gcgLINK *	node
	)

virtual

Inserts a new entry newnode in the list, after an existent entry pointed by node. This is a O(1) operation.

Parameters

[in]	newnode	a pointer to a linkable instance (gcgDOUBLELINK) to be inserted after node. This pointer is deleted by the destructor or a deleteAll() call. A NULL value generates an error.
[in]	node	a pointer to an gcgDOUBLELINK entry that is already linked in the list. A NULL value has the same effect as insertLast(newnode). After the insertion, the newnode will follow the node in the list: node->next = newnode and newnode->previous = node.

Returns: returns true if the data is successfully inserted after node. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertLast(); insertBefore(); dequeueFirst(); dequeueLast(); remove()

Implements gcgLISTSTRUCTURE.

◆ insertBefore()

bool gcgDOUBLELINKEDLIST::insertBefore	(	gcgLINK *	newnode,
		gcgLINK *	node
	)

virtual

Inserts a new entry newnode in the list, before an existent entry pointed by node. This is a O(1) operation.

Parameters

[in]	newnode	a pointer to a linkable instance (gcgDOUBLELINK) to be inserted after node. This pointer is deleted by the destructor or a deleteAll() call. A NULL value generates an error.
[in]	node	a pointer to a gcgDOUBLELINK entry that is already linked in the list. A NULL value has the same effect as insertFirst(newnode). After the insertion, the node will follow the newnode in the list: newnode->next = node and node->previous = newnode.

Returns: returns true if the data is successfully inserted after node. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); insertAfter(); dequeueFirst(); dequeueLast(); remove()

Implements gcgLISTSTRUCTURE.

◆ insertFirst()

bool gcgDOUBLELINKEDLIST::insertFirst ( gcgLINK * node )

virtual

Inserts a new entry node at the HEAD of the list. The node will have a NULL left/previous link.

Parameters

[in] node a pointer to a linkable instance (gcgDOUBLELINK) to be held in the new queue entry. This pointer is deleted by the destructor or deleteAll(). A NULL value generates an error. This is a O(1) operation.

Returns: returns true if the data is successfully inserted at the top of the queue. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertLast(); dequeueFirst(); dequeueLast(); insertAfter(); insertBefore(); remove()

Implements gcgLISTSTRUCTURE.

◆ insertLast()

bool gcgDOUBLELINKEDLIST::insertLast ( gcgLINK * node )

virtual

Inserts a new entry node at the TAIL of the list. The node will have a NULL right/next link.

Parameters

[in] node a pointer to a linkable instance (gcgDOUBLELINK) to be inserted in the linked list's tail. This pointer is deleted by the destructor or a deleteAll() call. A NULL value generates an error. This is a O(1) operation.

Returns: returns true if the data is successfully inserted at the end of the linked list. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); dequeueFirst(); dequeueLast(); insertAfter(); insertBefore(); remove()

Implements gcgLISTSTRUCTURE.

◆ moveToFirst()

bool gcgDOUBLELINKEDLIST::moveToFirst ( gcgLINK * node )

virtual

Move an entry node that is already in the list to its first position. The node will have a NULL previous link. This is a O(1) operation.

Parameters

[in] node a pointer to a linkable instance (gcgDOUBLELINK) that is already in the list. A NULL value generates an error.

Returns: returns true if the data is successfully moved to the beginning of the linked list. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); dequeueFirst(); dequeueLast(); insertAfter(); insertBefore(); remove(); moveToLast()

Implements gcgLISTSTRUCTURE.

◆ moveToLast()

bool gcgDOUBLELINKEDLIST::moveToLast ( gcgLINK * node )

virtual

Move an entry node that is already in the list to its last position. The node will have a NULL next link. This is a O(1) operation.

Parameters

[in] node a pointer to a linkable instance (gcgDOUBLELINK) that is already in the list. A NULL value generates an error.

Returns: returns true if the data is successfully moved to the end of the linked list. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); dequeueFirst(); dequeueLast(); insertAfter(); insertBefore(); remove(); moveToFirst()

Implements gcgLISTSTRUCTURE.

◆ remove()

bool gcgDOUBLELINKEDLIST::remove ( gcgLINK * node )

virtual

Removes an entry node from the linked list. The node is not deleted. This is a O(1) operation.

Parameters

[in] node a pointer to a linkable instance (gcgDOUBLELINK) to be removed from the list. The node must be an element of this list. A NULL value generates an error.

Returns: returns true if the data is successfully removed from the list. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insertFirst(); insertLast(); dequeueFirst(); dequeueLast(); insertAfter(); insertBefore()

Implements gcgLISTSTRUCTURE.

◆ switchNodes()

bool gcgDOUBLELINKEDLIST::switchNodes	(	gcgLINK *	node1,
		gcgLINK *	node2
	)

virtual

Switches the position of two existent elements of the linked list. The two nodes must be part of the list. This is a O(1) operation.

Parameters

[in]	node1	a pointer to a linkable node (gcgDOUBLELINK) that carries the information to be switched with the position of node2. If NULL, an error occurs.
[in]	node2	a pointer to a linkable node (gcgDOUBLELINK) that carries the information to be switched with the position of node1. If NULL, an error occurs.

Returns: true if the nodes are correctly switched. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insert()

Implements gcgLISTSTRUCTURE.

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

M:/Documentos/Projetos/Projetos/GCGlib/src/gcg.h

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ gcgDOUBLELINKEDLIST()

◆ ~gcgDOUBLELINKEDLIST()

Member Function Documentation

◆ deleteAll()

◆ dequeueFirst()

◆ dequeueLast()

◆ detach()

◆ getCounter()

◆ getIterator()

◆ insertAfter()

◆ insertBefore()

◆ insertFirst()

◆ insertLast()

◆ moveToFirst()

◆ moveToLast()

◆ remove()

◆ switchNodes()