无头结点循环单链表(CircularSinglyList)
template<class T>
class CircularSinglyList {
struct Node {
T data;
Node* next;
Node(const T& x){ data=x; next=nullptr; }
};
Node* head;
int n;
Node* tail() const{
if(head==nullptr) return nullptr;
Node* p=head;
while(p->next!=head) p=p->next;
return p;
}
Node* nodeAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
CircularSinglyList(){ head=nullptr; n=0; }
~CircularSinglyList(){ clear(); }
bool empty() const { return head==nullptr; }
int size() const { return n; }
void push_front(const T& x){
Node* q=new Node(x);
if(head==nullptr){
q->next=q;
head=q;
}else{
Node* t=tail();
q->next=head;
t->next=q;
head=q;
}
n++;
}
void push_back(const T& x){
Node* q=new Node(x);
if(head==nullptr){
q->next=q;
head=q;
}else{
Node* t=tail();
q->next=head;
t->next=q;
}
n++;
}
bool insert(int pos,const T& x){
if(pos<0 || pos>n) return false;
if(pos==0){ push_front(x); return true; }
if(pos==n){ push_back(x); return true; }
Node* p=nodeAt(pos-1);
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;
if(n==1){
delete head;
head=nullptr;
n=0;
return true;
}
if(pos==0){
Node* t=tail();
Node* q=head;
head=head->next;
t->next=head;
delete q;
}else{
Node* p=nodeAt(pos-1);
Node* q=p->next;
p->next=q->next;
delete q;
}
n--;
return true;
}
void clear(){
if(head==nullptr) return;
Node* p=head->next;
while(p!=head){
Node* q=p;
p=p->next;
delete q;
}
delete head;
head=nullptr;
n=0;
}
};
工程细节
- 非空时尾结点的
next 指向 head;只有一个结点时,head->next == head。
- 遍历终止条件是回到起点,不能再用
p != nullptr。清空先删除其余结点,最后释放头结点。
- 删除头结点时同步修改尾结点的
next;删除唯一结点时直接恢复空表。
- 这里只有头指针,找尾结点为
O(n),头插和尾插都需要找尾。
跳转
下一个:带头结点循环单链表
上一个:带尾指针单链表