模板 - 数据结构 - 链表/LinkedList

一个只供删除的双向链表，为了简单不再引入head节点，而且也不进行next的套娃操作。空间使用略微多了一些，但是无伤大雅。

struct LinkedList {

    static const int MAXN = 100000;

    int n, prev[MAXN + 5], next[MAXN + 5];

    void Init(int _n) {

        n = _n;

        for(int i = 1; i <= n; ++i) {

            prev[i] = i - 1;

            next[i] = i + 1;

        }

        prev[1] = -1;

        next[n] = -1;

    }

    void Remove(int x) {

        prev[next[x]] = prev[x];

        next[prev[x]] = next[x];

    }

};

正常的链表是单向链表，删除操作是删除当前节点的下一个节点，没有必要。全部写双向的。b事多还可以写个垃圾回收。

struct LinkedList {

    static const int MAXN = 100000;

    int n, prev[MAXN + 5], next[MAXN + 5];

    static const int head = 0, tail = MAXN + 1;

    void Init() {

        n = 0;

        prev[head] = -1;

        next[head] = tail;

        prev[tail] = head;

        next[tail] = -1;

    }

    int Insert(int x) {

        ++n;

        prev[next[x]] = n;

        next[n] = next[x];

        prev[n] = x;

        next[x] = n;

        return n;

    }

    int Append() {

        return Insert(prev[tail]);

    }

    void Remove(int x) {

        prev[next[x]] = prev[x];

        next[prev[x]] = next[x];

    }

};

并查集实现的伪链表。用并查集实现的伪链表虽然删除不是O(1)的，但是不会怕访问到被删除的节点。

struct PrevLinkedList {

    int n;

    bool vis[100005];

    int prev[100005];

    void Init(int _n) {

        n = _n;

        for(int i = 1; i <= n; ++i) {

            vis[i] = 0;

            prev[i] = i - 1;

        }

    }

    int Prev(int x) {

        int r = prev[x];

        while(vis[r])

            r = prev[r];

        int t;

        while(prev[x] != r) {

            t = prev[x];

            prev[x] = r;

            x = t;

        }

        return r;

    }

    void Remove(int x) {

        vis[x] = 1;

    }

};

要使用next的话就再搞另一个伪链表就可以了。和只使用lower_bound,upper_bound,prev,next的平衡树相比，伪链表的速度卓越，缺点是不能插入，也不能维护第k大/前k项和。

巴特西

模板 - 数据结构 - 链表/LinkedList

最新文章

热门文章