加载中

手写数据结构·线性表14:双向循环链表

双向循环链表(CircularDoublyList)

template<class T>
class CircularDoublyList {
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& x){
            data=x;
            prev=next=this;
        }
    };

    Node* head;   // tail = head->prev
    int n;

    Node* nodeAt(int pos) const{
        if(pos<n/2){
            Node* p=head;
            while(pos--) p=p->next;
            return p;
        }else{
            Node* p=head->prev;
            int steps=n-1-pos;
            while(steps--) p=p->prev;
            return p;
        }
    }

public:
    CircularDoublyList(){ head=nullptr; n=0; }
    ~CircularDoublyList(){ 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){
            head=q;
        }else{
            Node* tail=head->prev;

            q->prev=tail;
            q->next=head;
            tail->next=q;
            head->prev=q;

            head=q;
        }

        n++;
    }

    void push_back(const T& x){
        if(head==nullptr){
            push_front(x);
            return;
        }

        Node* tail=head->prev;
        Node* q=new Node(x);

        q->prev=tail;
        q->next=head;
        tail->next=q;
        head->prev=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* right=nodeAt(pos);
        Node* left=right->prev;
        Node* q=new Node(x);

        q->prev=left;
        q->next=right;
        left->next=q;
        right->prev=q;

        n++;
        return true;
    }

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

        Node* q=nodeAt(pos);

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

        q->prev->next=q->next;
        q->next->prev=q->prev;

        if(q==head) head=q->next;

        delete q;
        n--;
        return true;
    }

    T& at(int pos){
        if(pos<0 || pos>=n) throw out_of_range("CircularDoublyList::at");
        return nodeAt(pos)->data;
    }

    void clear(){
        while(!empty()) erase(0);
    }
};

工程细节

  • 非空时 head->prev 即尾结点,尾结点的 next 指向头;单结点的 prev、next 都指向自己。
  • 插删必须同步两方向的边。删除头结点后更新 head,删除唯一结点时单独恢复 nullptr。
  • 环中没有空指针终点。本版 clear() 反复删除位置 0,直到 empty(),总时间为 O(n)。
  • 定位可从首尾两端选择较短路线;没有实现深拷贝,不要直接复制对象,避免结点所有权重复。

跳转

下一个:链式栈

上一个:双向链表

本文作者:flowwalker之码艺Blog

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

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