尾指针循环单链表(CircularSinglyListTail)
template<class T>
class CircularSinglyListTail {
struct Node {
T data;
Node* next;
Node(const T& x){ data=x; next=nullptr; }
};
Node* tail;
int n;
Node* nodeAt(int pos) const{
Node* p=tail->next;
while(pos--) p=p->next;
return p;
}
public:
CircularSinglyListTail(){ tail=nullptr; n=0; }
~CircularSinglyListTail(){ clear(); }
bool empty() const { return tail==nullptr; }
int size() const { return n; }
void push_front(const T& x){
Node* q=new Node(x);
if(tail==nullptr){
q->next=q;
tail=q;
}else{
q->next=tail->next;
tail->next=q;
}
n++;
}
void push_back(const T& x){
Node* q=new Node(x);
if(tail==nullptr){
q->next=q;
tail=q;
}else{
q->next=tail->next;
tail->next=q;
tail=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 tail;
tail=nullptr;
n=0;
return true;
}
if(pos==0){
Node* q=tail->next;
tail->next=q->next;
delete q;
}else{
Node* p=nodeAt(pos-1);
Node* q=p->next;
p->next=q->next;
if(q==tail) tail=p;
delete q;
}
n--;
return true;
}
void concat(CircularSinglyListTail& other){
if(other.empty()) return;
if(empty()){
tail=other.tail;
n=other.n;
}else{
Node* head1=tail->next;
Node* head2=other.tail->next;
tail->next=head2;
other.tail->next=head1;
tail=other.tail;
n+=other.n;
}
other.tail=nullptr;
other.n=0;
}
void clear(){
if(tail==nullptr) return;
Node* head=tail->next;
tail->next=nullptr;
while(head!=nullptr){
Node* q=head;
head=head->next;
delete q;
}
tail=nullptr;
n=0;
}
};
工程细节
tail 指向末结点,首结点由 tail->next 获得;空表时不能解引用 tail。单结点时 tail->next == tail。
- 头插保持
tail,尾插在接入新结点后更新 tail,两者均为 O(1)。删除尾结点仍要找前驱。
concat() 交换两环连接处并接管对方结点,随后把对方置空,避免两个对象共同释放同一批结点。不能与自身拼接,否则会破坏结点所有权和长度状态。
- 清空先断开尾结点的
next,再按普通单链表释放;这时可以安全用 nullptr 作为终止条件。
跳转
下一个:双向链表
上一个:带头结点循环单链表