单链表
- 用数组模拟
- 代码1
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
//head代表头结点,指向链表起始位置
//eval代表第i个节点存的值
//nex代表第i个节点的指针,指向下一个节点
//idx代表链表存储到了哪个节点
int head,eval[N],nex[N],idx;
void init(){
head=-1;//初始化:head指向-1,-1可以理解为尾节点下标
idx=0;
}
void insert_to_head(int x){
eval[idx]=x;
nex[idx]=head;
head=idx;
idx++;
}
void insert(int k,int x){
eval[idx]=x;
nex[idx]=nex[k];
nex[k]=idx;
idx++;
}
void remove(int k){
nex[k]=nex[nex[k]];
}
int main(){
init();
int n;
cin>>n;
while(n--){
int k,x;
char op;
cin>>op;
if(op=='H'){
cin>>x;
insert_to_head(x);
}
else if(op=='D'){
cin>>k;
if(k==0) head=nex[head];
else remove(k-1);
}
else if(op=='I'){
cin>>k>>x;
insert(k-1,x);
}
}
for(int i=head;i!=-1;i=nex[i]) cout<<eval[i]<<" ";
return 0;
}
- 代码2
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
//head代表头结点,指向链表起始位置
//eval代表第i个节点存的值
//nex代表第i个节点的指针,指向下一个节点
//idx代表链表存储到了哪个节点
int eval[N],nex[N],idx;
void init(){
nex[0]=-1;//初始化,头结点指向-1
idx=1;//从1开始
}
void insert(int k,int x){
eval[idx]=x;
nex[idx]=nex[k];
nex[k]=idx;
idx++;
}
void remove(int k){
nex[k]=nex[nex[k]];
}
int main(){
init();
int n;
cin>>n;
while(n--){
int k,x;
char op;
cin>>op;
if(op=='H'){
cin>>x;
insert(0,x);
}
else if(op=='D'){
cin>>k;
remove(k);
}
else if(op=='I'){
cin>>k>>x;
insert(k,x);
}
}
for(int i=nex[0];i!=-1;i=nex[i]) cout<<eval[i]<<" ";
return 0;
}
双链表
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
int idx,eval[N],nex[N],pre[N];
void init(){
//0代表头,1代表尾,节点从2开始
nex[0]=1;
pre[1]=0;
idx=2;//因为从2开始,第k个节点其索引就是k+2-1,k-1
}
//节点k的右边插入一个数
void insert(int k,int x){
eval[idx]=x;
nex[idx]=nex[k];
pre[nex[k]]=idx;
nex[k]=idx;
pre[idx]=k;
idx++;
}
//删除节点k
void remove(int k){
nex[pre[k]]=nex[k];
pre[nex[k]]=pre[k];
}
int main(){
int n;
cin>>n;
init();
while(n--){
int k,x;
string op;
cin>>op;
if(op=="L"){
cin>>x;
insert(0,x);
}
else if(op=="R"){
cin>>x;
insert(pre[1],x);
}
else if(op=="D"){
cin>>k;
remove(k+1);
}
else if(op=="IL"){
cin>>k>>x;
insert(pre[k+1],x);
}
else if(op=="IR"){
cin>>k>>x;
insert(k+1,x);
}
}
for(int i=nex[0];i!=1;i=nex[i]) cout<<eval[i]<<" ";
return 0;
}