文章內容過長，希望讀者見諒，寫的不好的地方多指教！！

寫在前面

從本文標題中的序號可以看出，本文是一個連載的開篇。

而且這個連載的標題是：數據結構 & 算法 in Swift。從這個連載的標題中可以看出，筆者分享的是使用Swift語言來實現所學的的數據結構和算法的知識。這裡面需要解釋兩點：

第一：為什麼學習數據結構和算法？

學習通用性知識，突破技能瓶頸：筆者做iOS開發也有兩年了，這期間通過從項目，第三方源碼，相關應用類的編程書籍提高了些技術水平。而作為沒學過數據結構和算法的非科班大軍中的一員，這些知識始終是繞不過去的。因為對此類知識的掌握程度會對今後編程技能的提高有著無可估量的影響，所以就決定學習了。

第二：為什麼用Swift語言來實現？

1. 選擇哪個語言並不重要，重要的是數據結構和算法本身的理解
   ：通過兩個星期的學習，如今筆者已經可以使用Swift語言來實現幾種數據結構和算法了，但我相信如果我使用C語言或者Objective-C語言的話會學得更快些，因為在實現的時候由於對該語言的不熟悉導致在實現過程中踩了不少坑。不過可以反過來思考：如果我可以使用Swift來實現這些，那麼我今後用C，Objective-C，甚至是Java就容易多了，再加上我還順便學習了Swift不是麼？
2. 如今Swift的勢頭還在上漲：筆者已經觀察到很多新的庫，教學都使用了Swift語言。而且聽說一些面試的朋友在面試過程中多少有問過Swift相關的知識，一些公司的新項目也有用Swift寫了。 ​

基於上面這些原因，在今年年初把數據結構，算法和Swift的學習提上了日程，並且計劃以連載的形式把學習過程中的筆記和知識分享出來。

該系列的最佳受眾是那些已經會Swift，但是對數據結構和算法還沒有過多接觸過的iOS開發者。其次是那些不會Swift也不會數據結構和算法的iOS開發者，畢竟Swift是大勢所趨。

不過對於那些非iOS開發者來說也同樣適合，因為還是那句話：

好了，背景介紹完了，現在正式開始：

作為該系列的開篇，本文分為兩個部分：

1. Swift語法基礎：講解一下後續連載中講到的數據結構和算法所涉及到的Swift語法知識（並不是很全面，也不是很深入，但是在實現數據結構和算法這塊應該是夠了）。
2. 數據結構：簡單介紹數據結構和算法的相關概念，以及用Swift來實現幾個簡單的數據結構（鏈表，棧，隊列）

注：該系列涉及到的Swift語法最低基於Swift4.0。

Swift 語法基礎

Swift語法基礎從以下幾點來展開：

1. 循環語句
2. 泛型
3. guard
4. 函數
5. 集合

循環語句

循環條件的開閉區間

Swift將循環的開閉區間做了語法上的簡化：

閉區間：

for index in 1...5 {
 print("index: \\(index)")
}
// index : 1
// index : 2
// index : 3
// index : 4
// index : 5

半開閉區間：

for index in 1..<5 {
 print("index: \\(index)")
}
// index : 1
// index : 2
// index : 3
// index : 4

循環的升序與降序

上面兩個例子都是升序的（index從小到大），我們來看一下降序的寫法：

for index in (1..<5).reversed() {
 print("index: \\(index)")
}
// index : 4
// index : 3
// index : 2
// index : 1

降序的應用可以在下篇的冒泡排序算法中可以看到。

泛型

使用泛型可以定義一些可複用的函數或類型，Swift中的Array和Dictionary都是泛型的集合。

為了體現出泛型的意義，下面舉一個例子來說明一下：

實現這樣一個功能:將傳入該函數的兩個參數互換。

整型的交換：

func swapTwoInts(_ a: inout Int, _ b: inout Int) {
 let tmp = a
 a = b
 b = tmp
}

字符串的交換：

