加载中

手写数据结构·线性表13:双向链表

双向链表(DoublyList)

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

    Node* head;
    Node* tail;
    int n;

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

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

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

    void push_front(const T& x){
        Node* q=new Node(x);
        q->next=head;

        if(head!=nullptr) head->prev=q;
        else tail=q;

        head=q;
        n++;
    }

    void push_back(const T& x){
        Node* q=new Node(x);
        q->prev=tail;

        if(tail!=nullptr) tail->next=q;
        else head=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* 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(q->prev!=nullptr) q->prev->next=q->next;
        else head=q->next;

        if(q->next!=nullptr) q->next->prev=q->prev;
        else tail=q->prev;

        delete q;
        n--;
        return true;
    }

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

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

工程细节

  • 非空时保持 head->prev == nullptr 与 tail->next == nullptr;每条前向边都要有对应后向边。
  • 中间插入检查四条边:新结点的 prev/next,左结点的 next,右结点的 prev。删除时同时接好两个方向。
  • 首尾插删同步维护 head、tail;删除唯一结点后两者都为空。
  • nodeAt() 从较近的一端走。已知结点时改边为 O(1),按位置定位后插删的整体时间仍为 O(n)。

跳转

下一个:双向循环链表

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

本文作者:flowwalker之码艺Blog

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

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