加载中

手写数据结构·线性表09:带尾指针单链表

带尾指针单链表(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)。
  • 清空要释放整条链并将尾指针归零;不要直接复制对象,默认浅拷贝会重复释放结点。

跳转

下一个:无头结点循环单链表

上一个:带头结点单链表

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/4ad91904/

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