func swapTwoStrings(_ a: inout String, _ b: inout String) {
 let tmp = a
 a = b
 b = tmp
 

複製代碼

浮點型的交換：

func swapTwoDoubles(_ a: inout Double, _ b: inout Double) {
 let tmp = a
 a = b
 b = tmp
}

上面這三種情況的實現部分其實都是一樣的，但僅僅是因為傳入類型的不一致，導致對於不同的類型還要定義一個新的函數。所以如果類型有很多的話，定義的新函數也會很多，這樣顯然是不夠優雅的。

此類問題可以使用泛型來解決：

func swapTwoValues(_ a: inout T, _ b: inout T) {
 let tmp = a
 a = b
 b = tmp
}

上面函數中的T是泛型的固定寫法，可以理解為“所有類型”。這樣一來，我們可以傳入任何相同的類型來作交換了。

泛型還有其他比較強大的功能，由於在後續的數據結構和算法的講解裡面可能不會涉及到，所以在這裡先不贅述了。有興趣的朋友可以參考官方文檔：Swift：Generics

guard

guard是 swift 2.0推出的新的判斷語句的用法。

與if語句相同的是，guard也是基於一個表達式的布爾值去判斷一段代碼是否該被執行。與if語句不同的是，guard只有在條件不滿足的時候才會執行這段代碼。你可以把guard近似的看做是Assert，但是你可以優雅的退出而非崩潰

使用guard語法，可以先對每個條件逐一做檢查，如果不符合條件判斷就退出（或者進行其他某些操作）。這就會讓人容易看出來什麼條件會讓這個函數退出（或者進行其他某些操作）。

可以用一個例子來分別使用if和guard來實現，體會二者的區別：

使用if-else

//money: holding moneny (用戶持有的錢數)
//price: product price (商品的價格)
//capacity: bag capacity (用戶用來裝商品的袋子容量)
//volume: product size (商品的大小)

func buying1( money: Int , price: Int , capacity: Int , volume: Int){
 
 if money >= price{
 
 if capacity >= volume{
 
 print("Start buying...")
 print("\\(money-price) money left after buying.")
 print("\\(capacity-volume) capacity left after buying.")
 
 }else{ 

 
 print("No enough capacity")
 }
 
 }else{
 
 print("No enough money")
 
 }

複製代碼

從上面的邏輯可以看出，當同時滿足：

1. 用戶的錢數>商品價格
2. 用戶用來裝商品的袋子容量>商品的大小

這兩個情況的時候，購買才會進行，其他所有情況都無法引發購買。

對於大多數習慣使用if-else的朋友來說，上面的代碼理解來並沒有難度，但是相同的邏輯，我們看一下使用guard之後的效果：

使用guard

func buying2( money: Int , price: Int , capacity: Int , volume: Int){
 
 guard money >= price else{
 print("No enough money")
 return
 }
 
 guard capacity >= volume else{
 print("No enough capacity")
 return
 }
  

 print("Start buying...")
 print("\\(money-price) money after buying.")
 print("\\(capacity-volume) capacity left after buying.")
}

從上面的實現可以看出：

• 使用guard以後，將money < price和capacity < volume 這兩個情況首先排除掉並填上了相應的處理代碼。
• 在兩個guard下面才是真正正確邏輯後的處理代碼。

因此通過兩個guard判斷的語句，我們知道該函數所處理的正確邏輯是什麼，非常清晰。

函數

因為後續的數據結構和算法的講解是離不開函數的使用的，所以在這裡簡單介紹一下Swift中函數的使用。

• 無返回值的函數
• 有返回值的函數
• 省略函數的外部參數名
• 值傳遞和引用傳遞

無返回值的函數

func log(message: String) { 

 print("log: \\(message)!")
}

log(message: "memory warning")
// output: log: memory warning!

有返回值的函數

func logString(string: String) -> String {
 return "log: " + string
}

let logStr = logString(string: "memory warning!")
print("\\(logStr)")
// output: log: memory warning!

省略函數外部參數名

通過在函數形參前面加上_,可以起到在調用時省略外部參數的作用：

func logMessage(_ message: String) {
 print("log: \\(message)!")
}

logMessage("memory warning")
// output: log: memory warning!

再來看一下兩個參數的情況：

func addInt(_ a : Int ,_ b : Int){
 print("sum is \\(a + b)")
}

addInt(3, 4)
//output : sum is 7

值傳遞和引用傳遞

Swift中，struct是按值傳遞，class是按引用傳遞。數組和字典在Swift裡是屬於struct，所以需要如果在一個函數里要修改傳入的數組，需要做特殊處理：

var originalArr = [2,1,3]

func removeLastInArray(_ array: inout [Int]){
 array.removeLast()
}
print("\\n============ before removing: \\(originalArr)")
//[2, 1, 3]

removeLastInArray(&originalArr)

print("============ after removing: \\(originalArr)")
//[2, 1]

在這裡使用的inout關鍵字就是將傳入的數組改為引用傳遞了。

集合

Swift裡的集合類型有：數組，集合，字典，下面來分別講一下。

這三種類型都支持泛型，也就是說裡面的元素可以是整數，字符串，浮點等等。

數組

Swift’s Array type is bridged to Foundation’s NSArray class.

可變數組與不可變數組

// immutable array
let immutableNumbers: [Int] = [1, 3, 5, 4, 4, 1]

// mutable array
var mutableNumbers : [Int] = [2, 1, 5, 4, 1, 3]

Swift中可以用let和var來分別聲明可變和不可變數組：數組的添加刪除等操作只能作用於可變數組。

數組的遍歷

// iteration 1
for value in mutableNumbers {
 if let index = mutableNumbers.index(of: value) {
 print("Index of \\(value) is \\(index)")
 }
}

// iteration 2
mutableNumbers.forEach { value in
 if let index = mutableNumbers.index(of: value) {
 print("Index of \\(value) is \\(index)")
 }
}

// iteration 3
for (index, value) in mutableNumbers.enumerated() {
 print("Item \\(index + 1): \\(value)")
}

數組的操作

mutableNumbers.append(11)
// Output: [2, 1, 5, 4, 1, 3, 11]

mutableNumbers.insert(42, at: 4)
// Output: [2, 1, 5, 4, 42, 1, 3, 11]

mutableNumbers.swapAt(0, 1)
// Output: [1, 2, 5, 4, 42, 1, 3, 11]

mutableNumbers.remove(at: 1)
// Output: [2, 5, 4, 42, 1, 3, 11]

mutableNumbers.removeFirst()
// Output: [5, 4, 42, 1, 3, 11]

mutableNumbers.removeLast()
// Output: [5, 4, 42, 1, 3]

mutableNumbers.removeAll()
//[]

append函數的作用是在數組的末尾添加元素

swapAt函數的作用是交換在傳入的兩個index上的元素，該方法在下篇的排序算法中使用得非常頻繁。

集合

Swift’s Set type is bridged to Foundation’s NSSet class.

集合的無序性，值的唯一性

關於集合與數組的區別，除了數組有序，集合無序以外，數組內部的元素的數值可以不是唯一的；但是集合裡元素的數值必須是唯一的，如果有重複的數值會算作是一個：

//value in set is unique
let onesSet: Set = [1, 1, 1, 1]
print(onesSet)
// Output: [1]

let onesArray: Array = [1, 1, 1, 1]
print(onesArray)
// Output: [1, 1, 1, 1]

集合的遍歷

let numbersSet: Set = [1, 2, 3, 4, 5]
print(numbersSet)
// Output: undefined order, e.g. [5, 2, 3, 1, 4]


// iteration 1
for value in numbersSet {
 print(value)
}
// output is in undefined order


// iteration 2
numbersSet.forEach { value in
 print(value)
}
// output is in undefined order

集合的操作

var mutableStringSet: Set = ["One", "Two", "Three"] 

let item = "Two"

//contains
if mutableStringSet.contains(item) {
 print("\\(item) found in the set")
} else {
 print("\\(item) not found in the set")
}

//isEmpty
let strings = Set<string>()
if strings.isEmpty {
 print("Set is empty")
}

//count
let emptyStrings = Set<string>()
if emptyStrings.count == 0 {
 print("Set has no elements")
}

//insert
mutableStringSet.insert("Four")


//remove 1
mutableStringSet.remove("Three")

//remove 2
if let removedElement = mutableStringSet.remove("Six") {
 print("\\(removedElement) was removed from the Set")
} else {
 print("Six is not found in the Set")
}

//removeAll()
mutableStringSet.removeAll()
// []/<string>/<string>

字典

A dictionary Key type must conform to the Hashable protocol, like a set’s value type.

//empty dictionary
var dayOfWeek = Dictionary()
var dayOfWeek2 = [Int: String]()

//not empty dictionary
var dayOfWeek3: [Int: String] = [0: "Sun", 1: "Mon", 2: "Tue"] 

print(dayOfWeek3)
//output:[2: "Tue", 0: "Sun", 1: "Mon"]

可以看到字典的鍵值對也是無序的，它與聲明時的順序不一定一致。

字典的遍歷

// iteration 1
for (key, value) in dayOfWeek {
 print("\\(key): \\(value)")
}

// iteration 2
for key in dayOfWeek.keys {
 print(key)
}

// iteration 3
for value in dayOfWeek.values {
 print(value)
}

字典的操作

// find value
dayOfWeek = [0: "Sun", 1: "Mon", 2: "Tue"]
if let day = dayOfWeek[2] {
 print(day)
}

// addValue 1
dayOfWeek[3] = "Wed"
print(dayOfWeek)
// Prints: [2: "Tue", 0: "Sun", 1: "Mon", 3: "Wed"]

// updateValue 1
dayOfWeek[2] = "Mardi"
print(dayOfWeek)
// Prints: [2: "Mardi", 0: "Sun", 1: "Mon", 3: "Wed"]

// updateValue 2
dayOfWeek.updateValue("Tue", forKey: 2)
print(dayOfWeek)
// Prints: [2: "Tue", 0: "Sun", 1: "Mon", 3: "Wed"]
 

// removeValue 1
dayOfWeek[1] = nil
print(dayOfWeek)
// Prints: [2: "Tue", 0: "Sun", 3: "Wed"]

// removeValue 2
dayOfWeek.removeValue(forKey: 2)
print(dayOfWeek)
// Prints: [0: "Sun", 3: "Wed"]

// removeAll
dayOfWeek.removeAll()

print(dayOfWeek)
// Output: [:]

可以看到從字典裡面刪除某個鍵值對有兩個方法：

使用removeValue方法並傳入要刪除的鍵值對裡的鍵。 將字典取下標之後將nil賦給它。

數據結構

這一部分內容主要是對連載的後續文章作鋪墊，讓大家對數據結構先有一個基本的認識，因此在概念上不會深入講解。該部分由以下三點展開：

• 數據結構的基本概念
• 抽象數據類型
• 鏈表，棧和隊列的實現 ​

概念

首先我們來看一下數據結構的概念：

數據結構：是相互之間存在一種或多種特定關係的數據元素的集合。

由數據結構這個詞彙的本身（數據的結構）以及它的概念可以看出，它的重點在於“結構”和“關係”。所以說，數據是何種數據並不重要，重要的是這些數據是如何聯繫起來的。

而這些聯繫，可以從兩個維度來展開：

1. 邏輯結構：指數據對象中元素之間的相互關係。
2. 物理結構：指數據的邏輯結構在計算機中的存儲形式。

可以看出，邏輯結構是抽象的聯繫，而物理結構是實際在計算機內存裡的具體聯繫。那麼它們自己又細分為哪些結構呢？

邏輯結構：

• 集合結構：集合結構中的數據元素除了同屬於一個集合外，它們之間沒有其他關係。
• 線性結構：線性結構中的數據元素之間是一對一的關係。
• 樹形結構：數據結構中的元素存在一對多的相互關係。
• 圖形結構：數據結構中的元素存在多對多的相互關係。

物理結構：

• 順序存儲結構：把數據元素存放在地址連續的存儲單元裡，其數據間的邏輯關係和物理關係是一致的（數組）。
• 鏈式存儲結構：把數據元素存放在任意的存儲單元裡，這組存儲單元可以是連續的，也可以是不連續的。

為了便於記憶，用思維導圖總結一下上面所說的：

而通過結合這兩個維度中的某個結構，可以定義出來一個實際的數據結構的實現：

比如線性表就是線性結構的一種實現：

• 順序存儲結構的線性表就是數組：它的內存分佈是連續的，元素之間可以通過內存地址來做關聯；
• 鏈式存儲結構的線性表就是鏈表：它的內存分佈可以是不連續的，元素之間通過指針來做關聯： 如果每個元素（在鏈表中稱作節點）只持有指向後面節點的指針，那此鏈表就是單鏈表。 如果每個元素（在鏈表中稱作節點）持有指向前後節點的兩個指針，那此鏈表就是雙鏈表。

為什麼會有鏈表這麼麻煩的東西？像數組這樣，所有內存地址都是連續的不是很方便麼？既生瑜何生亮呢？

對於獲取元素（節點）這一操作，使用數組這個數據結構確實非常方便：因為所有元素在內存中是連續的，所以只需要知道數組中第一個元素的地址以及要獲取元素的index就能算出該index內存的地址，一步到位非常方便。

但是對於向數組中某個index中插入新的元素的操作恐怕就沒有這麼方便了：恰恰是因為數組中所有元素的內存是連續的，所以如果想在中間插入一個新的元素，那麼這個位置後面的所有元素都要後移，顯然是非常低效的。如果插在數組尾部還好，如果插在第一位的話成本就太高了。

而如果使用鏈表，只要把要插入到的index前後節點的指針賦給這個新的節點就可以了，不需要移動原有節點在內存中的位置。

關於鏈表的這種插入操作會在後面用代碼的形式體現出來。

既然有這麼多的數據結構，那麼有沒有一個標準的格式來將這些特定的數據結構（也可以說是數學模型）抽象出來呢？答案是肯定的，它就是我們下一節要講的抽象數據類型。

抽象數據類型

首先來看一下抽象數據類型的概念，摘自《大話數據結構》:

抽象數據類型（Abstract Data Type，ADT）：是指一個數學模型及定義在該模型上的一組操作。

需要注意的是：抽象數據類型的定義僅僅取決於它的一組邏輯特性，而與其在計算機內部如何表示和實現沒有關係。而且，抽象數據類型不僅僅指那些已經定義並實現的數據類型，還尅是計算機編程者自己定義的數據類型。

我們看一下數據類型的標準格式：

ADT 抽象數據類型名

Data
 數據元素之間邏輯關係的定義
 
Operation
 操作1
 初始條件
 操作結果描述
 
 操作2
 初始條件
 操作結果描述
 
 操作n

endADT

其實看上去和麵向對象編程裡的類的定義相似：

• 可以把抽象數據類型的Data 和 類的成員變量聯繫起來。
• 可以把抽象數據類型的操作和類的函數聯繫起來。

簡單來說，抽象數據類型描述了一個數據模型所使用的數據和數據之間的邏輯關係，以及它可以執行的一些操作。因此，如果知道了一個數學模型的抽象數據類型，那麼在真正接觸數學模型的實現（代碼）之前，就可以對該數學模型能做的事情有一個大致的瞭解。

下一章筆者會介紹鏈表，棧和隊列這三個數學模型，在講解每個數學模型的實現之前都會給出它們各自的抽象數據類型，讓讀者可以先對當前數學模型有個大致的瞭解。

注意：書本文歸納的所有抽象數據類型是筆者自己根據網上資料和相關書籍而定下來的，所以嚴格來說它們並不是“最官方”的抽象數據類型。讀者也可以參考網上的資料或是相關書籍，結合自己的思考來定義自己對著三個數據模型的抽象數據類型。

鏈表，棧和隊列的實現

通過上一節的介紹，我們知道了數據結構的概念以及分類，還知道了不同的數據結構在不同的場景下會發揮不同的優勢，我們要根據實際的場景來選擇合適的數據結構。

下面就來介紹幾種在實際應用中使用的比較多的數學模型：

• 鏈表
• 棧
• 隊列

鏈表（Linked list）

說到鏈表就不得不提線性表這一數據結構，在介紹鏈表之前，首先看一下線性表的定義：

線性表：零個或多個數據元素的有限序列。

而根據物理結構的不同，線性表有兩種具體的實現方式：

• 線性表的順序存儲結構：線性表的數據元素是被一段地址連續的存儲單存儲起來的。
• 線性表的鏈式存儲結構: 線性表的數據元素是被用一組連續或不連續的存儲單元存儲起來的，這些元素通過指針來作為邏輯上的連接。

注：上面兩個概念是筆者用自己的話總結出來的。

在這裡，線性表的順序存儲結構的實現就是我們熟悉的數組；而線性表的鏈式存儲結構的實現就是筆者即將要介紹的鏈表。

鏈表的定義

相信對於讀完上一節的朋友來說，應該對鏈表有一個比較清晰的認識了。關於鏈表的定義有很多不同的版本，筆者個人比較喜歡百度百科裡的定義：

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

而且由於數據元素所持有的指針個數和鏈接特性可以將鏈表分為：

• 單向鏈表：單向鏈表的鏈接方向是單向的，其中每個結點都有指針成員變量指向列表中的下一個結點；
• 雙向鏈表：雙向鏈表的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點，它的鏈接方向是雙向的。
• 循環鏈表：循環鏈表是另一種形式的鏈式存貯結構。它的特點是表中最後一個結點的指針域指向頭結點，整個鏈表形成一個環。

筆者從中挑選出雙向鏈表來進行講解，它的難度適中，而且能夠很好地讓讀者體會出鏈表的優勢。

雙向鏈表的抽象數據類型

因為節點是鏈表的基本組成單元，所以想要實現鏈表，必須先要介紹鏈表的組成部分-節點。

節點：

ADT 節點(node)

Data
 value:持有的數據

Operation
 init:初始化
 previous:指向上一節點的指針
 next:指向下一節點的指針
 
endADT
複製代碼

再來看一下鏈表的抽象數據類型：

ADT 鏈表（linked list）

Data 

 linked list:持有的線性表

Operation
 init:初始化
 count:持有節點總個數
 isEmpty:是否為空
 first:頭節點
 last:尾節點
 node:傳入index返回節點
 insert:插入node到指定index
 insertToHead:插入節點到表頭
 appendToTail:插入節點到表尾
 removeAll:移除所有節點
 remove:移除傳入的節點
 removeAt:移除傳入index的節點
 
endADT

雙向鏈表的實現

節點

public class LinkedListNode {
 
 //value of a node
 var value: T
 
 //pointer to previous node
 weak var previous: LinkedListNode?
 
 //pointer to next node
 var next: LinkedListNode?
 
 
 //init
 public init(value: T) {
 self.value = value
 }
}

再來看一下鏈表的實現：

因為整個鏈表的插入，刪除等操作比較多，整個鏈表的定義超過了200行代碼，所以為了看著方便一點，在這裡來分段說明一下。

首先看一下鏈表的成員變量:

成員變量

public class LinkedList {
 
 public typealias Node = LinkedListNode
 
 //if empty
 public var isEmpty: Bool {
 return head == nil
 }
 
 //total count of nodes
 public var count: Int {
 
 guard var node = head else {
 return 0
 }
 
 var count = 1
 while let next = node.next {
 node = next
 count += 1
 }
 return count
 }
 
 //pointer to the first node, private
 private var head: Node?
 
 //pointer to the first node, public
 public var first: Node? {
 return head
 }
  

 //pointer to the last node
 public var last: Node? {
 
 guard var node = head else {
 return nil
 }
 
 //until node.next is nil
 while let next = node.next {
 node = next
 }
 return node
 }
 
 ...
 
}

相信看上面的命名以及註釋大家可以對鏈表的成員變量有個初步的理解，這裡面需要說三點：

1. typealias是用來重新為已經存在的類型命名的：這裡用Node代替了LinkedListNode（節點類型），降低了不少閱讀代碼的成本。
2. 在獲取count和last的實現，都先判斷了head這個指針是否為nil，如果是則判定為空鏈表，自然也就不存在節點個數和最後的節點對象了。
3. 同樣地，也是在獲取count和last的實現裡，使用了while控制語句來判斷node.next節點是否存在：如果存在，則繼續+1或者繼續往下尋找，直到node.next為nil時才停止。在這裡我們可以看到鏈表的尋址方式：是通過頭結點開始，以節點的.next指針來尋找下一個節點的。而且作為鏈表的尾節點，它的.next指針不指向任何對象，因為它本來就是鏈表的最後一項。

最下方的…代表即將在下面介紹的一些函數，這些函數都定義在的LinkedList這個class裡面。

獲取index上node

//get node of index
public func node(atIndex index: Int) -> Node? {

 if index == 0 {
 //head node
 return head!

 } else {

 var node = head!.next

 guard index < count else {
 return nil;
 }

 for _ in 1..<index> // go on finding by .next
 node = node?.next
 if node == nil {
 break
 }
 }

 return node!
 }
}/<index>

注意在這裡返回的node是可以為nil的，而且在這裡可以看出來，鏈表在尋找特定node的時候，是根據節點的.next指針來一個一個尋找的。這個與順序存儲結構的數組是不同的，在後面我會重點講解一下這二者的不同。

插入節點

//insert node to last index
public func appendToTail(value: T) { 


 let newNode = Node(value: value)

 if let lastNode = last {

 //update last node: newNode becomes new last node;
 //the previous last node becomes the second-last node
 newNode.previous = lastNode
 lastNode.next = newNode

 } else {

 //blank linked list
 head = newNode
 }
}

//insert node to index 0
public func insertToHead(value: T) {

 let newHead = Node(value: value)

 if head == nil {
\t\t//blank linked list
 head = newHead

 }else {

 newHead.next = head
 head?.previous = newHead
 head = newHead

 }
}

//insert node in specific index
public func insert(_ node: Node, atIndex index: Int) {

 if index < 0 {
 print("invalid input index")
 return
 }

 let newNode = node

 if count == 0 {

 head = newNode

 }else { 


 if index == 0 {

 newNode.next = head
 head?.previous = newNode
 head = newNode

 } else {

 if index > count {

 print("out of range")
 return

 }

 let prev = self.node(atIndex: index-1)
 let next = prev?.next

 newNode.previous = prev
 newNode.next = prev?.next
 prev?.next = newNode
 next?.previous = newNode
 }

 }
}

鏈表的插入節點的操作分為三種，按照從上到下的順序依次是：

1. 在頭部插入
2. 在尾部插入
3. 指定index插入

需要注意的是

• 在前兩種插入函數中，需要先判斷該鏈表是否是空的，如果是，則要將鏈表的該節點賦給鏈表的head指針。
• 在第三種插入函數中，還是先判斷該鏈表是否是空的，如果是，則無論index是多少(只要不小於0)，都插在鏈表的頭部。如果不是空的，再判斷index是否為0，如果是，則直接插在頭部；如果index不為0，則判斷index是否大於count，如果是，則無法插入；如果不是，則獲取插入位置的前後節點進行重連。

在這裡判斷鏈表為空鏈表後的處理是筆者自己加上去的，筆者在網上的資料裡沒有看到過。大家不必糾結於這種處理方式，畢竟鏈表操作的重點在於前後節點的重連。

移除節點

//removing all nodes
public func removeAll() {
 head = nil
}

//remove the last node
public func removeLast() -> T? {

 guard !isEmpty else {
 return nil
 }

 return remove(node: last!)
}

//remove a node by it's refrence
public func remove(node: Node) -> T? {

 guard head != nil else {
 print("linked list is empty")
 return nil
 }
 

 let prev = node.previous
 let next = node.next

 if let prev = prev {
 prev.next = next
 } else {
 head = next
 }

 next?.previous = prev

 node.previous = nil
 node.next = nil
 return node.value
}


//remove a node by it's index
public func removeAt(_ index: Int) -> T? {

 guard head != nil else {
 print("linked list is empty")
 return nil
 }

 let node = self.node(atIndex: index)
 guard node != nil else {
 return nil
 }
 return remove(node: node!)
}

• 如果要移除鏈表上所有節點，只需要將head指針置空就可以了，因為它是所有節點的“源頭”，是鏈表尋址的第一個節點。
• 在持有某個節點的指針的時候可以指定鏈表來移除這個節點（使用remove函數）。在這個函數內部，首先需要將該節點的前後節點對接，然後將該幾點的前後指針置空。
• 當有要移除節點的指針但是知道該節點在鏈表中的index，可以使用removeAt函數。在這個函數內部，首先根據index來獲取對應的node的指針，然後再調用remove函數刪除這個node。

打印所有節點

public func printAllNodes(){

 guard head != nil else {
 print("linked list is empty")
 return
 }

 var node = head

 print("\\nstart printing all nodes:")

 for index in 0..<count>
 if node == nil {
 break
 }

 print("[\\(index)]\\(node!.value)")
 node = node!.next

 }
}/<count>

