题目描述

实现一个双链表，支持五种操作，分别是头插、尾插、删除第k元素、k左插入、k右插入；

样例

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

算法1

使用数组模拟双链表

使用数组进行模拟，跟单链表的区别主要是会有两个指针分别指向头与尾，会增加较多操作；

时间复杂度 O(n)

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5+10;
int e[N], le[N], re[N];         //e[]模拟链表节点的值，le[]模拟左指针，re[]模拟右指针；
int head, tail, idx;            //head为头指针，tail为尾指针，idx为第几个插入的元素；

void init(){
    head = -1;
    tail = -1;
    idx = 0;
}                               //初始化；

void addToLorR(int x, bool isLeft){
    e[++idx] = x;
    if(isLeft){
        re[idx] = head;
        le[idx] = -1;
        if(head != -1)
            le[head] = idx;
        head = idx;
        if(tail == -1) tail = idx;          //判断是否空表，为空的话要把尾指针也指向新插入的节点；
    }else{
        le[idx] = tail;
        re[idx] = -1;
        if(tail != -1)
            re[tail] = idx;
        tail = idx;
        if(head == -1) head = idx;          //同样，右边插入也要将头指针指向新节点；
    }
}

void deleK(int k){
    if(le[k] != -1) re[le[k]] = re[k];
    else head = re[k];
    if(re[k] != -1) le[re[k]] = le[k];
    else tail = le[k];
}                                           //删除节点前先判断是否为头节点或者尾节点；

void addToK(int k, int x, bool isLeft){
    if(isLeft){
        if(le[k] == -1)                     //判断一下插入位置是否在最左侧，如果是，调用头插函数；
            addToLorR(x, isLeft);
        else{
            e[++idx] = x;
            le[idx] = le[k];
            re[le[idx]] = idx;
            re[idx] = k;
            le[k] = idx;
        }                                   //双链表插入模拟，只要注意不断链即可；
    }else{
        if(re[k] == -1)                     //同上；
            addToLorR(x, isLeft);
        else{
            e[++idx] = x;
            re[idx] = re[k];
            le[re[idx]] = idx;
            le[idx] = k;
            re[k] = idx;
        }
    }
}

int main()
{
    int m;
    cin>>m;
    init();                                 //别忘了初始化；
    char type;
    int k, x;
    bool isL;
    while(m--)
    {
        cin>>type;
        switch(type){           //switch只接受基本类型，int,short int,long,int,char,enum(其实也是int)；
            case 'L':
                cin>>x;
                addToLorR(x, true);
                break;
            case 'R':
                cin>>x;
                addToLorR(x, false);
                break;
            case 'D':
                cin>>k;
                deleK(k);
                break;
            case 'I':
                cin>>type>>k>>x;
                isL = (type == 'L') ? true : false;
                addToK(k, x, isL);
                break;
            default:
                break;                      //也可以将某一种情况写成default;
        }
    }
    while(head != -1){
        cout<<e[head]<<' ';
        head = re[head];
    }
    return 0;
}