带头结点循环单链表(CircularSinglyListDummy)
template<class T>
class CircularSinglyListDummy {
struct Node {
T data;
Node* next;
Node(){ next=nullptr; }
Node(const T& x){ data=x; next=nullptr; }
};
Node* head;
int n;
Node* prevAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
CircularSinglyListDummy(){
head=new Node;
head->next=head;
n=0;
}
~CircularSinglyListDummy(){
clear();
delete head;
}
bool empty() const { return head->next==head; }
int size() const { return n; }
bool insert(int pos,const T& x){
if(pos<0 || pos>n) return false;
Node* p=prevAt(pos);
Node* q=new Node(x);
q->next=p->next;
p->next=q;
n++;
return true;
}
bool erase(int pos){
if(pos<0 || pos>=n) return false;
Node* p=prevAt(pos);
Node* q=p->next;
p->next=q->next;
delete q;
n--;
return true;
}
void push_front(const T& x){ insert(0,x); }
void push_back(const T& x){ insert(n,x); }
void clear(){
Node* p=head->next;
while(p!=head){
Node* q=p;
p=p->next;
delete q;
}
head->next=head;
n=0;
}
};
工程细节
- dummy 本身参与循环;空表为
head->next == head,而不是 nullptr。
- 插删由 dummy 提供统一前驱。遍历与清空必须在再次遇到 dummy 时停止,不能把 dummy 当数据结点。
clear() 保留 dummy 并恢复自环,析构再释放 dummy。删除最后一个数据结点也应自然恢复该自环。
- 本版没有尾指针,尾插仍为
O(n);dummy 中的 T data 要求 T 能默认构造。
跳转
下一个:尾指针循环单链表
上一个:无头结点循环单链表