链表

如何实现

动态申请存储空间，速度慢，代码量大。因此利用数组模拟链表。

数组模拟链表

如何模拟？

变量tot分配空间，v[tot]代表节点的值，需要一个l[tot]指向节点上一个元素，r[tot]指向节点下一个元素

有无头结点尾节点

head指向头结点，tail指向尾节点
head指向第一个节点，tail指向最后一个节点,不指向任何节点时为-1；

（以下讨论单链表）

向第一个节点前插入元素时的区别：向头结点后插入，等价于普通插入insert(p,v)向p后插入v
向第一个节点前插入，需要单写一个函数。

删除第一个节点时的区别：等价于普通删除。remove(p);
直接调整head指向r[head];

总结，指向一个空节点可以减少代码量。
有些时候可以不写空节点，额外写两个特判（插入到第一个节点，和删除第一个节点）

代码实现,有空节点

int v[N],l[N],r[n],tot,head,tail;
void init(){
    head = 0,tail = 1,tot = 2;//分配头结点尾节点空间，tot指向分配空间的指针
    l[head] = r[tail] = -1;//初始化，空链表
    r[head] = tail;
    l[tail] = head;
}
void insert(int p,int val){//在P后插入节点val
    int q = r[p];
    r[q] = l[p] = tot;
    l[tot] = p,r[tot] = q,v[tot] = val;
    tot++;
}

void remove(int p){//删除节点P
    r[l[p]] = r[p];
    l[r[p]] = l[p]; 
}