带尾指针单链表(SinglyListTail)
template<class T>
class SinglyListTail {
struct Node {
T data;
Node* next;
Node(const T& x,Node* p=nullptr){ data=x; next=p; }
};
Node* head;
Node* tail;
int n;
Node* nodeAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
SinglyListTail(){ head=tail=nullptr; n=0; }
~SinglyListTail(){ clear(); }
bool empty() const { return head==nullptr; }
int size() const { return n; }
void push_front(const T& x){
head=new Node(x,head);
if(tail==nullptr) tail=head;
n++;
}
void push_back(const T& x){
Node* q=new Node(x);
if(tail==nullptr) head=tail=q;
else{
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);
p->next=new Node(x,p->next);
n++;
return true;
}
bool erase(int pos){
if(pos<0 || pos>=n) return false;
if(pos==0){
Node* q=head;
head=head->next;
delete q;
n--;
if(n==0) tail=nullptr;
return true;
}
Node* p=nodeAt(pos-1);
Node* q=p->next;
p->next=q->next;
if(q==tail) tail=p;
delete q;
n--;
return true;
}
int find(const T& x) const{
Node* p=head;
int i=0;
while(p!=nullptr){
if(p->data==x) return i;
p=p->next; i++;
}
return -1;
}
T& at(int pos){
if(pos<0 || pos>=n) throw out_of_range("SinglyListTail::at");
return nodeAt(pos)->data;
}
void clear(){
while(head!=nullptr){
Node* q=head;
head=head->next;
delete q;
}
tail=nullptr;
n=0;
}
};
工程细节
- 同时维护首尾指针,尾插为
O(1);非空时 tail->next == nullptr。
- 空表头插、尾插都必须建立首尾指针;删除唯一结点后,
head 和 tail 必须同时为空。
- 删除尾结点后把
tail 改为其前驱。单链表找前驱仍需遍历,不能因为有尾指针就认为尾删也是 O(1)。
- 清空要释放整条链并将尾指针归零;不要直接复制对象,默认浅拷贝会重复释放结点。
跳转
下一个:无头结点循环单链表
上一个:带头结点单链表