[编程笔记]-Double-Linked_Lists双链表

前言

鉴于双链表和单链表基本上一毛一样，所以不会重新再写一遍链表基本操作，详见“[编程笔记]-Single-Linked_Lists单链表”。

概念

就是双向链表，每个节点既指向后一个元素，又指向前一个元素。

代码

对没错就是这么懒( •̀ ω •́ )✧

class Double_linked_lists{
    public:
        int head,tail,cnt;
        int e[N],ne[N],la[N];
        void init(int n,int h=0){
            head=h;tail=n+1;
            ne[head]=tail;
        }
        void add_next(int k,int x){
            ++cnt;
            e[cnt]=x;
            ne[cnt]=ne[k];
            ne[k]=cnt;
            la[cnt]=k;
            la[ne[cnt]]=cnt;
        }
        void add_last(int k,int x){//其实这里可以直接转成add_next()，但为了方便学习还是手打了一遍。
            ++cnt;
            e[cnt]=x;
            la[cnt]=la[k];
            la[k]=cnt;
            ne[la[cnt]]=cnt;
            ne[cnt]=k;
        }
        void del(int k){//删除编号为k的节点。
            ne[la[k]]=ne[k];
            la[ne[k]]=la[k];
        }
        vector<int> get(){
            vector<int> vec;
            for(int i=ne[head];i!=tail;i=ne[i]){
                vec.push_back(e[i]);
            }
            return vec;
        }
}dll;

完结撒花o(￣︶￣)o