一个简单的双向循环链表(FIFO)

andalousie

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;
};

#endif

list.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;
}