#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N];
int l[N],r[N];
int idx;
void init()
{
r[0]=1,l[1]=0;
idx=2;
}
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
void add_to_right(int k,int x)
{
e[idx]=x;
l[idx]=k,r[idx]=r[k];
l[r[k]]=idx,r[k]=idx;
idx++;
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
char s[10];
cin>>s;
if(s[0]=='L')
{
int x;
cin>>x;
add_to_right(0,x);
}
else if(s[0]=='R')
{
int x;
cin>>x;
add_to_right(l[1],x);
}
else if(s[0]=='D')
{
int k;
cin>>k;
remove(k+1);
}
else if(s[1]=='L')
{
int k,x;
cin>>k>>x;
add_to_right(l[k+1],x);
}
else
{
int k,x;
cin>>k>>x;
add_to_right(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
{
cout<<e[i]<<" ";
}
puts("");
return 0;
}
双链表，其实和单链表还是有一些相似之处，但是双链表更加精巧，尤其体现在有两个端点，单链表只有一个head头节点，双链表有左端点和右端点两个端点
设置了三个函数，第一个函数是初始化函数，把0作为左端点，1作为右端点，刚开始的时候，刚开始的时候0的右边是1，1的左边是0，链表除了两个端点，没有其他的元素，索引下标idx从2开始计数
第二个函数是删除函数，详细的来说是，删除第k个插入的数，改变指针即可，比较巧妙，原来的元素的右边的元素的左指针指向原来元素左边的元素，相当于跳过了原来的元素，原来元素左边元素的右指针指向原来元素右边的元素，假设是这样子的：本来是 a ,b ,c，b表示插入的第k个元素，让c的左指针指向a，让a的右指针指向c，就可以实现删除中间的元素b的效果
第三个函数是插入一个元素，详细的说是，在第k个插入的元素右边插入一个元素，其实比较简单，就是插入的元素需要断开第k个插入的元素和该元素右边元素的链接，然后重新建立一个链接，假设把第k个插入的元素记作a，a右边的元素记作b，我们需要让插入的元素的左指针指向a，右指针指向b，让a的右指针指向插入的元素，b的左指针指向插入的元素
实现五种操作
第一种操作是在最左端插入一个元素，其实就是在0的右边插入一个元素，直接调用第三个函数即可
第二种操作是在最右端插入一个元素，其实就是在右端点的左边一个元素的右边插入一个元素，所以把第一个参数设置为右端点的左边一个元素即可
第三种操作是删除第k个插入的元素，直接调用函数即可，注意索引下标从2开始计数，所以第k个插入的元素的索引下标是k+1（表现在函数里面 ），假设索引下标从0开始计数，第k个插入的元素的索引下标是k-1,假设索引下标从1开始计数，第k个插入的元素的索引下标是k
第四种操作是在第k个插入的元素左边插入一个数字，其实就是在第k个插入的元素左边一个元素右边插入一个元素，所以把调用函数的第一个参数设置为第k个插入元素的左边一个元素即可，还是需要注意索引下标
第五种操作是在第k 个插入的元素右边插入一个数字，直接调用函数即可，注意索引下标
输出的时候注意，从左端点的右边开始循环，一直到右端点截止，每一次找右指针指向的元素输出
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N];
int l[N],r[N];//左指针和右指针
int idx;//索引下标
void init()//初始化
{
r[0]=1,l[1]=0;
idx=2;
}
void remove(int k)//删除
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
void add_to_right(int k,int x)//在第k个插入的元素右边插入一个元素
{
e[idx]=x;
l[idx]=k,r[idx]=r[k];
l[r[k]]=idx,r[k]=idx;
idx++;
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
char s[10];
cin>>s;
if(s[0]=='L')//最左端插入一个元素
{
int x;
cin>>x;
add_to_right(0,x);
}
else if(s[0]=='R')//最右端插入一个元素
{
int x;
cin>>x;
add_to_right(l[1],x);
}
else if(s[0]=='D')//删除第k 个插入的元素
{
int k;
cin>>k;
remove(k+1);
}
else if(s[1]=='L')//在第k个插入的元素左边插入一个元素
{
int k,x;
cin>>k>>x;
add_to_right(l[k+1],x);
}
else//在第k个元素的右边插入一个元素
{
int k,x;
cin>>k>>x;
add_to_right(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])//输出双链表
{
cout<<e[i]<<" ";
}
puts("");
return 0;
}
自己又独立敲了一遍，WA了一次，瞪眼法调试了出来，成功ac，有两个细节需要注意，先把WA的代码和AC的代码依次放在下面
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N];
int idx;
void init()
{
r[0]=1,l[1]=0;
idx=2;
}
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
void add_to_right(int k,int x)
{
e[idx]=x;
l[idx]=l[k];
r[idx]=r[k];
r[l[k]]=idx;
l[r[k]]=idx;
idx++;
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
char s[10];
cin>>s;
if(s[0]=='L')
{
int x;
cin>>x;
add_to_right(0,x);
}
else if(s[0]=='R')
{
int x;
cin>>x;
add_to_right(l[1],x);
}
else if(s[0]=='D')
{
int k;
cin>>k;
remove(k+1);
}
else if(s[1]=='L')
{
int k,x;
cin>>k>>x;
add_to_right(l[k+1],x);
}
else
{
int k,x;
cin>>k>>x;
add_to_right(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
{
cout<<e[i]<<" ";
}
puts("");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N];
int idx;
void init()
{
r[0]=1,l[1]=0;
idx=2;
}
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
void add_to_right(int k,int x)
{
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx;
idx++;
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
char s[10];
cin>>s;
if(s[0]=='L')
{
int x;
cin>>x;
add_to_right(0,x);
}
else if(s[0]=='R')
{
int x;
cin>>x;
add_to_right(l[1],x);
}
else if(s[0]=='D')
{
int k;
cin>>k;
remove(k+1);
}
else if(s[1]=='L')
{
int k,x;
cin>>k>>x;
add_to_right(l[k+1],x);
}
else
{
int k,x;
cin>>k>>x;
add_to_right(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
{
cout<<e[i]<<" ";
}
puts("");
return 0;
}
第一个是因为没有注意其实只有两个元素，不要扯到k元素左边的元素，这里是指往k元素右边插入一个元素的时候（k元素是第k个插入的元素的简称），不要牵扯到k元素左边的元素，是需要在k元素和k元素右边元素之间插入一个新的元素
第二个是注意操作的顺序，如果经过我们的操作，变量发生了我们不想要的改变，那就会出错，这个非常难发现，所以一定要小心，还是上面提到的函数，WA的那份代码，好吧，其实是完全没有经过思考，应该是k元素的右边是新插入的元素，但是我们不可以先写
r[k]=idx;
l[r[k]]=idx;
这样子写，r[k]发生了改变，和我们的愿意有所区别，代码就是这样，有一些区别结果就是天差地别
所以我们要先写下面一行，再写上面一行