带头结点单链表(SinglyListDummy)
template<class T>
class SinglyListDummy {
struct Node {
T data;
Node* next;
Node(){ next=nullptr; }
Node(const T& x,Node* p=nullptr){ data=x; next=p; }
};
Node* head;
int n;
Node* prevAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
SinglyListDummy(){
head=new Node;
n=0;
}
~SinglyListDummy(){
clear();
delete head;
}
bool empty() const { return head->next==nullptr; }
int size() const { return n; }
bool insert(int pos,const T& x){
if(pos<0 || pos>n) return false;
Node* p=prevAt(pos);
Node* q=new Node(x,p->next);
p->next=q;
n++;
return true;
}
bool erase(int pos){
if(pos<0 || pos>=n) return false;
Node* p=prevAt(pos);
Node* q=p->next;
p->next=q->next;
delete q;
n--;
return true;
}
void push_front(const T& x){ insert(0,x); }
void push_back(const T& x){ insert(n,x); }
int find(const T& x) const{
Node* p=head->next;
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("SinglyListDummy::at");
return prevAt(pos)->next->data;
}
void clear(){
Node* p=head->next;
while(p!=nullptr){
Node* q=p;
p=p->next;
delete q;
}
head->next=nullptr;
n=0;
}
};
工程细节
- 头指针与头结点不是一回事:
head 指向不存储有效元素的 dummy,首个数据结点是 head->next。
prevAt(pos) 从 dummy 开始走 pos 步,返回插删位置的前驱;位置 0 因而能统一处理。
- 插入先让新结点接到旧后继,再让前驱指向新结点。反过来改边可能丢失原链。
clear() 只释放数据结点,保留 dummy 并将其 next 置空;析构时再释放 dummy。当前 dummy 含 T data,要求 T 能默认构造。
跳转
下一个:带尾指针单链表
上一个:无头结点单链表