一个简单的双向循环链表(FIFO)
list.h#if !defined (LIST_H)
#define LIST_H
class DLink
{
public:
DLink (int id)
: _id (id)
{
_pPrev = this;
_pNext = this;
}
DLink *Prev () const { return _pPrev; }
DLink *Next () const { return _pNext; }
void SetPrev (DLink* pPrev) { _pPrev = pPrev; }
void SetNext (DLink* pNext) { _pNext = pNext; }
int Id () const { return _id; }
void Unlink();
private:
DLink *_pPrev;
DLink *_pNext;
int _id;
};
class List
{
public:
List (): _pHead (0) {}
~List ();
void Put ( int id );
int Get ();
DLink const * GetHead () const { return _pHead; }
protected:
DLink*_pHead;
};
#endiflist.cpp
#include "List.h"
#include <iostream>
#include <cassert>
void DLink::Unlink()
{
assert (_pNext != 0);
assert (_pPrev != 0);
_pNext->SetPrev (_pPrev);
_pPrev->SetNext (_pNext);
_pPrev = this;
_pNext = this;
}
void List::Put (int id)
{
DLink * pLink = new DLink (id);
if (_pHead == 0)
_pHead = pLink;
else
{
pLink->SetNext (_pHead);
pLink->SetPrev (_pHead->Prev ());
_pHead->Prev ()->SetNext (pLink);
_pHead->SetPrev (pLink);
_pHead = pLink;
}
}
int List::Get ()
{
assert (_pHead != 0);
DLink * pLink = _pHead->Prev ();
if (pLink == _pHead) // last one
_pHead = 0;
pLink->Unlink ();
int result = pLink->Id ();
delete pLink;
return result;
}
List::~List ()
{
// free the list
while ( _pHead != 0 )
{
DLink * pLink = _pHead->Prev ();
if (pLink == _pHead)
_pHead = 0;
pLink->Unlink (); // unlink pLink
delete pLink;
}
}
int main ()
{
List list;
list.Put (1);
list.Put (2);
list.Put (5);
list.Put (3);
std::cout << list.Get ();
return 0;
}
页:
[1]