双链表
题目 双链表
思路分析
道理基本一样 再加上一个数组表示左指针就行了
e[i]、l[i]、r[i]
可以不定义head 直接将0号位置作为head 1号位置作为tail 反正是双向的
但是idx不能少 这个是核心
那么初始化其实就是
让0.r=1 1.l=0 开始就用了两个位置 所以res=2（可以位置为第三个）
void init(){
r[0]=1;
l[1]=0;
idx=2;
}
而插入就是
idx位置的右指向k的右
idx的左指向k
原本k的右的左要指向idx
k的右要指向idx
void add(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
其实还有一种在k位置左边插入的情况
但是可以在调用时 调用add(l[k],x)
在k左边元素的右边插入 就是在k左边插入
这样可以少写一个函数
删除也不难
右的左变左
左变右的左
void remove(int k){
r[l[k]]=r[k];|
l[r[k]]=l[k];
}
遍历输出就是
从第一个节点开始 不断右寻
void print(){
for(int i=r[0];i!=1;i=r[i])
cout<<e[i]<<" ";
}
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int e[N],l[N],r[N];
int idx;
void init()
{
//初始化 第一个点的右边是 1 第二个点的左边是 0
l[1]=0;
r[0]=1;
idx=2;//idx 此时已经用掉两个点了
}
//在第 K 个点右边插入一个 X
void add(int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
//在K的左边插入一个数 可以直接调用这个函数
//在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)
//删除第 k个 点
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
void print()
{
for(int i=r[0];i!=1;i=r[i])
cout<<e[i]<<" ";
}
int main()
{
int M;
cin>>M;
init();
while(M--)
{
string op;
cin>>op;
if(op=="L")
{//0和1代表头和尾 最左边插入只要在指向0的数的左边插入就可以了
//也就是可以直接在0的右边插入
int x;
cin>>x;
add(0, x);
}
else if(op=="R")
{//最右边插入 只要在指向1的那个点的右边插入
int x;
cin>>x;
add(l[1],x);
}
else if(op=="D")
{
int k;
cin>>k;
remove(k+1);//remove（k+1）这样头结点和尾结点就永远不会被删掉了
}
else if(op=="IL")
{
int k,x;
cin>>k>>x;
add(l[k+1],x);
}
else if(op=="IR")
{
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
print();
return 0;
}
💬 评论