該函數只是為了方便調試，為了跟蹤鏈表的狀態而定義的，它並不存在於鏈表的模型裡。

為了驗證上面這些方法的有效性，我們來實例化一個鏈表後實際操作一下，讀者可以結合註釋來看一下每一步對應的結果：

let list = LinkedList<string>()
list.isEmpty // true
list.first // nil
list.count // 0

list.appendToTail(value: "Swift")
list.isEmpty // false
list.first!.value // "Swift"
list.last!.value // "Swift"
list.count //1
 

list.appendToTail(value:"is")
list.first!.value // "Swift"
list.last!.value // "is"
list.count // 2

list.appendToTail(value:"great")
list.first!.value // "Swift"
list.last!.value // "great"
list.count // 3


list.printAllNodes()
//[0]Swift
//[1]is
//[2]Great

list.node(atIndex: 0)?.value // Swift
list.node(atIndex: 1)?.value // is
list.node(atIndex: 2)?.value // great
list.node(atIndex: 3)?.value // nil


list.insert(LinkedListNode.init(value: "language"), atIndex: 1)
list.printAllNodes()
//[0]Swift
//[1]language
//[2]is
//[3]great


list.remove(node: list.first!)
list.printAllNodes()
//[0]language
//[1]is
//[2]great


list.removeAt(1)
list.printAllNodes()
//[0]language
//[1]great

