//#include "LinkedList.h"


//------------------------------------------------------------------------------------
//	populateFreeList()
//	Description	-	Call to fill up the free pool list (NOTE: list should be empty
//					before calling this... we completely replace whatever was in it)
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::populateFreeList( )
{
	if ( memory_nodes_per_block > 0 )
	{
		// Allocate another memory block
		allocateAdditionalMemoryBlock( memory_nodes_per_block );
		
		// Initialize head_ptr to point to these new blocks
		head_ptr_of_free_pool = &memory_node_blocks[memory_block_count-1][0];

		// Insert into available LinkedListNode<T> list everything that was just allocated
		LinkedListNode<T>	*cur_free_pool_ptr = head_ptr_of_free_pool;
		for (unsigned int i = 1; i < memory_nodes_per_block; i++)
		{
			cur_free_pool_ptr->next = &memory_node_blocks[memory_block_count-1][i];
			cur_free_pool_ptr = cur_free_pool_ptr->next;
		}

		// Make last one point at nothing
		cur_free_pool_ptr->next = NULL;
	}
	// Allocate a single new node if memory block preallocation disabled
	else
	{
		LinkedListNode<T>	*cur_free_pool_ptr = new LinkedListNode<T>();
		cur_free_pool_ptr->next = head_ptr_of_free_pool;
		head_ptr_of_free_pool = cur_free_pool_ptr;
		++size_of_free_pool;
	}
}


//------------------------------------------------------------------------------------
//	allocateAdditionalMemoryBlock()
//	Description	-	Allocates memory block with number 'number_of_nodes' nodes.  Can
//					be accessed using ( memory_node_blocks[memory_block_count-1] )
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::allocateAdditionalMemoryBlock( unsigned int number_of_nodes )
{
	// Assume head_ptr_of_free_pool is INVALID when this is called
	++memory_block_count;
	size_of_free_pool += number_of_nodes;

	// Expand memory_node_blocks by one
	LinkedListNode<T> **memory_node_blocks_orig = memory_node_blocks;
	memory_node_blocks = new LinkedListNode<T>* [memory_block_count];
	memory_node_blocks[memory_block_count-1] = new LinkedListNode<T> [number_of_nodes];

	// Copy over pointers from pre-existing blocks (if any)
	for (unsigned int i=0; i < (memory_block_count-1); i++)
	{
		memory_node_blocks[i] = memory_node_blocks_orig[i];
	}
	// Delete previous memory block array
	if ( memory_node_blocks_orig )
	{
		delete[] memory_node_blocks_orig;
	}
}


//------------------------------------------------------------------------------------
//	returnNodeToFreeList()
//	Description	-	Returns specified node to the free list.  This node is corrupt,
//					whatever is in it should not be used.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::returnNodeToFreeList(LinkedListNode<T> *this_node)
{
	this_node->next = head_ptr_of_free_pool;
	head_ptr_of_free_pool = this_node;
	++size_of_free_pool;
}


//------------------------------------------------------------------------------------
//	insertAfter()
//	Description	-	Inserts 'new_node' after 'this_node' in linked list.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::insertAfter( LinkedListNode<T> *this_node, LinkedListNode<T> *new_node )
{
	// Make sure we have a head_ptr pointer
	if ( head_ptr )
	{
		// We are in middle of list, can just insert
		if ( this_node->next )
		{
			// Update pointers on the new node
			new_node->next = this_node->next;
			new_node->prev = this_node;
			// Next node will now have previous node be the new one
			this_node->next->prev = new_node;
			// Node we are inserting after, will have new node being next
			this_node->next = new_node;

			++size;
		}
		// We are at end of list, use other function
		else
		{
			this->insertAtEnd( new_node );
		}
	}
	// This is the very first item, make both head_ptr and tail_ptr point to it
	else
	{		
		insertFirstNode( new_node );
		++size;
	}
}

template <class T>
void	LinkedList<T>::insertAfter( LinkedListNode<T> *this_node, T &item )
{
	insertAfter( this_node, getNewNode() );
	this_node->next->item = item;
}


