《啊哈！算法》第 2 章第 5 节，模拟链表的 Swift 实现。
问题
为数组添加一个数，仍然得到按数值大小的排序，但不移动原数组的位置。
解决
用 data 存数组，用 right 记录对应 data 中的数值的下一个数所在的编号(0 编号表示结束)。为 data 尾部添加一个数后，修改 3 处 right 编号（1 新添加的数 2 此前的数 3 结束的数），完成插入。
var data = [0] //初始化链表，前置一个空项，不打印此项
var right: [Int] = []
//待操作的数组
data += [2, 3, 5, 8, 9, 10, 18, 26, 32]
//初始化数组的 right
var count = data.count
for i in 0...count {
if i != count {
right.append(i+1)
}else{
right.append(0)
}
}
//直接在数组 data 末尾添加一个数
data.append(6)
count += 1
//从链表头部开始遍历
var t = 1
while t != 0 {
//如果当前节点的下一个节点大于插入数，将数插到中间
if data[right[t]] > data[count-1] {
//新插入数的下一个节点编号等于当前节点的下一个节点编号
right[count-1] = right[t]
//当前节点的下一个节点编号等于新插入数的编号（最后一个）
right[t] = count - 1
//原数组最后一个节点的下一个节点编号为0（标记着数组结束）书中的 bug，缺了结束编号
right[count-1-1] = 0
break //完成插入，退出循环
}
t = right[t]
}
//遍历输出链表中的所有数
t = 1
while t != 0 {
print("\(data[t])")
t = right[t]
}
代码在 GitHub
