本文將使用Swift實現(xiàn)一個標(biāo)準(zhǔn)鏈表，在實現(xiàn)的過程中，遵守函數(shù)式編程的規(guī)則，無副作用，可以看到和C語言的實現(xiàn)還是有較大的差異。

預(yù)備知識

• enum的各種用法
• swift的基本的模式匹配（pattern matching)
  -- 代碼里面case后面部分屬于模式匹配，包含switch case, guard case, let case等
• extension的用法
• guard
• generic
  遇到不懂的地方可以參閱官方文檔學(xué)習(xí)即可

鏈表定義

首先來看一下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的做法我們應(yīng)該先定義好類和函數(shù)體，這里根據(jù)Swift的特性選擇了ENUM來實現(xiàn)這個鏈表，ENUM對于模式匹配有著天然的優(yōu)勢，在實現(xiàn)過程中，相信你也可以體會到。不過ENUM也有一些缺點，比如不能被繼承等等?？炊x：

enum List<Element> {
    //表示是一個空鏈表，也表示是鏈表的結(jié)束
    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
    }
}

上面的定義分成了三個部分，第一個部分是構(gòu)造基本定義，構(gòu)造的時候會創(chuàng)建一個空鏈表，其中indirect的含義表示會嵌套使用List，這個修飾符也可以放在enum的前面，含義相同。第二部分主要定義了空鏈表判斷，元素數(shù)量，獲取頭尾，插入操作，對于head和tail，可以對應(yīng)到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)，到這里應(yīng)該就可以跑過剛才不過的用例了；對于非空鏈表，.Node(head, tail.append(elem))創(chuàng)建了一個新的鏈表，并把新的元素插入進去。這里如果沒有看明白的話簡單解釋一下執(zhí)行過程。

//假設(shè)我們有一個鏈表，其中有4個元素，分別為1，2，3，那么這個鏈表的表示應(yīng)該為：
.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í)行結(jié)果為 .Node(4, .E)
.Node(1, .Node(2, .Node(3, .Node(4, .E))))

上面的代碼明白之后后序的代碼就不會有什么問題了，回頭來看開頭的測試用例，block在head和tail了，下面實現(xiàn)這兩個函數(shù)，前面也分析過了，其實List結(jié)構(gòu)主要就是.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)用。如何移除元素之后再把前面的部分和后面的部分鏈接起來呢？

假設(shè)鏈表是.Node(1, .Node(2, .Node(3, .Node(4, .Node(5, .E)))))，現(xiàn)在要移除其中一個元素，分兩種情況分析：

1. 刪除第一個元素：比較簡單，直接返回tail即可
2. 刪除其它元素，和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)導(dǎo)致最后一組用例無法通過，留下一個insert給大家做課后作業(yè)。

后序計劃

• Tree
• R-B Tree