存储结构

单链表

单链表 头指针 head 指向单链表的第一个结点, 空表的头指针为空.
也可以在单链表的第一个结点前附设一头结点, 头结点不存放数据, 或者也可存放表的长度等信息. 头结点的指针域指向第一个结点. 引入头结点的好处是, 链表第一个结点的操作和其它结点的操作变得一致了, 空表和非空表的操作也变得一致了. 因为头结点无需任何改变, 所以 head 的指向始终不变. 不过, 下面没有特别说明时, 总假定单链表不含头结点.
也可以附设单链表的尾指针, 指向最后一个结点.

struct Node:
	Type val
	Node *next
Node *head

单链表的查找

# 查找第 i 个结点, 1 ≤ i ≤ len.
# 如果 i 无效, 返回 NULL
get(i):
	if i < 1:
		return NULL
	p = head
	while p and --i:
		p = p->next
	return p

# 查找值为 val 的结点, 找不到则返回 NULL
# 另外如果链表含尾指针, 可以先在末尾插入一个值
# val 的结点作哨兵, 可省去每步循环对空指针的判断
find(val):
	p = head
	while p and p->val != val:
		p = p->next
	return p

单链表的增删 下面各个删除结点的算法, 亦可以利用返回值或引用参数返回被删除结点的值.

# 在 head 所指的链表前插入一个结点,
# 使用前保证 head 确实指向一链表,
# 即 head == NULL, 或指向某一结点
insert_head(val):
	head = new Node(val, head)

# 在指针 p 所指的结点后插入一值为 val 的结点
# 使用前保证 p 确实指向某一结点
# 注意此算法不能在头部插入结点
insert_after(p, val):
	p->next = new Node(val, p->next)

# 头插法: 反向输入各结点的值, 建立单链表
init_reverse():
	head = NULL
	while input(val):
		insert_head(val)

# 尾插法: 正向输入各结点的值, 建立单链表
init():
	head = tail = new Node(?, NULL) # 头结点
	while input(val):
		insert_after(tail, val)
		tail = tail->next
	remove_head()	# 若不需要头结点, 可以删除之

# 删除 head 所指的结点,
# 使用前保证 head 确实指向某一结点
remove_head():
	tmp = head
	head = head->next;
	delete tmp

# 删除指针 p 所指结点的下一结点,
# 使用前保证 p 确实指向某一结点.
# 注意此算法不能删除头部的结点
remove_after(p)
	tmp = p->next
	if tmp:
		p->next = tmp->next
		delete tmp

# 清空单链表
clear():
	while head:
		remove_head()

对单链表的结点作增, 删操作时, 一般要求已知该结点的前驱. 但是, 也可以这样删除一个非尾结点: 先将下一结点的内容拷贝到此结点, 再删除下一结点. 同理, 为了在非尾部插入一个结点, 可以先在此结点后插入一个此结点的拷贝, 再将要插入的数据拷贝到此结点. 这两种做法分别称为单链表的前插与前删操作, 与已知前驱结点的后插/后删算法相比, 它们各自多了一次数据的拷贝.

双链表

双链表 相比于单链表, 增加了一个指向前驱结点的指针. 操作与单链表相似. 在双链表中, 寻找前驱的时间由单链表的 O(n) 降到 O(1).

struct DualNode:
	Type val
	DualNode *prev
	DualNode *next
DualNode *head

双链表的增删 下面只列出其中两个算法. 注意指针回指前应当判断非空, 比如 p->next->prev = node 一句. insert_before, insert_head 的思路都类似.

# 在 p 所指的结点后插入一值为 val 的结点
# 使用前保证 p 确实指向某一结点
# 注意此算法不能在头部插入结点
insert_after(p, val):
	node = new Node(val, p, p->next)
	if p->next:
		p->next->prev = node
	p->next = node

# 删除指针 p 所指结点, 使用前保证 p 确实指向某一结点
remove(p):
	if p->next:
		p->next->prev = p->prev
	if p->prev:
		p->prev->next = p->next
	delete p

循环链表

循环 (单) 链表 的结点结构与单链表相同; 与单链表的区别在于, 最后一个指针不是空指针, 而是指向第一个结点 (或头结点, 如果存在), 整个链表形成一个环. 与单链表不同, 循环链表常设尾指针, 而不是头指针, 这是因为表非空时, tail->next 就是头指针. 空循环链表的 tail == NULL; 只有单个元素的循环链表, 其惟一结点的后继就是自己.

struct Node:
	Type val
	Node *next
Node *tail

# 在表尾插入一个新结点
append(val):
	if !tail:
		tail = new Node(val, NULL)
		tail->next = tail
	else:
		tail = tail->next = new Node(val, tail->next)

# 删除 p 所指结点的下一结点. 要求 p 确实指向一个结点.
remove_after(p):
	if tail->next == tail:
		tail = NULL
		delete tail
	else:
		tmp = p->next
		p->next = tmp->next
		if tmp == tail:
			tail = p
		delete tmp

# 遍历所有结点
traverse(visit):
	if tail:
		p = tail
		do:
			p = p->next
			visit(p)
		while p != tail

循环双链表 的结点结构与双链表相同; 与双链表的区别在于, 最后一个结点的 next 指针指向第一个结点, 而第一个结点的 prev 指针指向最后一个结点.

静态链表

静态链表 借助数组实现链表结构. 因为不涉及指针, 所以静态链表在用于一些大小固定的数据结构时有一定的方便之处. 后面会看到, 二叉树, 图... 凡是用到指针的数据结构, 统统可以做出它们的静态版本来. 动态分配的算法 new, delete 等需要自己实现. 一般数组的 0 号单元空出不用 (亦即, 0 号单元用作头结点), 这样就可以用 0 表示空指针. 假设静态链表可用单元最多为 N 个, 则数组大小须是 N+1.

struct StaticList:
	Type val[N+1]
	int next[N+1]

静态链表的空间分配算法 将未分配的空间链接成一单链表 (实为链栈), next[0] == 0 表示可用空间为空. 每次分配 (回收) 空间时从表头进行操作即可.

init():
	for i = 0 to N-1:
		next[i] = i+1
	next[N] = 0

# 分配 next[0] 所指的单元; 如果空间用尽, 返回 0
alloc(&p):
	p = next[0]
	next[0] = next[p] # 空间用尽时, 这里其实是自赋值

# 释放 p 所指的单元
free(p):
	next[p] = next[0]
	next[0] = p