list.removeLast()
list.printAllNodes()
//[0]language

list.insertToHead(value: "study")
list.count // 2
list.printAllNodes()
//[0]study 

//[1]language


list.removeAll()
list.printAllNodes()//linked list is empty

list.insert(LinkedListNode.init(value: "new"), atIndex: 3)
list.printAllNodes()
//[0]new

list.insert(LinkedListNode.init(value: "new"), atIndex: 3) //out of range
list.printAllNodes()
//[0]new

list.insert(LinkedListNode.init(value: "new"), atIndex: 1)
list.printAllNodes()
//[0]new
//[1]new/<string>

棧（Stack）

棧的講解從

• 棧的定義
• 棧的抽象數據類型
• 棧的實現

三個部分來展開。

棧的定義

首先來看一下棧的定義：

棧是限定僅在表的尾部進行插入和刪除操作的線性表。

從定義中可以看出，我們知道我們只能在棧的一端來操作棧：

• 允許插入和刪除的一端成為棧頂
• 另一端成為棧底

用一張圖來看一下棧的操作：

圖源：《維基百科：Stack (abstract data type)》

從上圖可以看出，最先壓入棧裡面的只能最後訪問，也就是說，棧遵循後進先出（Last In First Out, LIFO）的原則。

棧的抽象數據類型

