链表

说明

你的团队决定用双向链表来表示时刻表中的每条火车路线。 火车路线沿途的每个车站都由链表中的一个节点表示。

你不需要操心各个车站的到达和出发时间。 每个车站只用一个数字表示就好。

路线可以延长，在路线的开头或末尾增加车站。 也可以从路线的开头或末尾移除车站来缩短。

有时某个车站会关闭，这时即使它不在路线的开头或末尾，也需要把它从路线中移除。

路线的大小不是以火车行驶的距离来衡量，而是以它停靠的车站数量来衡量。

有状态的数据结构

在 Lean 这样的函数式语言中，大多数值在设计上都是不可变的。 这意味着更新通常是通过产生一个新值来完成的。 旧值和新值同时存在，都可以被引用和使用。

不过，很多情况下我们确实需要，甚至必须使用_有状态_的值。 有状态的值通过变更来更新，它是_替换_旧值，而不是创建一个新值。 变更之后，只有更新后的值仍然可以访问。

注意，变更可能会破坏语言的一些保证。 纯函数对于同一组输入必须始终返回相同的结果；但如果某个输入会随时间变化，那么即使以相同的实参调用，函数也可能返回不同的结果。 同样，如果一个函数除了返回结果之外还会产生外部变化，或者会从其形参以外的来源读取内容，那么对同一个函数的两次调用可能会得到不同、有时甚至无法预测的结果。

为了处理这类有状态的行为，Lean 和其他函数式语言一样，要求把有副作用的函数包装在一种特殊的结构里，以区别于纯函数。 这种结构叫做_单子_。

需要注意的是，虽然每个有状态的值都存在于某个有副作用的单子之中，但并非每个单子都表示可变状态。 值得一提的“纯”单子的例子有Option、Except和Id。

在这个练习中，你将定义一个叫做LinkedList的有状态数据结构。 这种数据结构的实例通过变更来更新。

为此，所有函数都包装在ST单子之中。 在这个单子里，可变状态是唯一的副作用，而且可变引用无法逃逸。 想了解更多信息，可以查阅参考。