双向循环链表(CircularDoublyList)
template<class T>
class CircularDoublyList {
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& x){
data=x;
prev=next=this;
}
};
Node* head;
int n;
Node* nodeAt(int pos) const{
if(pos<n/2){
Node* p=head;
while(pos--) p=p->next;
return p;
}else{
Node* p=head->prev;
int steps=n-1-pos;
while(steps--) p=p->prev;
return p;
}
}
public:
CircularDoublyList(){ head=nullptr; n=0; }
~CircularDoublyList(){ 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){
head=q;
}else{
Node* tail=head->prev;
q->prev=tail;
q->next=head;
tail->next=q;
head->prev=q;
head=q;
}
n++;
}
void push_back(const T& x){
if(head==nullptr){
push_front(x);
return;
}
Node* tail=head->prev;
Node* q=new Node(x);
q->prev=tail;
q->next=head;
tail->next=q;
head->prev=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* right=nodeAt(pos);
Node* left=right->prev;
Node* q=new Node(x);
q->prev=left;
q->next=right;
left->next=q;
right->prev=q;
n++;
return true;
}
bool erase(int pos){
if(pos<0 || pos>=n) return false;
Node* q=nodeAt(pos);
if(n==1){
delete q;
head=nullptr;
n=0;
return true;
}
q->prev->next=q->next;
q->next->prev=q->prev;
if(q==head) head=q->next;
delete q;
n--;
return true;
}
T& at(int pos){
if(pos<0 || pos>=n) throw out_of_range("CircularDoublyList::at");
return nodeAt(pos)->data;
}
void clear(){
while(!empty()) erase(0);
}
};
工程细节
- 非空时
head->prev 即尾结点,尾结点的 next 指向头;单结点的 prev、next 都指向自己。
- 插删必须同步两方向的边。删除头结点后更新
head,删除唯一结点时单独恢复 nullptr。
- 环中没有空指针终点。本版
clear() 反复删除位置 0,直到 empty(),总时间为 O(n)。
- 定位可从首尾两端选择较短路线;没有实现深拷贝,不要直接复制对象,避免结点所有权重复。
跳转
下一个:链式栈
上一个:双向链表