你会链表吗？我觉得我会。

链表支持 $O(1)$ 删除、插入，$O(n)$ 查找。数组支持 $O(n)$ 删除插入，$O(1)$ 查找。

用 $pre_i,nxt_i$ 维护每个数的前驱后继即可，其中 $nxt_0,pre_0$ 分别是链表的头和尾。

队列安排 勉强算链表板子。

struct LIST{
    int pre[N],nxt[N];
    void init(){ pre[0]=nxt[0]=0; }
    void ins_l(int x,int y){ nxt[y]=x,pre[y]=pre[x],nxt[pre[x]]=y,pre[x]=y; }
    void ins_r(int x,int y){ pre[y]=x,nxt[y]=nxt[x],pre[nxt[x]]=y,nxt[x]=y; }
    int exist(int x){ return nxt[pre[x]]==x&&pre[nxt[x]]==x; }
    void del(int x){ if(exist(x)) pre[nxt[x]]=pre[x],nxt[pre[x]]=nxt[x]; }
    void print(){ for(int i=nxt[0];i;i=nxt[i]) printf("%d ", i); puts(""); }
}L;

还有块状链表，不太熟。