算法题中,一般使用静态链表,可以大幅提升速度。
结点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];