//------------------------------------------------------------------------------------
//	insertAtEnd()
//	Description	-	Inserts 'new_node' at very end of linked list.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::insertAtEnd( LinkedListNode<T> *new_node )
{
	// Make sure this is not the very first item in list
	if ( tail_ptr )
	{
		// Make the new_node point to correct places
		new_node->prev = tail_ptr;
		new_node->next = NULL;
		// Update tail_ptr pointer
		tail_ptr->next = new_node;
		tail_ptr = new_node;
	}
	// First item in list, make head_ptr and tail_ptr point at it
	else
	{
		insertFirstNode( new_node );
	}
	
	++size;
}

template <class T>
void	LinkedList<T>::insertAtEnd( T &item )
{
	insertAtEnd( getNewNode() );
	tail_ptr->item = item;
}


//------------------------------------------------------------------------------------
//	insertBefore()
//	Description	-	Inserts 'new_node' before 'this_node'
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::insertBefore( LinkedListNode<T> *this_node, LinkedListNode<T> *new_node )
{
	// Make sure this is not the very first item in list
	if ( head_ptr )
	{
		// Make sure this is not being inserted at the start
		if ( this_node->prev )
		{
			// Make the new_node point to correct places
			new_node->prev = this_node->prev;
			new_node->next = this_node;
			// Update it's neighbors pointers
			this_node->prev->next = new_node;
			this_node->prev = new_node;
			++size;
		}
		else
		{
			insertAtStart( new_node );
		}
	}
	// First item in list, make head_ptr and tail_ptr point at it
	else
	{
		insertFirstNode( new_node );
		++size;
	}
}

template <class T>
void	LinkedList<T>::insertBefore( LinkedListNode<T> *this_node, T &item )
{
	insertBefore( this_node, getNewNode() );
	this_node->prev->item = item;
}


//------------------------------------------------------------------------------------
//	insertAtStart()
//	Description	-	Inserts 'new_node' at very start of list
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::insertAtStart( LinkedListNode<T> *new_node )
{
	// Make sure this is not the very first item in list
	if ( head_ptr )
	{
		// Make the new_node point to correct places
		new_node->prev = NULL;
		new_node->next = head_ptr;
		// Update head_ptr pointer and previous head_ptr nodes info
		head_ptr = new_node;
		head_ptr->next->prev = head_ptr;
	}
	// First item in list, make head_ptr and tail_ptr point at it
	else
	{
		insertFirstNode( new_node );
	}
	++size;
}

template <class T>
void	LinkedList<T>::insertAtStart( T &item )
{
	insertAtStart( getNewNode() );
	head_ptr->item = item;
}


//------------------------------------------------------------------------------------
//	insertAtStart() *private*
//	Description	-	Inserts 'new_node' if list is empty
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::insertFirstNode( LinkedListNode<T> *new_node )
{
	// We should initialize next/prev pointers to NULL
	new_node->next = NULL;
	new_node->prev = NULL;
	// Make both tail and head point at it
	head_ptr = new_node;
	tail_ptr = new_node;
}


//------------------------------------------------------------------------------------
//	unlinkNode()
//	Description	-	Unlinks node from list, preserving lists structure minus the node.
//					WARNING: Does NOT place node in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::unlinkNode( LinkedListNode<T> *this_node )
{
	// If there is more than 1 Node in List, we will need to do
	// some pointer rearranging.
	if ( size > 1 )
	{
		// If there is a previous Node, just make it point to the next
		// one.
		if ( this_node->prev )
		{
			this_node->prev->next = this_node->next;
		}
		// Otherwise Head LinkedListNode<T> is being removed, update Head pointer
		else
		{
			head_ptr = this_node->next;
			head_ptr->prev = NULL;
		}

		// If there is a next Node, just make it point to the previous
		// one.
		if ( this_node->next )
		{
			this_node->next->prev = this_node->prev;
		}
		// Otherwise Tail LinkedListNode<T> is being removed, update tail_ptr pointer
		else
		{
			tail_ptr = this_node->prev;
			tail_ptr->next = NULL;
		}
	}
	else
	{
		tail_ptr = NULL;
		head_ptr = NULL;
		size = 1;	// Prevent underflow from below decrementation
	}

	// Reduce size by one
	--size;
}


