배열 시 뮬 레이 션 링크 의 실현

#pragma once
/**
 *     ,           ,                 。         
 *    /     
 *
 *           
 * ：     ，      。
 * ：        ELEMENT  ，          。           
 *          ，    ELEMENT，          。                  
 *      ，     (          )
 *ELEMENT       ：typedef CListWithArray<int,1000>::ELEMENT CListWithArray_t;
 *    CListWithArray_t  
 
 *      
 * bool Add(llist_t* e); //               。
 * llist_t* Erase();	 //          ,        
 *  next      ，         ，         
**/
namespace list_with_array
{
	template<typename llist_t, int llist_size=100>
	class CListWithArray
	{
	//variable
	public:			
		struct ELEMENT
		{
			llist_t element;
			ELEMENT* pPre;
			ELEMENT* pNext;
		};

	private:
		ELEMENT elementData[llist_size];//    

		ELEMENT freeElement;			//       
		ELEMENT useElement;             //         

	//function
	public:
		CListWithArray();

		bool Add(const llist_t e);
		ELEMENT* Erase(ELEMENT *p)
		{
			return ReleaseElement(p);
		}
		ELEMENT* GetListHead()
		{
			return useElement.pNext;		
		}
		
		/**
		 *       
		 **/
		int GetSumUseElement()
		{
			int sum=0;
			ELEMENT* p;
			
			for(p=useElement.pNext; p!=NULL; p=p->pNext)
			{
				++sum;
			}

			return sum;
		}

		int GetSumFreeElement()
		{
			int sum=0;
			ELEMENT* p;
			
			for(p=freeElement.pNext; p!=NULL; p=p->pNext)
			{
				++sum;
			}

			return sum;		
		}
		
	private:
		/**
		 *     ,     
		**/
		void InitList();
		ELEMENT* MallocElement();
		ELEMENT* ReleaseElement(ELEMENT *p);

		/**
		 *            
		**/
		void AddNodeToList(ELEMENT* const pNode, ELEMENT* const pDesList)
		{
			//       
			pNode->pNext = pDesList->pNext;
			pNode->pPre  = pDesList;

			//         ,         
			if( NULL!=pDesList->pNext )
			{
				pDesList->pNext->pPre = pNode;
			}

			pDesList->pNext = pNode;
		}
	};

	/**
	 *         
	 **/
	template <typename llist_t, int llist_size>
	CListWithArray<llist_t, llist_size>::CListWithArray()
	{
		InitList();
	}

	template <typename llist_t, int llist_size>
	void CListWithArray<llist_t, llist_size>::InitList()
	{
		//     
		for(int i=0; i<llist_size-1; ++i)
		{
			elementData[i].pNext = &elementData[i+1];
		}

		elementData[llist_size-1].pNext = NULL;

		useElement.pNext = NULL;
		freeElement.pNext = &elementData[0];
	}

	template <typename llist_t, int llist_size>
	typename CListWithArray<llist_t, llist_size>::ELEMENT* CListWithArray<llist_t, llist_size>::MallocElement()
	{
		//         
		if( NULL==freeElement.pNext )
		{
			return NULL;
		}

		// Free    ,  
		ELEMENT* p = freeElement.pNext;
		freeElement.pNext = freeElement.pNext->pNext;

		//     
		p->pPre = NULL;
		p->pNext = NULL;

		AddNodeToList(p, &useElement);

		return p;
	}

	template <typename llist_t, int llist_size>
	typename CListWithArray<llist_t, llist_size>::ELEMENT* CListWithArray<llist_t, llist_size>::ReleaseElement( ELEMENT *p)
	{
		ELEMENT *pResult = p->pNext;
		// Use    
		p->pPre->pNext = p->pNext;
		//        
		if( NULL!=p->pNext )
		{
			p->pNext->pPre = p->pPre;	
		}
		
		//    
		p->pPre = NULL;
		p->pNext = NULL;

		AddNodeToList(p, &freeElement);

		return pResult;
	}

	template <typename llist_t, int llist_size>
	bool CListWithArray<llist_t, llist_size>::Add(const llist_t e)
	{
		//  Free          
		ELEMENT *p = MallocElement();

		if( NULL==p )
		{
			return false;
		}
		else
		{
			p->element = e;
			return true;
		}
	}
};

/*
     
 #include "CListWithArray.h"

using namespace std;
using namespace list_with_array;

CListWithArray<int,1000> listTest;
typedef CListWithArray<int,1000>::ELEMENT CListWithArray_t;


void cout_listinfo()
{
	cout<<"sum use:"<<listTest.GetSumUseElement()<<endl;
	cout<<"sum free:"<<listTest.GetSumFreeElement()<<endl;
	cout<<"-------------------"<<endl;
}

void test_del_1()
{
	CListWithArray_t *p=listTest.GetListHead();
	while( NULL!=p )
	{
		if( ((p->element)&0x1) == 0 )   //    
		{
			p = listTest.Erase(p);		//  ，  p        ，   p->pNext;
			continue;
		}

		p=p->pNext;
	}	
}

void test_del_2()
{
	CListWithArray_t *p=listTest.GetListHead();
	while( NULL!=p )
	{
		if( 1000==p->element || 2000==p->element )
		{
			p = listTest.Erase(p);
				continue;
		}

		p=p->pNext;
	}
}

void test_add_1()
{
	for(int i=0; i<1100; ++i)
	{
		listTest.Add(i);
	}	
}

void test_add_2()
{
	for(int i=0; i<3; ++i)
	{
		listTest.Add(i*1000);
	}	
}

int _tmain(int argc, _TCHAR* argv[])
{

	cout_listinfo();		//      

	test_add_1();			//    
	cout_listinfo();


	test_del_1();			//    
	cout_listinfo();

	test_add_2();			//      ，0，1000，2000
	cout_listinfo();

	test_del_2();			//  1000，2000
	cout_listinfo();

	return 0;
}

*/