ADT 棧（Stack）

Data
 linked list:持有的線性表

Operation
 init:初始化
 count:棧的元素個數
 isEmpty:是否為空
 push:入棧
 pop:出棧
 top:返回頂部元素
 
endADT

上面的operation可能不全，但是涵蓋了棧的一些最基本的操作。那麼基於這個抽象數據類型，我們來看一下如何使用Swift來實現它。

棧的實現

筆者將數組（順序存儲）作為棧的線性表的實現，同時支持泛型。

public struct Stack 
 {
 
 //array
 fileprivate var stackArray = [T]()
 
 //count
 public var count: Int {
 return stackArray.count
 }
 
 //is empty ?
 public var isEmpty: Bool {
 return stackArray.isEmpty
 }
 
 //top element
 public var top: T? {
 
 if isEmpty{
 return nil
 }else {
 return stackArray.last
 }
 
 }
 
 //push operation
 public mutating func push(_ element: T) {
 stackArray.append(element)
 }
 
 
 //pop operation
 public mutating func pop() -> T? {
 
 if isEmpty{
 print("stack is empty")
 return nil
 }else {
 return stackArray.removeLast()
 }
 }
 
 //print all
 public mutating func printAllElements() {
 
 guard count > 0 else {
 print("stack is empty")
 return
 } 

 
 print("\\nprint all stack elemets:")
 for (index, value) in stackArray.enumerated() {
 print("[\\(index)]\\(value)")
 }
 }
}