//------------------------------------------------------------------------------------
//	unlinkTailNode()
//	Description	-	Unlinks tail node from list, preserving lists structure minus the node.
//					Faster than general unlink function.
//					WARNING: Does NOT place node in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
LinkedListNode<T>* LinkedList<T>::getAndUnlinkTailNode( )
{
	LinkedListNode<T>*	ret_node_ptr = tail_ptr;

	// If there is more than 1 Node in List, we will need to do
	// some pointer rearranging.
	if ( size > 1 )
	{
		// If there is a previous Node, just make it point to the next
		// one.
		tail_ptr->prev->next = NULL;
		tail_ptr = tail_ptr->prev;
		tail_ptr->next = NULL;
	}
	else
	{
		tail_ptr = NULL;
		head_ptr = NULL;
		size = 1;
	}

	// Reduce size by one
	--size;
	return	ret_node_ptr;
}


//------------------------------------------------------------------------------------
//	removeNode()
//	Description	-	Removes node from list, preserving lists structure minus the node,
//					Places node in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeNode( LinkedListNode<T> *this_node )
{
	// First unlink the node
	unlinkNode( this_node );

	// Now that the node has no links, place it on the free list
	returnNodeToFreeList( this_node );
}


//------------------------------------------------------------------------------------
//	removeHeadNode()
//	Description	-	Removes the HEAD node from list, this is more convinient and faster
//					than the general removeNode() if list is used as a queue.
//					Places node in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeHeadNode( )
{
	// If 'head' is not the only item in list, clear next nodes previous ptr
	if ( head_ptr->next )
	{
		head_ptr = head_ptr->next;
		returnNodeToFreeList( head_ptr->prev );
		head_ptr->prev = NULL;

		// Reduce size by one
		--size;
	}
	// Otherwise, free the head node, and make both head and tail NULL
	else if ( head_ptr )
	{
		returnNodeToFreeList( head_ptr );
		tail_ptr = NULL;
		head_ptr = NULL;

		// Reduce size by one
		--size;
	}
}


//------------------------------------------------------------------------------------
//	removeTailNode()
//	Description	-	Removes the TAIL node from list, see removeHeadNode() for details
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeTailNode( )
{
	// If 'tail' is not the only item in list, clear prev nodes next ptr
	if ( tail_ptr->prev )
	{
		tail_ptr = tail_ptr->prev;
		returnNodeToFreeList( tail_ptr->next );
		tail_ptr->next = NULL;

		// Reduce size by one
		--size;
	}
	// Otherwise, free the head node, and make both head and tail NULL
	else if ( tail_ptr )
	{
		returnNodeToFreeList( tail_ptr );
		tail_ptr = NULL;
		head_ptr = NULL;

		// Reduce size by one
		--size;
	}
}


//------------------------------------------------------------------------------------
//	removeAllNodes()
//	Description	-	Removes all nodes from list, and places them in the free
//					list for future insertions.  Very fast.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeAllNodes( )
{
	// If there is more than 1 Node in List, we will need to do
	// some pointer rearranging.
	if ( size > 0 )
	{
		// Make tail next pointer point at the current available list head, and make
		// current head the head of free pool list.
		tail_ptr->next = head_ptr_of_free_pool;
		head_ptr_of_free_pool = head_ptr;
		size_of_free_pool += size;

		// Nullify tail and head pointers
		tail_ptr = NULL;
		head_ptr = NULL;

		// Size is now zero
		size = 0;
	}	
}


//------------------------------------------------------------------------------------
//	removeAllNodesAfter()
//	Description	-	Removes all nodes from list between the specified nodes.
//					WARNING: does no fault checking.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeAllNodesBetween( LinkedListNode<T> *this_node, LinkedListNode<T> *and_this_node )
{
	while ( this_node->next != and_this_node )
	{
		removeNode( this_node->next );
	}
}


//------------------------------------------------------------------------------------
//	removeAllNodesAfter()
//	Description	-	Removes all nodes from list after specified node, and places
//					them in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeAllNodesAfter( LinkedListNode<T> *this_node )
{
	// Make sure 'this_node' is not last node
	if ( this_node->next != NULL )
	{
		LinkedListNode<T>	*cur_node_ptr = this_node->next;

		// Decrease size by how ever many nodes are being removed
		while ( cur_node_ptr )
		{
			--size;
			++size_of_free_pool;
			cur_node_ptr = cur_node_ptr->next;
		}

		// Make tail next pointer point at the current available list head, and make
		// current first node to be removed the head of free pool list.
		tail_ptr->next = head_ptr_of_free_pool;
		head_ptr_of_free_pool = this_node->next;

		// Update tail pointer
		tail_ptr = this_node;
		tail_ptr->next = NULL;
	}	
}


