【算法基础篇】双链表数组实现（算法竞赛常用）

常见问题

常见问题见上一篇单链表文章

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;
int m;


void init()
&#123;
    r[0] = 1, l[1] = 0;
    idx = 2; // 用掉两个结点 
&#125;
//在第 K 个点右边插入一个 X 
void add(int k, int x)
&#123;
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx ++;
&#125;
// 删掉第k个数
void del(int k)
&#123;
    r[l[k]] = r[k];
    l[r[k]] = l[k];
&#125;

int main()
&#123;
    cin >> m;
    init();

    while (m -- )
    &#123;
        string op;
        int x, k;
        cin >> op; 
        if(op == "L") //表示在链表的最左端插入数  x
        &#123;
            cin >> x;
            add(0, x);
        &#125;
        else if(op == "R") // 在链表的最右端插入数 x
        &#123;
            cin >> x;
           add(l[1], x);
        &#125;
        else if(op == "D") // 将第 k 个插入的数删除
        &#123;
            cin >> k;
            del(k + 1);
        &#125;
        else if(op == "IL") // 表示在第 k 个插入的数左侧插入一个数
        &#123;
            cin >> k >> x;
            add(l[k + 1],  x);  // 相当于在 第k - 1 的右侧插入
        &#125;
        else // 表示在第 k 个插入的数右侧插入一个数
        &#123;
            cin >> k >> x;
            add(k + 1, x);// 因为已经用掉左右两个点 idx=2 所以在第k-1结点的左边插入 应该是此时idx = k+1
        &#125;
    &#125;

    //输出结果
    for (int i = r[0]; i != 1; i = r[i] ) cout << e[i] << " ";
    cout << endl;
    return 0;
&#125;