• fileprivate：是Swift3.0新增的訪問控制，表示在定義的聲明文件裡可訪問。它代替了過去意義上的private。而有了fileprivate以後，新的private則代表了真正的私有：在這個類或結構體的外部無法訪問。
• 這裡printAllElements方法也不屬於抽象數據類型裡的方法，也是為了方便調試，可以打印出所有的數據元素。

我們來實例化上面定義的棧實際操作一下：

var stack = Stack.init(stackArray: [])
stack.printAllElements() //stack is empty
stack.isEmpty //true

stack.push(2)
stack.printAllElements()
//[0]2

stack.isEmpty //false
stack.top //2


stack.push(3)
stack.printAllElements()
//[0]2
//[1]3

stack.isEmpty //false
stack.top //3
 


stack.pop()
stack.printAllElements()
//[0]2

stack.isEmpty //false
stack.top //2


stack.pop()
stack.printAllElements() //stack is empty
stack.top //nil
stack.isEmpty //true

stack.pop() //stack is empty

隊列（Queue）

隊列的講解從

• 隊列的定義
• 隊列的抽象數據類型
• 隊列的實現

三個部分來展開。

隊列的定義

圖源：《維基百科：FIFO (computing and electronics)》

隊列的抽象數據類型

ADT 隊列（Queue）

