数据结构之双向链表(数组模拟)

const int MAXN = 100005;
int value[MAXN];    //保存链表数据
int pre[MAXN];      //指向上一个元素的指针
int ne[MAXN];       //指向下一个元素的指针
int index;          //当前元素保存位置
//初始化
void init() {
          
   
    //第0个表示head指针指向链表开始位置
    //第1个表示tail指针指向链表尾部位置
    //初始化链表未空,即首尾中间无元素
    pre[1] = 0;   //tail指向head
    ne[0] = 1;   //head指向tail
    index = 2;
}
//在最左侧插入一个数；
void insert_left(int x) {
          
   
    ne[index] = ne[0];
    pre[index] = 0;
    pre[ne[0]] = index;
    ne[0] = index;
    value[index++] = x;
}
// 在最右侧插入一个数；
void insert_right(int x) {
          
   
    ne[index] = 1;
    pre[index] = pre[1];
    ne[pre[1]] = index;
    pre[1] = index;
    value[index++] = x;
}
//将第k个插入的数删除；
void remove(int k) {
          
   
    ne[pre[k+1]] = ne[k+1];
    pre[ne[k+1]] = pre[k+1];
}
//在第k个插入的数左侧插入一个数；
void insert_left(int k, int x) {
          
   
    ne[index] = k + 1;
    pre[index] = pre[k+1];
    ne[pre[k+1]] = index;
    pre[k+1] = index;
    value[index++] = x;
}
//在第k个插入的数右侧插入一个数
void insert_right(int k, int x) {
          
   
    pre[index] = k + 1;
    ne[index] = ne[k+1];
    pre[ne[k+1]] = index;
    ne[k+1] = index;
    value[index++] = x;
}
//正向输出(head->tail)
void print_left() {
          
   
    for(int i = ne[0]; i != 1; i = ne[i]) {
          
   
        cout << value[i] <<  ;
    }
    cout << endl;
}
//反向输出
void print_right() {
          
   
    for(int i = pre[1]; i != 0; i = pre[i]) {
          
   
        cout << value[i] <<  ;
    }
    cout << endl;
}