双向链表
双向链表数据结构
具有前后指针的链表结构
题目链接
https://www.acwing.com/problem/content/829/
操作分析
注意： 插入操作默认是从k的后面插入
0 和 1 是左右边界，不是具体的值
0是左边界， 1 是右边界
以idx == 1 为结束条件
代码：
#include<iostream>
using namespace std
;
const int N
= 100010;
int idx
,e
[N
],L
[N
],R
[N
];
void init()
{
L
[1] = 0;
R
[0] = 1;
idx
= 2;
}
void connect(int a
,int b
)
{
R
[a
] = b
;
L
[b
] = a
;
}
void insert(int k
,int x
)
{
e
[idx
] = x
;
connect(idx
,R
[k
]);
connect(k
,idx
);
idx
++;
}
void del(int k
)
{
connect(L
[k
],R
[k
]);
}
int main()
{
int M
;
cin
>>M
;
init();
while(M
--)
{
string op
;
int k
,x
;
cin
>> op
;
if( op
== "L")
{
cin
>>x
;
insert(0,x
);
}else if(op
== "R")
{
cin
>> x
;
insert(L
[1],x
);
}else if(op
== "D")
{
cin
>> k
;
del(k
+1);
}else if(op
== "IL")
{
cin
>>k
>>x
;
insert(L
[k
+1],x
);
}else{
cin
>>k
>>x
;
insert(k
+1,x
);
}
}
for(int i
= R
[0]; i
!= 1; i
= R
[i
])cout
<<e
[i
]<<' ';
cout
<<endl
;
return 0;
}