Data
 linked list:持有的線性表

Operation
 init:初始化
 count:棧的元素個數
 isEmpty:是否為空
 front:獲取隊列頭元素
 enqueue:插入到隊尾
 dequeue:刪除隊列頭元素並返回
 
endADT

和上面的棧的實現一致，隊列的實現也使用數組來實現隊列內部的線性表。

隊列的實現

public struct Queue {
 
 //array
 fileprivate var queueArray = [T]()
 
 
 //count
 public var count: Int {
 return queueArray.count
 } 

 
 
 //is empty?
 public var isEmpty: Bool {
 return queueArray.isEmpty
 }
 
 
 //front element
 public var front: T? {
 
 if isEmpty {
 print("queue is empty")
 return nil
 } else {
 return queueArray.first
 }
 }
 
 
 //add element
 public mutating func enqueue(_ element: T) {
 queueArray.append(element)
 }
 
 
 //remove element
 public mutating func dequeue() -> T? {
 if isEmpty {
 print("queue is empty")
 return nil
 } else {
 return queueArray.removeFirst()
 }
 }
 
 //print all
 public mutating func printAllElements() {
 
 guard count > 0 else {
 print("queue is empty")
 return
 }
 
 print("\\nprint all queue elemets:")
 for (index, value) in queueArray.enumerated() {
 print("[\\(index)]\\(value)")
 }
 }
  

}

