//链表--链式存储的线性表 
//存信息和下一个节点位置，数据域和指针域合起来叫节点
//带头（哨兵位）下标为0 
//单向，双向，循环链表
//实现 单
//俩足够大数组 
// elem，数据域 
// next ，指针域
//下标
//head，头结点下标；id新节点位置  h=0，id=0；
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10; 
//定义，初始化
int e[N],ne[N],h,id;
int mp[N]; 
//    头插，，兵 ，   ，下一节点 
//             （x）
void push_front(int x)
{
id++;
e[id]=x;
mp[x]=id; 
ne[id]=ne[h];
ne[h]=id;
//mp[x]=id;
} 
// 遍历,打印 
void print() 
{
//    for(int i=1;i!=)
for(int i=ne[h];i;i=ne[i])
{
cout<<e[i]<<" ";
}
}
//按值查找下标 
int find (int x)
{

//    for(int i=ne[h];i;i=ne[i])
//    {
//        if(e[i]==x) return i; 
//    }return 0;

//按值查找方法二，重新标记数组哈希 cout<<mp[x];
// 太大开不了，不能存重复 
return mp[x];
} 

//任意   存储  位置（实际存的下标的位置) 之 后 插入元素
//   p
//   x     y
//      z
void insert(int p,int x)
{
id++;
e[id]=x;
mp[x]=id;
ne[id]=ne[p];
ne[p]=id;
} 
// 删除任意（存储位置p）之后位置
//    p
//    x    y     z      
void erase (int p) 
{
if(ne[p])
{

ne[p]=ne[ne[p]];
mp[e[ne[p]]]=0;

}
}

int main()
{
for(int i=0;i<6;i++)
push_front(i);// 5 4 3 2 1 0 
print();
cout<<endl<<find (5);//6
cout<<endl<<find (0);//1
cout<<endl;
insert(1 ,88);
print();
cout<<endl;
insert(6,99);
print();
cout<<endl;
insert(3 ,33);
print();
cout<<endl;
insert(7 ,100);
print();
cout<<endl;
insert(8 ,666);
print();
cout<<endl;
erase(4);
print();
cout<<endl;
erase(3);//第三个已经删没了


print();
cout<<endl;
erase(4);
print();
return 0;
}