无头结点单链表(SinglyList)
template<class T>
class SinglyList {
struct Node {
T data;
Node* next;
Node(const T& x,Node* p=nullptr){ data=x; next=p; }
};
Node* head;
int n;
Node* nodeAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
SinglyList(){ head=nullptr; n=0; }
~SinglyList(){ clear(); }
bool empty() const { return head==nullptr; }
int size() const { return n; }
void push_front(const T& x){
head=new Node(x,head);
n++;
}
void push_back(const T& x){
Node* q=new Node(x);
if(head==nullptr) head=q;
else{
Node* p=head;
while(p->next!=nullptr) p=p->next;
p->next=q;
}
n++;
}
bool insert(int pos,const T& x){
if(pos<0 || pos>n) return false;
if(pos==0){ push_front(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;
}else{
Node* p=nodeAt(pos-1);
Node* q=p->next;
p->next=q->next;
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("SinglyList::at");
return nodeAt(pos)->data;
}
void clear(){
while(head!=nullptr){
Node* q=head;
head=head->next;
delete q;
}
n=0;
}
};
工程细节
head 直接指向第一个数据结点,空表时为 nullptr。首结点没有前驱,位置 0 的插删需要单独处理。
- 删除时先保存待删结点,再接好后继,最后
delete;释放后不能继续读取该结点的 next。
- 仅有头指针,尾插需要遍历,时间为
O(n)。清空后恢复 head == nullptr 和 n == 0。
- 链表持有结点所有权,未实现深拷贝,不要直接复制对象,避免默认浅拷贝导致重复释放。
跳转
下一个:带头结点单链表
上一个:顺序串