Aha! Algorithms - Linked List Si

《啊哈！算法》第 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