//------------------------------------------------------------------------------------
//	removeAllNodesBefore()
//	Description	-	Removes all nodes from list before specified node, and places
//					them in the free list for future insertions.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::removeAllNodesBefore( LinkedListNode<T> *this_node )
{
	// Make sure 'this_node' is not head node
	if ( this_node->prev != NULL )
	{
		LinkedListNode<T>	*cur_node_ptr = this_node->prev;

		// Decrease size by how ever many nodes are being removed
		while ( cur_node_ptr )
		{
			--size;
			++size_of_free_pool;
			cur_node_ptr = cur_node_ptr->prev;
		}

		// Make previous nodes next pointer point at the current available list head, and make
		// current first node to be removed the head of free pool list.
		this_node->prev->next = head_ptr_of_free_pool;
		head_ptr_of_free_pool = head_ptr;

		// Update head pointer
		head_ptr = this_node;
		head_ptr->prev = NULL;
	}	
}


//------------------------------------------------------------------------------------
//	purgePreallocatedList()
//	Description	-	Allocates a new single block containing all nodes in list,
//					copies over current list information, then deletes all existing
//					memory.  Has a spike of memory, but reduces final memory print.
//					Should be used if list is not expected to change size anymore.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::purgeFreeList( )
{
	if ( size == 0 )
	{
		// Free any preallocated memory and return
		deleteMemory();
		size_of_free_pool = 0;
		memory_nodes_per_block = 0;
		return;
	}

	// First allocate a new block of memory the size of current list
	LinkedListNode<T>	*new_memory_block = new LinkedListNode<T> [this->size];
	LinkedListNode<T>	*current_node_ptr = this->head_ptr;
	unsigned int	i;

	// Now copy over list information for each node
	new_memory_block[0].prev = NULL;
	for ( i = 0; i < (this->size-1); i++ )
	{
		new_memory_block[i].next = &new_memory_block[i+1];
		new_memory_block[i+1].prev = &new_memory_block[i];
		new_memory_block[i].item = current_node_ptr->item;
		current_node_ptr = current_node_ptr->next;
	}
	new_memory_block[i].next = NULL;
	new_memory_block[i].item = current_node_ptr->item;

	// Free old memory
	deleteMemory();

	// Make head and tail point in correct places
	this->head_ptr = &new_memory_block[0];
	this->tail_ptr = &new_memory_block[i];

	// Re-initialize memory block information and pointers
	memory_block_count = 1;
	memory_nodes_per_block = this->size;
	memory_node_blocks = new LinkedListNode<T>* [1];
	memory_node_blocks[0] = new_memory_block;
	size_of_free_pool = 0;
}


//------------------------------------------------------------------------------------
//	deleteMemory()
//	Description	-	Deletes all current memory (destroys list)
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::deleteMemory()
{	
	// Memory allocated on the fly, need to delete each node individually
	if ( memory_nodes_per_block == 0 )
	{
		// Now travel through the current list and delete each node
		while ( head_ptr )
		{
			tail_ptr = head_ptr->next;
			delete	head_ptr;
			head_ptr = tail_ptr;
		}

		// Purge the free list
		head_ptr = head_ptr_of_free_pool;
		while ( head_ptr )
		{
			tail_ptr = head_ptr->next;
			delete	head_ptr;
			head_ptr = tail_ptr;
		}
	}
	// If there were memory blocks allocated, simply delete the blocks
	else
	{
		// Simply delete all memory blocks that were allocated
		for (unsigned int i = 0; i < memory_block_count; i++)
		{
			delete[] memory_node_blocks[i];
		}

		delete[] memory_node_blocks;
	}

	head_ptr = NULL;
	tail_ptr = NULL;
	head_ptr_of_free_pool = NULL;
}


