单链表

算法题中,一般使用静态链表,可以大幅提升速度。

结点i的值为value[i]next指针为next[i]d表示数组已用位的下一位;

默认0号位为首结点,不存储任何实际值,-1表示空指针;

int value[n], next[n], d = 1;

next[0] = -1;

插入

在节点x的后面插入值为a的结点:

value[d] = a;
next[d] = next[x];
next[x] = d++;

删除

删除节点x后面的一个结点:

next[x] = next[next[x]];

注解:

(1)单链表有首结点好处是,在表首部进行操作时,与在表中部进行操作的代码一致。

(2)无首结点的单链表如下:

结点i的值为value[i],next指针为next[i]d表示数组已用位的下一位,head表示首指针,-1表示空指针;

int value[n], next[n], d = 0, head = -1;

无首结点的单链表在表首部进行操作时,与在表中部进行操作的代码不一致;

在表首插入值为a的结点:

value[d] = a;
next[d] = head;
head = d++;

删除表首的一个结点:

head = next[head];