链表
luckydrawbox · · 个人记录
使用前，请根据自己需要更改基本数据类型：
#define L_T int以上实现了一个以
操作
#define L_T int
struct List{
int tot,size;
int nc[N];
struct Line{
int head,next;
L_T val;
}a[N],e;
L_T INF;
List(){
tot=size=0;
for(int i=1;i<N;i++)
nc[i]=i;
e.head=e.next=0;
e.val=0;
INF=0x3f3f3f3f;
}
int build(int p,L_T val){
int np=nc[++tot];
size++;
a[np]=e;
a[np].head=p;
a[np].next=a[p].next;
a[a[p].next].head=np;
a[p].next=np;
a[np].val=val;
return np;
}
L_T del(int p){
size--;
nc[tot--]=p;
a[a[p].head].next=a[p].next;
a[a[p].next].head=a[p].head;
return a[p].val;
}
int insert(int p,L_T val){
if(p>size)
return 0;
int np=0;
for(int i=0;i<p;i++)
np=a[np].next;
return build(np,val);
}
int push_front(L_T val){
return build(0,val);
}
int push_back(L_T val){
return build(a[0].head,val);
}
L_T remove(int p){
if(p>size)
return INF;
int np=0;
for(int i=0;i<p;i++)
np=a[np].next;
return del(np);
}
L_T pop_front(){
if(!size)
return INF;
return del(a[0].next);
}
L_T pop_back(){
if(!size)
return INF;
return del(a[0].head);
}
L_T get_val(int p){
if(size<p)
return INF;
int np=0;
for(int i=0;i<p;i++)
np=a[np].next;
return a[np].val;
}
L_T get_front(){
if(!size)
return INF;
return a[a[0].next].val;
}
L_T get_back(){
if(!size)
return INF;
return a[a[0].head].val;
}
void write(int l,int r){
l=max(l,1);
r=min(r,size);
int p=0;
for(int i=0;i<r;i++){
p=a[p].next;
if(i>=l-1)
printf("%d ",a[p].val);
}
printf("\n");
}
};