LinkedList.h #2

#pragma once
// ======================================================================================== //
// Linked List Node class template
// ======================================================================================== //
template <class T> class LinkedListNode
{
public:
	LinkedListNode( ) { };
	~LinkedListNode( ) { };

	LinkedListNode<T>	*prev, *next;
	T					item;
};


// ======================================================================================== //
// Linked List Wrapper class template
// ======================================================================================== //
template <class T> class LinkedList
{
	// --------------------    Constructor/Destructor    --------------------- //
public:
	LinkedList( unsigned int nodes_to_preallocate = 0 );
	~LinkedList( void );
	
	// --------------------  Access functions (Inlined)  --------------------- //
	unsigned int		getSize( );
	LinkedListNode<T>*	getHeadPtr( );
	LinkedListNode<T>*	getTailPtr( );
	LinkedListNode<T>*	getAndUnlinkTailNode( );
	unsigned int		getFreeListSize( );
	LinkedListNode<T>*	getFreeListPtr( );
	LinkedListNode<T>*	getNewNode( );

	// --------------------Insertion and removal functions-------------------- //
	void	insertAfter( LinkedListNode<T> *this_node, LinkedListNode<T> *new_node );
	void	insertAfter( LinkedListNode<T> *this_node, T &item );

	void	insertBefore( LinkedListNode<T> *this_node, LinkedListNode<T> *new_node );
	void	insertBefore( LinkedListNode<T> *this_node, T &item );

	void	insertAtStart( LinkedListNode<T> *new_node );
	void	insertAtStart( T &item );

	void	insertAtEnd( LinkedListNode<T> *new_node );
	void	insertAtEnd( T &item );

	void	unlinkNode( LinkedListNode<T> *this_node );
	void	removeNode( LinkedListNode<T> *this_node );
	void	removeHeadNode( );
	void	removeTailNode( );
	void	removeAllNodes( );
	void	removeAllNodesBetween( LinkedListNode<T> *this_node, LinkedListNode<T> *and_this_node );
	void	removeAllNodesAfter( LinkedListNode<T> *this_node );
	void	removeAllNodesBefore( LinkedListNode<T> *this_node );

	// ------------------------ Additional Operations ------------------------ //
	void	purgeFreeList( );
	T*		convertToArray( );
	void	reverseList( );
	void	copyFromOtherListAfter( LinkedListNode<T> *this_node, LinkedList<T> *other_list );
	void	copyFromOtherListBefore( LinkedListNode<T> *this_node, LinkedList<T> *other_list );
	bool	checkListIntegrity( );
	
	
	// ========================        PRIVATE       ========================= //
private:
	void	returnNodeToFreeList(LinkedListNode<T> *this_node);
	void	populateFreeList( );
	void	allocateAdditionalMemoryBlock( unsigned int number_of_nodes );
	void	insertFirstNode( LinkedListNode<T> *new_node );
	void	deleteMemory();

	LinkedListNode<T>	*head_ptr, *tail_ptr;
	unsigned int		size, size_of_free_pool;

	// Memory preallocation
	unsigned int	memory_block_count;			// Total blocks used at the moment
	unsigned int	memory_nodes_per_block;		// This will be constant, number of NODES per block
												// If it is '0', no preallocation is done.

	LinkedListNode<T>	*head_ptr_of_free_pool;
	LinkedListNode<T>	**memory_node_blocks;
};


//------------------------------------------------------------------------------------
//	LinkedList()
//
//	Description	-	Create a linked list structure wrapper.  Will preallocate
//					'nodes_to_preallocate' number of list nodes and keep track of
//					a free node pool.  If 'nodes_to_preallocate' is 0, all memory
//					allocation/deletion is done one node at a time (recommended for small
//					lists, maybe 20 nodes max, that do not grow or shrink much)
//------------------------------------------------------------------------------------
template <class T>
LinkedList<T>::LinkedList( unsigned int nodes_to_preallocate /*=0*/ ) : 
							 head_ptr(0),tail_ptr(0),size(0),size_of_free_pool(0)
{
	memory_nodes_per_block = nodes_to_preallocate;

	// Initialize to 0, because allocateAdditionalMemoryBlock() increments this by one
	memory_block_count = 0;
	memory_node_blocks = NULL;
	head_ptr_of_free_pool = NULL;

	if ( nodes_to_preallocate > 0 )
	{
		allocateAdditionalMemoryBlock( nodes_to_preallocate );
	}
}

template <class T>
LinkedList<T>::~LinkedList()
{
	deleteMemory( );
}


//====================================================================================
//	Access Functions
//====================================================================================

template <class T>	inline
unsigned int		LinkedList<T>::getSize( )
{
	return	size;
}

template <class T>	inline
LinkedListNode<T>*	LinkedList<T>::getHeadPtr( )
{
	return	head_ptr;
}

template <class T>	inline
LinkedListNode<T>*	LinkedList<T>::getTailPtr( )
{
	return	tail_ptr;
}

//------------------------------------------------------------------------------------
//	This should be used after initial list construction to allocate 'item's if it is
//	a pointer type.  And then can be called again before list destruction to free
//	items that have gotten into the free pool.
//------------------------------------------------------------------------------------
template <class T>	inline
LinkedListNode<T>*	LinkedList<T>::getFreeListPtr( )
{
	return	head_ptr_of_free_pool;
}

template <class T>	inline
unsigned int		LinkedList<T>::getFreeListSize( )
{
	return	size_of_free_pool;
}


//------------------------------------------------------------------------------------
//	getNewNode()
//	Description	-	Obtains a node from the free list, if there are not any left, we
//					will increase the size of the free list by 'memory_nodes_per_block'
//
//	NOTE: This function should always be used to obtain new nodes for an existing list!!
//------------------------------------------------------------------------------------
template <class T>	inline
LinkedListNode<T>* LinkedList<T>::getNewNode()
{
	LinkedListNode<T>	*new_node = head_ptr_of_free_pool;

	// See if we have obtained a valid free node
	if ( !new_node )
	{
		// We have ran out of free nodes in preallocated list, allocate more
		populateFreeList();
		new_node = head_ptr_of_free_pool;
	}

	head_ptr_of_free_pool = new_node->next;
	--size_of_free_pool;
	return	new_node;
}


//====================================================================================
//=======================   REST OF FUNCTIONS    =====================================
//====================================================================================

#include "LinkedList.hpp"

//====================================================================================
//=======================      END OF FILE       =====================================
//====================================================================================