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

andalousie

list.h

1. #if !defined (LIST_H)
   
2. #define LIST_H
   
3. 
   
4. class DLink
   
5. {
   
6. public:
   
7.         DLink (int id)
   
8.                 : _id (id)
   
9.         {
   
10.                 _pPrev = this;
    
11.                 _pNext = this;
    
12.         }
    
13.         DLink *  Prev () const { return _pPrev; }
    
14.         DLink *  Next () const { return _pNext; }
    
15.         void    SetPrev (DLink* pPrev) { _pPrev = pPrev; }
    
16.         void    SetNext (DLink* pNext) { _pNext = pNext; }
    
17.         int     Id () const { return _id; }
    
18.         void    Unlink();
    
19. private:
    
20.         DLink *  _pPrev;
    
21.         DLink *  _pNext;
    
22.         int     _id;
    
23. };
    
24. 
    
25. class List
    
26. {
    
27. public:
    
28.         List (): _pHead (0) {}
    
29.         ~List ();
    
30.         void    Put ( int id );
    
31.         int     Get ();
    
32.         DLink const * GetHead () const { return _pHead; }
    
33. protected:
    
34.         DLink*  _pHead;
    
35. };
    
36. 
    
37. #endif

复制代码

list.cpp

1. #include "List.h"
   
2. #include <iostream>
   
3. #include <cassert>
   
4. 
   
5. void DLink::Unlink()
   
6. {
   
7.   assert (_pNext != 0);
   
8.   assert (_pPrev != 0);
   
9.   _pNext->SetPrev (_pPrev);
   
10.   _pPrev->SetNext (_pNext);
    
11.   _pPrev = this;
    
12.   _pNext = this;
    
13. }
    
14. 
    
15. void List::Put (int id)
    
16. {
    
17.   DLink * pLink = new DLink (id);
    
18.   if (_pHead == 0)
    
19.     _pHead = pLink;
    
20.   else
    
21.   {
    
22.     pLink->SetNext (_pHead);
    
23.     pLink->SetPrev (_pHead->Prev ());
    
24.     _pHead->Prev ()->SetNext (pLink);
    
25.     _pHead->SetPrev (pLink);
    
26.     _pHead = pLink;
    
27.   }
    
28. }
    
29. 
    
30. int List::Get ()
    
31. {
    
32.   assert (_pHead != 0);
    
33.   DLink * pLink = _pHead->Prev ();
    
34.   if (pLink == _pHead) // last one
    
35.     _pHead = 0;
    
36.   pLink->Unlink ();
    
37.   int result = pLink->Id ();
    
38.   delete pLink;
    
39.   return result;
    
40. }
    
41. 
    
42. List::~List ()
    
43. {
    
44.   // free the list
    
45.   while ( _pHead != 0 )
    
46.   {
    
47.     DLink * pLink = _pHead->Prev ();
    
48.     if (pLink == _pHead)
    
49.       _pHead = 0;
    
50.     pLink->Unlink (); // unlink pLink
    
51.     delete pLink;
    
52.   }
    
53. }
    
54. 
    
55. int main ()
    
56. {
    
57.   List list;
    
58.   list.Put (1);
    
59.   list.Put (2);
    
60.   list.Put (5);
    
61.   list.Put (3);
    
62.   std::cout << list.Get ();
    
63.   return 0;
    
64. }

复制代码