加载中

手写数据结构·线性表12:尾指针循环单链表

尾指针循环单链表(CircularSinglyListTail)

template<class T>
class CircularSinglyListTail {
    struct Node {
        T data;
        Node* next;
        Node(const T& x){ data=x; next=nullptr; }
    };

    Node* tail;   // 第一个结点 = tail->next
    int n;

    Node* nodeAt(int pos) const{
        Node* p=tail->next;
        while(pos--) p=p->next;
        return p;
    }

public:
    CircularSinglyListTail(){ tail=nullptr; n=0; }
    ~CircularSinglyListTail(){ clear(); }

    bool empty() const { return tail==nullptr; }
    int size() const { return n; }

    void push_front(const T& x){
        Node* q=new Node(x);

        if(tail==nullptr){
            q->next=q;
            tail=q;
        }else{
            q->next=tail->next;
            tail->next=q;
        }

        n++;
    }

    void push_back(const T& x){
        Node* q=new Node(x);

        if(tail==nullptr){
            q->next=q;
            tail=q;
        }else{
            q->next=tail->next;
            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);
        Node* q=new Node(x);
        q->next=p->next;
        p->next=q;
        n++;
        return true;
    }

    bool erase(int pos){
        if(pos<0 || pos>=n) return false;

        if(n==1){
            delete tail;
            tail=nullptr;
            n=0;
            return true;
        }

        if(pos==0){
            Node* q=tail->next;
            tail->next=q->next;
            delete q;
        }else{
            Node* p=nodeAt(pos-1);
            Node* q=p->next;
            p->next=q->next;
            if(q==tail) tail=p;
            delete q;
        }

        n--;
        return true;
    }

    void concat(CircularSinglyListTail& other){
        if(other.empty()) return;

        if(empty()){
            tail=other.tail;
            n=other.n;
        }else{
            Node* head1=tail->next;
            Node* head2=other.tail->next;

            tail->next=head2;
            other.tail->next=head1;

            tail=other.tail;
            n+=other.n;
        }

        other.tail=nullptr;
        other.n=0;
    }

    void clear(){
        if(tail==nullptr) return;

        Node* head=tail->next;
        tail->next=nullptr;   // 先断环

        while(head!=nullptr){
            Node* q=head;
            head=head->next;
            delete q;
        }

        tail=nullptr;
        n=0;
    }
};

工程细节

  • tail 指向末结点,首结点由 tail->next 获得;空表时不能解引用 tail。单结点时 tail->next == tail。
  • 头插保持 tail,尾插在接入新结点后更新 tail,两者均为 O(1)。删除尾结点仍要找前驱。
  • concat() 交换两环连接处并接管对方结点,随后把对方置空,避免两个对象共同释放同一批结点。不能与自身拼接,否则会破坏结点所有权和长度状态。
  • 清空先断开尾结点的 next,再按普通单链表释放;这时可以安全用 nullptr 作为终止条件。

跳转

下一个:双向链表

上一个:带头结点循环单链表

本文作者:flowwalker之码艺Blog

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

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