加载中

手写数据结构·线性表08:带头结点单链表

带头结点单链表(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;   // dummy 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 能默认构造。

跳转

下一个:带尾指针单链表

上一个:无头结点单链表

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/3dde2992/

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