双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
C++完整个代码示例（代码在VS2005下测试可运行）
AL_ListDouble.h
/**
@(#)$Id: AL_ListDouble.h 26 2013-09-02 06:38:34Z xiaoting $
@brief Also called double-linked list doubly linked list is a list in which each data node in both two pointers that point to a
direct successor and direct precursors. Therefore, two-way linked list from any one of the node point, can easily access its
predecessor and successor nodes node. @Author $Author: xiaoting $
@Date $Date: 2013-09-02 14:38:34 +0800 (周一, 02 九月 2013) $
@Revision $Revision: 26 $
@URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListDouble.h $
@Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListDouble.h 26 2013-09-02 06:38:34Z xiaoting $
*/ #ifndef CXX_AL_LISTDOUBLE_H
#define CXX_AL_LISTDOUBLE_H #ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif ///////////////////////////////////////////////////////////////////////////
// AL_ListDouble
/////////////////////////////////////////////////////////////////////////// template<typename T>
class AL_ListDouble
{
public:
static const DWORD LISTDOUBLE_POSITION_INVALID = 0xffffffff;
/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
AL_ListDouble(); /**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
~AL_ListDouble(); /**
* Length
*
* @param VOID
* @return DWORD
* @note get the length of the list
* @attention
*/
DWORD Length() const; /**
* Find
*
* @param const T& tTemplate
* @return DWORD
* @note find the position of tTemplate
* @attention if not find, will be return 0xffffffff
*/
DWORD Find(const T& tTemplate ) const; /**
* IsElement
*
* @param const T& tTemplate
* @return BOOL
* @note the tTemplate is in the list?
* @attention
*/
BOOL IsElement(const T& tTemplate ) const; /**
* Insert
*
* @param DWORD dwIndex
* @param const T& tTemplate
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
BOOL Insert(DWORD dwIndex,const T& tTemplate ); /**
* InsertBegin
*
* @param const T& tTemplate
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
BOOL InsertBegin(const T& tTemplate ); /**
* InsertEnd
*
* @param const T& tTemplate
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
BOOL InsertEnd(const T& tTemplate ); /**
* Remove
*
* @param const T& tTemplate
* @return BOOL
* @note remove the tTemplate into the list
* @attention
*/
BOOL Remove(const T& tTemplate ); /**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note the list has data?
* @attention
*/
BOOL IsEmpty() const; /**
* Get
*
* @param
* @return BOOL
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
T Get(DWORD dwIndex) const; /**
* Set
*
* @param DWORD dwIndex
* @param const T& tTemplate
* @return BOOL
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
T Set(DWORD dwIndex, const T& tTemplate ); /**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
VOID Clear(); protected:
private:
/**
* GetNodeByIndex
*
* @param
* @return BOOL
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const; public:
protected:
private:
AL_Node<T>* m_pHeader;
}; ///////////////////////////////////////////////////////////////////////////
// AL_ListDouble
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T>
AL_ListDouble<T>::AL_ListDouble():
m_pHeader(NULL)
{
m_pHeader = new AL_Node<T>;
} /**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T>
AL_ListDouble<T>::~AL_ListDouble()
{
Clear();
//delete the header
delete m_pHeader;
m_pHeader = NULL;
} /**
* Length
*
* @param
* @return
* @note get the length of the list
* @attention
*/
template<typename T> DWORD
AL_ListDouble<T>::Length() const
{
if (TRUE == IsEmpty()) {
return 0;
}
AL_Node<T>* pMove = NULL;
DWORD dwCount = 1; pMove = m_pHeader->m_pNext;
while (NULL != pMove->m_pNext) {
dwCount ++;
pMove = pMove->m_pNext;
}
return dwCount;
} /**
* Find
*
* @param const T& tTemplate
* @return DWORD
* @note find the position of tTemplate
* @attention if not find, will be return 0xffffffff
*/
template<typename T> DWORD
AL_ListDouble<T>::Find(const T& tTemplate ) const
{
if (TRUE == IsEmpty()) {
return LISTDOUBLE_POSITION_INVALID;
} AL_Node<T>* pMove = NULL;
DWORD dwCount = 1; //loop the next data;
pMove = m_pHeader->m_pNext;
while (NULL != pMove->m_pNext) {
if (tTemplate == pMove->m_data) {
//find the data
return dwCount-1;
}
dwCount ++;
pMove = pMove->m_pNext;
} //the end
if (tTemplate == pMove->m_data) {
//find the data
return dwCount-1;
} return LISTDOUBLE_POSITION_INVALID;
} /**
* IsElement
*
* @param const T& tTemplate
* @return BOOL
* @note the tTemplate is in the list?
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::IsElement(const T& tTemplate ) const
{
if (LISTDOUBLE_POSITION_INVALID == Find(tTemplate )) {
return FALSE;
} return TRUE;
} /**
* Insert
*
* @param const T& tTemplate
* @param DWORD dwIndex
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::Insert(DWORD dwIndex, const T& tTemplate )
{
if (dwIndex > Length()) {
//can not insert to this position
return FALSE;
}
AL_Node<T>* pInsert = new AL_Node<T>;
pInsert->m_data = tTemplate; AL_Node<T>* pPre = NULL;
//get the previous Node
if (0x00 == dwIndex) {
pPre = m_pHeader;
}
else {
pPre = GetNodeByIndex(dwIndex - 1);
} if ((NULL == pPre)) {
//error
return FALSE;
}
if (Length() == dwIndex){
//end
pPre->m_pNext = pInsert;
pInsert->m_pPre = pPre;
}
else {
//among of the list
AL_Node<T>* pIndexNode = pPre->m_pNext;
if ((NULL == pIndexNode)) {
//error
return FALSE;
}
pInsert->m_pNext = pIndexNode;
pIndexNode->m_pPre = pInsert; pPre->m_pNext = pInsert;
pInsert->m_pPre = pPre;
}
return TRUE;
} /**
* InsertBegin
*
* @param const T& tTemplate
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::InsertBegin(const T& tTemplate )
{
return Insert(0, tTemplate);
} /**
* InsertEnd
*
* @param const T& tTemplate
* @return BOOL
* @note inset the tTemplate into the list at the position
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::InsertEnd(const T& tTemplate )
{
return Insert(Length(), tTemplate);
} /**
* Remove
*
* @param const T& tTemplate
* @return BOOL
* @note remove the tTemplate into the list
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::Remove(const T& tTemplate )
{
if (TRUE == IsEmpty()) {
return FALSE;
} DWORD dwPosition = Find(tTemplate);
if (LISTDOUBLE_POSITION_INVALID == dwPosition) {
//can not find the data
return FALSE;
} AL_Node<T>* pDelete = GetNodeByIndex(dwPosition);
if (NULL == pDelete) {
//error
return FALSE;
} AL_Node<T>* pPre = NULL;
//get the previous Node
if (0x00 == dwPosition) {
pPre = m_pHeader;
}
else {
pPre = pDelete->m_pPre;
} if (NULL == pPre) {
//error
return FALSE;
}
pPre->m_pNext = pDelete->m_pNext; AL_Node<T>* pNext = pDelete->m_pNext;
if (NULL != pNext) {
//among of the list
pNext->m_pPre = pPre;
} delete pDelete;
pDelete = NULL;
return TRUE;
} /**
* IsEmpty
*
* @param
* @return BOOL
* @note the list has data?
* @attention
*/
template<typename T> BOOL
AL_ListDouble<T>::IsEmpty() const
{
return (NULL == m_pHeader->m_pNext) ? TRUE:FALSE;
} /**
* Get
*
* @param
* @return T
* @note get the T at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> T
AL_ListDouble<T>::Get(DWORD dwIndex) const
{
T tTypeTemp;
memset(&tTypeTemp, 0x00, sizeof(T)); if (TRUE == IsEmpty()) {
//error
return tTypeTemp;
} if (Length()-1 < dwIndex) {
//error
return tTypeTemp;
} AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
if (NULL == pGet) {
//error
return tTypeTemp;
}
return pGet->m_data;
} /**
* Set
*
* @param DWORD dwIndex
* @param const T& tTemplate
* @return T
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
template<typename T> T
AL_ListDouble<T>::Set(DWORD dwIndex, const T& tTemplate )
{
T tTypeTemp;
memset(&tTypeTemp, 0x00, sizeof(T)); if (Length()-1 < dwIndex) {
//error
return tTypeTemp;
} AL_Node<T>* pSet = GetNodeByIndex(dwIndex);
if (NULL == pSet) {
//error
return tTypeTemp;
} tTypeTemp = pSet->m_data;
pSet->m_data = tTemplate;
return tTypeTemp;
} /**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
template<typename T> VOID
AL_ListDouble<T>::Clear()
{
if (TRUE == IsEmpty()) {
//No data,
return;
} AL_Node<T>* pDelete = NULL;
while(NULL != m_pHeader->m_pNext){
//get the node
pDelete = m_pHeader->m_pNext;
m_pHeader->m_pNext = pDelete->m_pNext;
delete pDelete;
pDelete = NULL;
}
} /**
* GetNodeByIndex
*
* @param
* @return BOOL
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> AL_Node<T>*
AL_ListDouble<T>::GetNodeByIndex(DWORD dwIndex) const
{
if (Length()-1 < dwIndex) {
//error
return NULL;
} AL_Node<T>* pMove = NULL;
DWORD dwCount = 1;
//loop the next data;
pMove = m_pHeader->m_pNext;
while (NULL != pMove->m_pNext) {
if (dwCount-1 == dwIndex) {
//get this place
return pMove;
}
dwCount ++;
pMove = pMove->m_pNext;
} //the end
return pMove; /*
//forward loop (only for test)
//get the end node
AL_Node<T>* pEnd = NULL;
AL_Node<T>* pMove = NULL;
//loop the next data;
pMove = m_pHeader->m_pNext;
while (NULL != pMove->m_pNext) {
pMove = pMove->m_pNext;
}
pEnd = pMove;
pMove = NULL; DWORD dwCount = Length();
//loop the next data;
pMove = pEnd;
while (m_pHeader != pMove->m_pPre) {
if (dwCount-1 == dwIndex) {
//get this place
return pMove;
}
dwCount --;
pMove = pMove->m_pPre;
} //the end
return pMove;
*/
} #endif // CXX_AL_LISTDOUBLE_H
/* EOF */
测试代码
#ifdef TEST_AL_LISTDOUBLE
AL_ListDouble<DWORD> cListDouble;
BOOL bEmpty = cListDouble.IsEmpty();
std::cout<<bEmpty<<std::endl; int array[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
for(int i=0;i<15;i++)
cListDouble.Insert(cListDouble.Length(), array[i]);
bEmpty = cListDouble.IsEmpty();
std::cout<<bEmpty<<std::endl; //test the interface
DWORD dwListSeqLen = cListDouble.Length();
std::cout<<dwListSeqLen<<std::endl; DWORD dwFind = cListDouble.Find(16);
std::cout<<dwFind<<std::endl;
dwFind = cListDouble.Find(12);
std::cout<<dwFind<<std::endl; BOOL bElement = cListDouble.IsElement(16);
std::cout<<bElement<<std::endl;
bElement = cListDouble.IsElement(14);
std::cout<<bElement<<std::endl; BOOL bInsert = cListDouble.Insert(0, 0);
std::cout<<bInsert<<std::endl;
bInsert = cListDouble.Insert(16, 16);
std::cout<<bInsert<<std::endl;
bInsert = cListDouble.Insert(16, 999);
std::cout<<bInsert<<std::endl; BOOL bRemove = cListDouble.Remove(9846354);
std::cout<<bRemove<<std::endl;
bRemove = cListDouble.Remove(999);
std::cout<<bRemove<<std::endl; bRemove = cListDouble.Remove(10);
std::cout<<bRemove<<std::endl; INT it = 0x00;
for (DWORD i=0; i<cListDouble.Length(); i++) {
it = cListDouble.Get(i);
std::cout<<it<<std::endl;
} DWORD dwSet = cListDouble.Set(16, 999);
std::cout<<dwSet<<std::endl;
dwSet = cListDouble.Set(0, 888);
std::cout<<dwSet<<std::endl;
dwSet = cListDouble.Set(11, 777);
std::cout<<dwSet<<std::endl; for (DWORD i=0; i<cListDouble.Length(); i++) {
it = cListDouble.Get(i);
std::cout<<it<<std::endl;
} cListDouble.Clear();
bEmpty = cListDouble.IsEmpty();
std::cout<<bEmpty<<std::endl;
dwListSeqLen = cListDouble.Length();
std::cout<<dwListSeqLen<<std::endl; bInsert = cListDouble.Insert(1, 999);
std::cout<<bInsert<<std::endl; bInsert = cListDouble.Insert(0, 666);
std::cout<<bInsert<<std::endl;
bRemove = cListDouble.Remove(666);
std::cout<<bRemove<<std::endl;
bEmpty = cListDouble.IsEmpty();
std::cout<<bEmpty<<std::endl;
dwListSeqLen = cListDouble.Length();
std::cout<<dwListSeqLen<<std::endl;
#endif