加载中

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

带头结点循环单链表(CircularSinglyListDummy)

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

    Node* head;   // dummy head
    int n;

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

public:
    CircularSinglyListDummy(){
        head=new Node;
        head->next=head;
        n=0;
    }

    ~CircularSinglyListDummy(){
        clear();
        delete head;
    }

    bool empty() const { return head->next==head; }
    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);
        q->next=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); }

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

工程细节

  • dummy 本身参与循环;空表为 head->next == head,而不是 nullptr。
  • 插删由 dummy 提供统一前驱。遍历与清空必须在再次遇到 dummy 时停止,不能把 dummy 当数据结点。
  • clear() 保留 dummy 并恢复自环,析构再释放 dummy。删除最后一个数据结点也应自然恢复该自环。
  • 本版没有尾指针,尾插仍为 O(n);dummy 中的 T data 要求 T 能默认构造。

跳转

下一个:尾指针循环单链表

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

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/5d19a077/

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