加载中

手写数据结构·线性表07:无头结点单链表

无头结点单链表(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。
  • 链表持有结点所有权,未实现深拷贝,不要直接复制对象,避免默认浅拷贝导致重复释放。

跳转

下一个:带头结点单链表

上一个:顺序串

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/ad613403/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议