加载中

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

无头结点循环单链表(CircularSinglyList)

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

    Node* head;
    int n;

    Node* tail() const{
        if(head==nullptr) return nullptr;
        Node* p=head;
        while(p->next!=head) p=p->next;
        return p;
    }

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

public:
    CircularSinglyList(){ head=nullptr; n=0; }
    ~CircularSinglyList(){ clear(); }

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

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

        if(head==nullptr){
            q->next=q;
            head=q;
        }else{
            Node* t=tail();
            q->next=head;
            t->next=q;
            head=q;
        }

        n++;
    }

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

        if(head==nullptr){
            q->next=q;
            head=q;
        }else{
            Node* t=tail();
            q->next=head;
            t->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; }
        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 head;
            head=nullptr;
            n=0;
            return true;
        }

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

        n--;
        return true;
    }

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

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

        delete head;
        head=nullptr;
        n=0;
    }
};

工程细节

  • 非空时尾结点的 next 指向 head;只有一个结点时,head->next == head。
  • 遍历终止条件是回到起点,不能再用 p != nullptr。清空先删除其余结点,最后释放头结点。
  • 删除头结点时同步修改尾结点的 next;删除唯一结点时直接恢复空表。
  • 这里只有头指针,找尾结点为 O(n),头插和尾插都需要找尾。

跳转

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

上一个:带尾指针单链表

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/2a1e90e1/

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