//------------------------------------------------------------------------------------
//	convertToArray()
//	Description	-	Returns array of lists items, preserving order (WARNING: if 'item' 
//					is a pointer, array will use say memory space as linked list)
//------------------------------------------------------------------------------------
template <class T>
T*	LinkedList<T>::convertToArray( )
{
	LinkedListNode<T>	*current_node_ptr = this->head_ptr;
	T*					item_array = new T [this->size];

	for ( unsigned int i = 0; i < this->size; i++ )
	{
		item_array[i] = current_node_ptr->item;
		current_node_ptr = current_node_ptr->next;
	}

	return	item_array;
}


//------------------------------------------------------------------------------------
//	reverseList()
//	Description	-	Reverses order in which list is linked (tail becomes head)
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::reverseList( )
{
	LinkedListNode<T> *temp_node_ptr = head_ptr;
	LinkedListNode<T> *cur_node_ptr;

	head_ptr = tail_ptr;
	tail_ptr = temp_node_ptr;

	// Fix tail and head first
	tail_ptr->prev = tail_ptr->next;
	tail_ptr->next = NULL;
	head_ptr->next = head_ptr->prev;
	head_ptr->prev = NULL;

	// Need to go down entire list flipping pointers
	cur_node_ptr = head_ptr->next;
	while ( cur_node_ptr->next )
	{
		temp_node_ptr = cur_node_ptr->next;
		cur_node_ptr->next = cur_node_ptr->prev;
		cur_node_ptr->prev = temp_node_ptr;

		cur_node_ptr = cur_node_ptr->next;
	}
}


//------------------------------------------------------------------------------------
//	copyFromOtherListAfter()
//	Description	-	Copies provided lists nodes (must be same type) into this list after
//					specified node.  Other list remains unchanged.
//
//	WARNING: If lists items are pointers to objects, they will both be sharing those objects.
//
//	NOTE:	If this list does not use preallocated memory blocks, it will be converted 
//			to during this function call.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::copyFromOtherListAfter( LinkedListNode<T> *this_node, LinkedList<T> *other_list )
{
	if ( other_list->getSize() > 0 )
	{
		LinkedListNode<T>	*cur_node_ptr;

		// First purge the current list if using non-preallocated blocks
		if ( memory_nodes_per_block == 0 )
		{
			purgeFreeList();
		}

		// If new list is larger than preallocated list, might as well create an entire
		// new memory block.
		if ( size_of_free_pool < other_list->getSize() )
		{
			unsigned int i;
			allocateAdditionalMemoryBlock( other_list->getSize() );

			// Update size to be combination of this list and other list
			size = size + other_list->getSize();

			// Copy over the nodes info into the new memory block
			cur_node_ptr = other_list->getHeadPtr();
			memory_node_blocks[memory_block_count-1][0].prev = this_node;
			for ( i = 0; i < (other_list->getSize()-1); i++ )
			{
				memory_node_blocks[memory_block_count-1][i].item = cur_node_ptr->item;
				memory_node_blocks[memory_block_count-1][i].next = &memory_node_blocks[memory_block_count-1][i+1];
				memory_node_blocks[memory_block_count-1][i+1].prev = &memory_node_blocks[memory_block_count-1][i];
				cur_node_ptr = cur_node_ptr->next;
			}

			// Last node, special case
			memory_node_blocks[memory_block_count-1][i].item = cur_node_ptr->item;
			if ( this_node )
			{
				memory_node_blocks[memory_block_count-1][i].next = this_node->next;
				if ( this_node->next )
				{	// 'this_node' was not the tail node
					this_node->next->prev = &memory_node_blocks[memory_block_count-1][i];
				}
				else
				{	// 'this_node' was tail, but new lists tail is now the real tail
					tail_ptr = &memory_node_blocks[memory_block_count-1][i];
				}

				// Finally, connect 'this_node'
				this_node->next = &memory_node_blocks[memory_block_count-1][0];
			}
			else
			{
				memory_node_blocks[memory_block_count-1][i].next = NULL;
				head_ptr = &memory_node_blocks[memory_block_count-1][i];
				tail_ptr = &memory_node_blocks[memory_block_count-1][0];
			}
		}
		// Otherwise, simply insert one node at a time
		else
		{
			cur_node_ptr = other_list->getTailPtr();

			// If current list is empty, make 'this_node' pointer be head
			if ( size == 0 )
			{
				insertAtStart(cur_node_ptr->item);
				this_node = head_ptr;
				cur_node_ptr = cur_node_ptr->next;
			}

			while ( cur_node_ptr )
			{
				insertAfter( this_node, cur_node_ptr->item );
				cur_node_ptr = cur_node_ptr->prev;
			}
		}
	}
}


