双向链表(DoublyList)
template<class T>
class DoublyList {
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& x){ data=x; prev=next=nullptr; }
};
Node* head;
Node* tail;
int n;
Node* nodeAt(int pos) const{
if(pos<n/2){
Node* p=head;
while(pos--) p=p->next;
return p;
}else{
Node* p=tail;
int steps=n-1-pos;
while(steps--) p=p->prev;
return p;
}
}
public:
DoublyList(){ head=tail=nullptr; n=0; }
~DoublyList(){ clear(); }
bool empty() const { return n==0; }
int size() const { return n; }
void push_front(const T& x){
Node* q=new Node(x);
q->next=head;
if(head!=nullptr) head->prev=q;
else tail=q;
head=q;
n++;
}
void push_back(const T& x){
Node* q=new Node(x);
q->prev=tail;
if(tail!=nullptr) tail->next=q;
else head=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* 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(q->prev!=nullptr) q->prev->next=q->next;
else head=q->next;
if(q->next!=nullptr) q->next->prev=q->prev;
else tail=q->prev;
delete q;
n--;
return true;
}
T& at(int pos){
if(pos<0 || pos>=n) throw out_of_range("DoublyList::at");
return nodeAt(pos)->data;
}
void clear(){
while(head!=nullptr){
Node* q=head;
head=head->next;
delete q;
}
tail=nullptr;
n=0;
}
};
工程细节
- 非空时保持
head->prev == nullptr 与 tail->next == nullptr;每条前向边都要有对应后向边。
- 中间插入检查四条边:新结点的
prev/next,左结点的 next,右结点的 prev。删除时同时接好两个方向。
- 首尾插删同步维护
head、tail;删除唯一结点后两者都为空。
nodeAt() 从较近的一端走。已知结点时改边为 O(1),按位置定位后插删的整体时间仍为 O(n)。
跳转
下一个:双向循环链表
上一个:尾指针循环单链表