本文將使用Swift實現(xiàn)一個標準鏈表胶惰，在實現(xiàn)的過程中哎迄，遵守函數(shù)式編程的規(guī)則谭贪，無副作用蜡励，可以看到和C語言的實現(xiàn)還是有較大的差異令花。
預備知識
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.)
除了上述的要求之外凉倚，下面還將對數(shù)值型鏈表增加：判斷是否存在元素兼都，移除指定元素，在指定元素后插入等
測試先行
基于測試先行的想法稽寒，嘗試先寫測試用例扮碧，需要注意我們的函數(shù)沒有副作用，意味著不會出現(xiàn)var類型變量杏糙，任何的修改都會產(chǎn)生新的對象慎王。
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的做法我們應該先定義好類和函數(shù)體，這里根據(jù)Swift的特性選擇了ENUM來實現(xiàn)這個鏈表宏侍，ENUM對于模式匹配有著天然的優(yōu)勢赖淤，在實現(xiàn)過程中，相信你也可以體會到谅河。不過ENUM也有一些缺點咱旱，比如不能被繼承等等嗜愈。看定義：
enum List<Element> {
//表示是一個空鏈表莽龟，也表示是鏈表的結束
case E
//鏈表的節(jié)點
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的對象才能執(zhí)行按值刪除，插入和判斷是否存在
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
}
}
上面的定義分成了三個部分锨天，第一個部分是構造基本定義毯盈，構造的時候會創(chuàng)建一個空鏈表，其中indirect的含義表示會嵌套使用List病袄，這個修飾符也可以放在enum的前面搂赋，含義相同。第二部分主要定義了空鏈表判斷益缠，元素數(shù)量脑奠，獲取頭尾，插入操作幅慌，對于head和tail宋欺，可以對應到Node定義上，Node的兩個元素分別為head和tail胰伍。第三部分定義要求Element實現(xiàn)了Equatable的協(xié)議齿诞，只要可以判斷是否包含特定元素，刪除指定元素骂租，以及在第一個指定元素后插入操作祷杈。
實現(xiàn)
好了，定義完成了渗饮，跑一下測試用例但汞，bingo，第一條assert通過互站，第二條失敗私蕾，因為第二條要求執(zhí)行append之后isEmpty失敗，所以接下來修改append和isEmpty這兩個實現(xiàn)云茸，實現(xiàn)如下：
//在鏈表最后追加新元素
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的實現(xiàn)非常簡單是目，不再贅述，append的實現(xiàn)使用了guard和模式匹配保證接下來的操作是基于.Node(head, tail)的标捺，否則的話就是空鏈表懊纳，我們創(chuàng)建并返回只有一個元素的鏈表.Node(elem, .E)，到這里應該就可以跑過剛才不過的用例了亡容；對于非空鏈表嗤疯，.Node(head, tail.append(elem))創(chuàng)建了一個新的鏈表，并把新的元素插入進去闺兢。這里如果沒有看明白的話簡單解釋一下執(zhí)行過程茂缚。
//假設我們有一個鏈表戏罢，其中有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) 執(zhí)行結果為 .Node(4, .E)
.Node(1, .Node(2, .Node(3, .Node(4, .E))))
上面的代碼明白之后后序的代碼就不會有什么問題了讲岁，回頭來看開頭的測試用例，block在head和tail了衬以，下面實現(xiàn)這兩個函數(shù)缓艳，前面也分析過了，其實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的實現(xiàn)
var count : Int {
switch self {
case .E :
return 0
case .Node(_, let tail):
return tail.count + 1
}
}
現(xiàn)在跑一下測試用例會發(fā)現(xiàn)前面三組都通過了阶淘，第四組因為用到了remove還沒有實現(xiàn)，所以失敗了互妓，思考一下移除一個元素的過程溪窒，很明顯需要知道如何判斷相等，所以這里要求Element實現(xiàn)了Equatable協(xié)議冯勉，不然編譯的時候會發(fā)現(xiàn)==無法調(diào)用霉猛。如何移除元素之后再把前面的部分和后面的部分鏈接起來呢？
假設鏈表是.Node(1, .Node(2, .Node(3, .Node(4, .Node(5, .E)))))珠闰，現(xiàn)在要移除其中一個元素惜浅，分兩種情況分析：
- 刪除第一個元素：比較簡單，直接返回tail即可
- 刪除其它元素伏嗜，和
append的思想是一樣的坛悉，保留head，然后在tail部分執(zhí)行刪除
實現(xiàn)如下：
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的實現(xiàn)：
func contains(_ elem : Element) -> Bool {
guard case let .Node(head, tail) = self else {return false}
return head == elem || tail.contains(elem)
}
到這里除了insert的沒有實現(xiàn)導致最后一組用例無法通過承绸，留下一個insert給大家做課后作業(yè)裸影。
后序計劃
- Tree
- R-B Tree