我們初始化一個隊列後實際操作一下：

var queue = Queue.init(queueArray: [])
queue.printAllElements()//queue is empty
queue.isEmpty //true
queue.count //0


queue.enqueue(2)
queue.printAllElements()
queue.isEmpty //false
//[0]2

queue.enqueue(3)
queue.printAllElements()
//[0]2
//[1]3


queue.enqueue(4)
queue.printAllElements()
//[0]2
//[1]3
//[2]4
queue.front //2


queue.dequeue()
queue.printAllElements()
//[0]3
//[1]4
queue.front //3


queue.dequeue()
queue.printAllElements()
//[0]4
queue.front //4

queue.dequeue()
queue.printAllElements() //queue is empty
queue.front //return nil, and print : queue is empty
queue.isEmpty //true
queue.count//0
 

最後的話

這兩週學習數據結構和算法讓我收穫很多，除了強化了Swift語法以外，感覺自己看代碼的感覺變了：看到一個設計就會想到裡面所用到的數據結構，或是算法上面有沒有可以優化的可能等等。

我相信對我來說編程的一扇新的門被打開了，希望自己可以堅持下去，看到更廣闊的世界。

該系列的所有代碼會放在我的GitHub的一個項目裡面，項目地址：Github:data-structure-and-algorithm-in-Swift

本篇文章的代碼：

• Swift語法部分：[1].Swift syntax
• 數據結構部分：[2].Data structure

鏈接：https://juejin.im/post/5a7096fa6fb9a01cb64f163b
來源：掘金

閱讀更多 Java技術分享 的文章

關鍵字: 數據結構 Objective-C Swift語言