本文将使用Swift实现一个标准链表，在实现的过程中，遵守函数式编程的规则，无副作用，可以看到和C语言的实现还是有较大的差异。
预备知识
enum的各种用法- swift的基本的模式匹配（
pattern matching)
-- 代码里面case后面部分属于模式匹配，包含switch case,guard case,let case等extension的用法guardgeneric
遇到不懂的地方可以参阅官方文档学习即可
链表定义
首先来看一下Wikipedia对List的描述
Implementation of the list data structure may provide some of the following operations:
- a constructor for creating an empty list;
- an operation for testing whether or not a list is empty;
- an operation for prepending an entity to a list
- an operation for appending an entity to a list
- an operation for determining the first component (or the "head") of a list
- an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)
除了上述的要求之外，下面还将对数值型链表增加：判断是否存在元素，移除指定元素，在指定元素后插入等
测试先行
基于测试先行的想法，尝试先写测试用例，需要注意我们的函数没有副作用，意味着不会出现var类型变量，任何的修改都会产生新的对象。
let list0 = List<Int>()
assert(list0.isEmpty(), "list0 should be empty after constructure")
let list1 = list0.append(10)
assert(!list1.isEmpty(), "list1 should not be empty after append")
assert(list1.head == 10, "list1 should have a head valued 10")
assert(list1.tail.isEmpty(), "list1 should have an empty tail")
let list2 = [5,4,6,3,7,2].reduce(list1) {$0.append($1)}
assert(list2.head == 10, "list2 should have a head valued 10")
assert(list2.count == 7, "list2 should have 7 elements")
assert(list2.tail.count == 6, "the tail of list2 should have 6 elements")
let list3 = list2.remove(7).remove(10)
assert(list3.head == 5, "list3 should have a head valued 5")
assert(list3.count == 5, "list3 should have 5 elements")
let list4 = list3.insert(after:6, with: 11)
assert(list4.head == 5, "list4 should have a head valued 5")
assert(list4.count == 6, "list4 should have 6 elements")
assert(list4.contains(11), "list4 should contain 11")
如果按照TDD的做法我们应该先定义好类和函数体，这里根据Swift的特性选择了ENUM来实现这个链表，ENUM对于模式匹配有着天然的优势，在实现过程中，相信你也可以体会到。不过ENUM也有一些缺点，比如不能被继承等等。看定义：
enum List<Element> {
//表示是一个空链表，也表示是链表的结束
case E
//链表的节点
indirect case Node(Element,List<Element>)
init() {
self = .E
}
}
extension List {
//获取第一个元素
var head : Element? {
return nil
}
//获取去掉第一个元素之后的链表
var tail : List<Element> {
return .E
}
//在链表最后追加新元素
func append(_ elem : Element) -> List<Element> {
return self
}
var count : Int {
return 0
}
func isEmpty() -> Bool {
return true
}
}
//只有Equatable的对象才能执行按值删除，插入和判断是否存在
extension List where Element:Equatable {
func remove(_ elem : Element) -> List<Element> {
return self
}
func insert(after existElem : Element, with elem : Element ) -> List<Element> {
return self
}
func contains(_ elem : Element) -> Bool {
return false
}
}
上面的定义分成了三个部分，第一个部分是构造基本定义，构造的时候会创建一个空链表，其中indirect的含义表示会嵌套使用List，这个修饰符也可以放在enum的前面，含义相同。第二部分主要定义了空链表判断，元素数量，获取头尾，插入操作，对于head和tail，可以对应到Node定义上，Node的两个元素分别为head和tail。第三部分定义要求Element实现了Equatable的协议，只要可以判断是否包含特定元素，删除指定元素，以及在第一个指定元素后插入操作。
实现
好了，定义完成了，跑一下测试用例，bingo，第一条assert通过，第二条失败，因为第二条要求执行append之后isEmpty失败，所以接下来修改append和isEmpty这两个实现，实现如下：
//在链表最后追加新元素
func append(_ elem : Element) -> List<Element> {
guard case let .Node(head, tail) = self else { return .Node(elem,.E) }
return .Node(head, tail.append(elem))
}
func isEmpty() -> Bool {
if case .E = self { return true }
return false
}
首先isEmpty的实现非常简单，不再赘述，append的实现使用了guard和模式匹配保证接下来的操作是基于.Node(head, tail)的，否则的话就是空链表，我们创建并返回只有一个元素的链表.Node(elem, .E)，到这里应该就可以跑过刚才不过的用例了；对于非空链表，.Node(head, tail.append(elem))创建了一个新的链表，并把新的元素插入进去。这里如果没有看明白的话简单解释一下执行过程。
//假设我们有一个链表，其中有4个元素，分别为1，2，3，那么这个链表的表示应该为：
.Node(1, .Node(2, .Node(3, .E)))
//插入操作把append命令从head分别传递给下一个元素，几个步骤
.Node(1, .Node(2, .Node(3, .E))).append(4) ->
.Node(1, .Node(2, .Node(3, .E)).append(4)) ->
.Node(1, .Node(2, .Node(3, .E).append(4))) ->
.Node(1, .Node(2, .Node(3, .E.append(4)))) ->
//.E.append(4) 执行结果为 .Node(4, .E)
.Node(1, .Node(2, .Node(3, .Node(4, .E))))
上面的代码明白之后后序的代码就不会有什么问题了，回头来看开头的测试用例，block在head和tail了，下面实现这两个函数，前面也分析过了，其实List结构主要就是.Node(head, tail)。
//获取第一个元素
var head : Element? {
guard case let .Node(head, _) = self else { return nil }
return head
}
//获取去掉第一个元素之后的链表
var tail : List<Element> {
guard case let .Node(_, tail) = self else { return .E }
return tail
}
接下来是count的实现
var count : Int {
switch self {
case .E :
return 0
case .Node(_, let tail):
return tail.count + 1
}
}
现在跑一下测试用例会发现前面三组都通过了，第四组因为用到了remove还没有实现，所以失败了，思考一下移除一个元素的过程，很明显需要知道如何判断相等，所以这里要求Element实现了Equatable协议，不然编译的时候会发现==无法调用。如何移除元素之后再把前面的部分和后面的部分链接起来呢？
假设链表是.Node(1, .Node(2, .Node(3, .Node(4, .Node(5, .E)))))，现在要移除其中一个元素，分两种情况分析：
- 删除第一个元素：比较简单，直接返回tail即可
- 删除其它元素，和
append的思想是一样的，保留head，然后在tail部分执行删除
实现如下：
func remove(_ elem : Element) -> List<Element> {
switch self {
case .E :
return .E
case .Node(elem, let tail):
return tail
case let .Node(head, tail):
return .Node(head, tail.remove(elem))
}
}
以及contains的实现：
func contains(_ elem : Element) -> Bool {
guard case let .Node(head, tail) = self else {return false}
return head == elem || tail.contains(elem)
}
到这里除了insert的没有实现导致最后一组用例无法通过，留下一个insert给大家做课后作业。
后序计划
- Tree
- R-B Tree
