/*
循環雙鏈表
*/

#include <iostream>
using namespace std;
struct Node
{
 int data;
 Node *next;
 Node *prior;
};

class CycleDLList
{
 private :
 Node *first;
 public:
 CycleDLList();
 void InsertNode(int data);
 void DeleteNode(int data);
 void PrintAll();
};

CycleDLList::CycleDLList()
{
 first->prior=first;
 first->next=first;
}
void CycleDLList::InsertNode(int data)
{
 Node *s=new Node();
 s->data=data;
 Node *p=first->next;
  while(p->next!=first)
  {
   p=p->next;
  }
  s->prior=p;
  s->next=p->next;
  p->next->prior=s;
  p->next=s;
}
void CycleDLList::DeleteNode(int data)
{
 Node *p=first->next;
 Node *q;
 while(p!=first)
 {
 if(p->data==data) break;
 q=p;
 p=p->next;
 }
 if (p!=first)
 {
 q->next=p->next;
 p->next->prior=q;
 delete p;
 }
}
void CycleDLList:: PrintAll()
{
Node *p=first->next;
Node *q=first->prior;
cout<<"p=p->next"<<endl;
while(p!=first)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
cout<<"q=q->prior"<<endl;
while(q!=first)
{
cout<<q->data<<" ";
q=q->prior;
}
}
int main()
{
CycleDLList *cd=new CycleDLList();
cd->InsertNode(5);
cd->InsertNode(4);
cd->InsertNode(3);
cd->InsertNode(2);
cd->PrintAll();
cd->DeleteNode(2);
cd->PrintAll();


}