It is a concrete class that defines a fast single linked list. This is a standard data structure that may be used with Last-In-First-Out policies. Use it if you need O(1) time costs for insertions and deletions in the head and tail, but can afford O(n) for searching from first to last element. It cannot iterate from last to first element as gcgDOUBLELINKEDLIST does. 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. Use the gcgLINKEDLIST::getIterator() method to obtain an iterator for the list from head to tail elements. Use gcgQUEUE if you need synchronized and exclusive accesses in enqueue and dequeue operations. More...

#include <gcg.h>

Inheritance diagram for gcgLINKEDLIST:

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

virtual	~gcgLINKEDLIST ()
	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(n) operation because the list is single linked. 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 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. The traversal order for this data structure is from head to tail elements (traversemode is ignored). 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 gcgLINKEDLIST::detach() MUST be used to delete all the nodes or reinsert them into another data structure. The traversal order of the iterator is defined by the parameter traversemode. Currently, the traversal order for this data structure is from head to tail elements (traversemode is ignored). All resources currently used by the gcgLINKEDLIST 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. This is a O(1) operation. More...

bool	insertLast (gcgLINK *node)
	Inserts a new entry node at the TAIL of the list. This is a O(1) operation. 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(n) operation because the list is single linked. More...

bool	moveToFirst (gcgLINK *node)
	Move an entry node that is already in the list to its first position. This is a O(n) operation because the list is single linked. More...

bool	moveToLast (gcgLINK *node)
	Move an entry node that is already in the list to its last position. This is a O(n) operation because the list is single linked. 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(n) operation because the list is single linked. More...

bool	remove (gcgLINK *node)
	Removes an entry node from the linked list. The node is not deleted. This is a O(n) operation because the list is single linked. 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 single linked list. This is a standard data structure that may be used with Last-In-First-Out policies. Use it if you need O(1) time costs for insertions and deletions in the head and tail, but can afford O(n) for searching from first to last element. It cannot iterate from last to first element as gcgDOUBLELINKEDLIST does. 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. Use the gcgLINKEDLIST::getIterator() method to obtain an iterator for the list from head to tail elements. Use gcgQUEUE if you need synchronized and exclusive accesses in enqueue and dequeue operations.

Since: 0.02.133

Constructor & Destructor Documentation

◆ gcgLINKEDLIST()

gcgLINKEDLIST::gcgLINKEDLIST ( )

Constructs a valid and empty linked list.

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

◆ ~gcgLINKEDLIST()

virtual gcgLINKEDLIST::~gcgLINKEDLIST ( )

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 gcgLINKEDLIST::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* gcgLINKEDLIST::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* gcgLINKEDLIST::dequeueLast ( )

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

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* gcgLINKEDLIST::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 gcgLINKEDLIST::detach() MUST be used to delete all the nodes or reinsert them into another data structure. The traversal order of the iterator is defined by the parameter traversemode. Currently, the traversal order for this data structure is from head to tail elements (traversemode is ignored). All resources currently used by the gcgLINKEDLIST 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 this parameter is ignored and the iterator spans the list from the head to tail nodes.

Returns: Returns an 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 gcgLINKEDLIST::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* gcgLINKEDLIST::getIterator ( int traversemode = 0 )

virtual

Returns an iterator for traversing the nodes of the linked list. 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. The traversal order for this data structure is from head to tail elements (traversemode is ignored).

Parameters

traversemode Specifies the order that the available elements in the list must be traversed. Currently this parameter is ignored and the iterator spans the list from the head to tail nodes.

Returns: Returns an iterator for traversing the list from head to tail nodes. 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 gcgLINKEDLIST::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 (gcgLINK) 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 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 gcgLINKEDLIST::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(n) operation because the list is single linked.

Parameters

[in]	newnode	a pointer to a linkable instance (gcgLINK) 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 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 gcgLINKEDLIST::insertFirst ( gcgLINK * node )

virtual

Inserts a new entry node at the HEAD of the list. This is a O(1) operation.

Parameters

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

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 gcgLINKEDLIST::insertLast ( gcgLINK * node )

virtual

Inserts a new entry node at the TAIL of the list. This is a O(1) operation.

Parameters

[in] node a pointer to a linkable instance (gcgLINK) 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.

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 gcgLINKEDLIST::moveToFirst ( gcgLINK * node )

virtual

Move an entry node that is already in the list to its first position. This is a O(n) operation because the list is single linked.

Parameters

[in] node a pointer to a linkable instance (gcgLINK) 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 gcgLINKEDLIST::moveToLast ( gcgLINK * node )

virtual

Move an entry node that is already in the list to its last position. This is a O(n) operation because the list is single linked.

Parameters

[in] node a pointer to a linkable instance (gcgLINK) 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 gcgLINKEDLIST::remove ( gcgLINK * node )

virtual

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

Parameters

[in] node a pointer to a linkable instance (gcgLINK) 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 gcgLINKEDLIST::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(n) operation because the list is single linked.

Parameters

[in]	node1	a pointer to a linkable node (gcgLINK) 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 (gcgLINK) 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

◆ gcgLINKEDLIST()

◆ ~gcgLINKEDLIST()

Member Function Documentation

◆ deleteAll()

◆ dequeueFirst()

◆ dequeueLast()

◆ detach()

◆ getCounter()

◆ getIterator()

◆ insertAfter()

◆ insertBefore()

◆ insertFirst()

◆ insertLast()

◆ moveToFirst()

◆ moveToLast()

◆ remove()

◆ switchNodes()