//------------------------------------------------------------------------------------
//	copyFromOtherListBefore()
//	Description	-	Copies provided lists nodes (must be same type) into this list after
//					specified node.  Other list remains unchanged.
//
//	WARNING: If lists items are pointers to objects, they will both be sharing those objects.
//
//	NOTE:	If this list does not use preallocated memory blocks, it will be converted 
//			to during this function call.
//------------------------------------------------------------------------------------
template <class T>
void	LinkedList<T>::copyFromOtherListBefore( LinkedListNode<T> *this_node, LinkedList<T> *other_list )
{
	if ( other_list->getSize() > 0 )
	{
		LinkedListNode<T>	*cur_node_ptr = other_list->getHeadPtr();

		// First purge the current list if using non-preallocated blocks
		if ( memory_nodes_per_block == 0 )
		{
			purgeFreeList();
		}

		// If new list is larger than preallocated list, might as well create an entire
		// new memory block.
		if ( size_of_free_pool < other_list->getSize() )
		{
			unsigned int i;
			allocateAdditionalMemoryBlock( other_list->getSize() );

			// Update size to be combination of this list and other list
			size = size + other_list->getSize();

			// Copy over the nodes info
			memory_node_blocks[memory_block_count-1][0].prev = this_node->prev;
			for ( i = 0; i < (other_list->getSize()-1); i++ )
			{
				memory_node_blocks[memory_block_count-1][i].item = cur_node_ptr->item;
				memory_node_blocks[memory_block_count-1][i].next = &memory_node_blocks[memory_block_count-1][i+1];
				memory_node_blocks[memory_block_count-1][i+1].prev = &memory_node_blocks[memory_block_count-1][i];
				cur_node_ptr = cur_node_ptr->next;
			}

			// Last node, special case
			memory_node_blocks[memory_block_count-1][i].item = cur_node_ptr->item;
			memory_node_blocks[memory_block_count-1][i].next = this_node;
			if ( this_node )
			{
				if ( this_node->prev )
				{	// 'this_node' was not the head node
					this_node->prev->next = &memory_node_blocks[memory_block_count-1][0];
				}
				else
				{	// 'this_node' was head, but new lists tail is now the real head
					head_ptr = &memory_node_blocks[memory_block_count-1][0];
				}

				// Finally, connect 'this_node'
				this_node->prev = &memory_node_blocks[memory_block_count-1][i];
			}
			else
			{
				head_ptr = &memory_node_blocks[memory_block_count-1][i];
				tail_ptr = &memory_node_blocks[memory_block_count-1][0];
			}
		}
		// Otherwise, simply insert one node at a time
		else
		{
			// If current list is empty, make 'this_node' pointer be head
			if ( size == 0 )
			{
				insertAtStart(cur_node_ptr->item);
				this_node = head_ptr;
				cur_node_ptr = cur_node_ptr->next;
			}

			while ( cur_node_ptr )
			{
				insertBefore( this_node, cur_node_ptr->item );
				cur_node_ptr = cur_node_ptr->next;
			}
		}
	}
}


//------------------------------------------------------------------------------------
//	checkListIntegrity()
//	Description	-	Tries to transverse the entire list based on size.  Returns TRUE
//					if can fully travel the list, FAIL otherwise.
//------------------------------------------------------------------------------------
template <class T>
bool	LinkedList<T>::checkListIntegrity( )
{
	LinkedListNode<T>	*cur_node_ptr = head_ptr;
	for ( unsigned int i = 0; i < (size-1); i++ )
	{
		if ( cur_node_ptr )
		{
			cur_node_ptr = cur_node_ptr->next;
		}
		else
		{
			return	false;
		}
	}

	return ( ( (cur_node_ptr == tail_ptr) && (cur_node_ptr->next == NULL) ) ? (true) : (false) );
}