通過前面課時的學習，我們了解到數據在代碼中被處理和加工的最小單位動作是增、刪、查。它們是深入學習數據結構的根基，通過“增刪查”的操作，我們可以選擇更合適的數據結構來解決實際工作中遇到的問題。例如，幾個客戶端分別向服務端發送請求，服務端要采用先到先得的處理方式，應該如何設計數據結構呢？接下來，從本課時開始，我們將正式開始系統性的學習數據結構的內容。 #### 什么是數據結構？ 首先，我們簡單探討一下什么是數據結構。數據結構，從名字上來看是數據的結構，也就是數據的組織方式。在數據結構適用的場合中，需要有一定量的數據。如果數據都沒有，也就不用討論數據如何組織了。當我們有了一定數量的數據時，就需要考慮以什么樣的方式去對這些數據進行組織了。 接下來，我將通過一個實際案例來幫助你更好地理解數據結構。假設你是一所幼兒園的園長，現在你們正在組織一場運動會，所有的小朋友需要在操場上接受檢閱。那么，如何組織小朋友有序站隊并完成檢閱呢？ 幾個可能的方式是，讓所有的小朋友站成一橫排，或者讓小朋友站成方陣，又或者讓所有的小朋友手拉手，圍成一個大圓圈等等。很顯然，這里有無數種可行的組織方式。具體選擇哪個組織方式，取決于哪一種能更好地展示出小朋友們的風采。 試想一下，當計算機要處理大量數據時，同樣需要考慮如何去組織這些數據，這就是數據結構。類似于小朋友的站隊方式有無數種情況，數據組織的方式也是有無數種可能性。 然而，在實際開發中，經過工程師驗證?并且能有效解決問題的高效率數據結構就比較有限了。事實上，只要我們把這些能真正解決問題的數據結構學會，就足以成為一名合格的軟件工程師了。 #### 什么是線性表 好了，鋪墊完數據結構的基本概念后，我們就正式進入到這個課程中的第一個數據結構的學習，線性表。 線性表是 n 個數據元素的有限序列，最常用的是鏈式表達，通常也叫作線性鏈表或者鏈表。在鏈表中存儲的數據元素也叫作結點，一個結點存儲的就是一條數據記錄。每個結點的結構包括兩個部分： * 第一是具體的數據值； * 第二是指向下一個結點的指針。  在鏈表的最前面，通常會有個頭指針用來指向第一個結點。對于鏈表的最后一個結點，由于在它之后沒有下一個結點，因此它的指針是個空指針。鏈表結構，和小朋友手拉手站成一排的場景是非常相似的。 例如，你需要處理的數據集是 10 個同學考試的得分。如果用鏈表進行存儲，就會得到如下的數據：  仔細觀察上圖，你會發現這個鏈表只能通過上一個結點的指針找到下一個結點，反過來則是行不通的。因此，這樣的鏈表也被稱作單向鏈表。 有時候為了彌補單向鏈表的不足，我們可以對結點的結構進行改造： * 對于一個單向鏈表，讓最后一個元素的指針指向第一個元素，就得到了循環鏈表； * 或者把結點的結構進行改造，除了有指向下一個結點的指針以外，再增加一個指向上一個結點的指針。這樣就得到了雙向鏈表。   同樣的，還可以對雙向鏈表和循環鏈表進行融合，就得到了雙向循環鏈表，如下圖所示：  這些種類的鏈表，都是以單向鏈表為基礎進行的變種。在某些場景下能提高線性表的效率。 #### 線性表對于數據的增刪查處理 學會了線性表原理之后，我們就來圍繞數據的增刪查操作，來看看線性表的表現。在這里我們主要介紹單向鏈表的增刪查操作，其他類型的鏈表與此雷同，我們就不再重復介紹了。 首先看一下增加操作。如下有一個鏈表，它存儲了 10 個同學的考試成績。現在發現這樣的問題，在這個鏈表中，有一個同學的成績忘了被存儲進去。假設我們要把這個成績在紅色的結點之后插入，那么該如何進行呢？ 其實，鏈表在執行數據新增的時候非常容易，只需要把待插入結點的指針指向原指針的目標，把原來的指針指向待插入的結點，就可以了。如下圖所示：  代碼如下： ``` s.next = p.next; p.next = s; ``` 接下來我們看一下刪除操作。還是這個存儲了同學們考試成績的鏈表，假設里面有一個成績的樣本是被誤操作放進來的，我們需要把這個樣本刪除。鏈表的刪除操作跟新增操作一樣，都是非常簡單的。如果待刪除的結點為 b，那么只需要把指向 b 的指針 （p.next），指向 b 的指針指向的結點（p.next.next）。如下圖所示：  代碼如下： ``` p.next = p.next.next; ``` 最后，我們再來看看查找操作。我們在前面的課時中提到過，查找操作有兩種情況： * 第一種情況是按照位置序號來查找。 它和數組中的 index 是非常類似的。假設一個鏈表中，按照學號存儲了 10 個同學的考試成績。現在要查找出學號等于 5 的同學，他的考試成績是多少，該怎么辦呢？ 其實，鏈表的查找功能是比較弱的，對于這個查找問題，唯一的辦法就是一個一個地遍歷去查找。也就是，從頭開始，先找到學號為 1 的同學，再經過他跳轉到學號為 2 的同學。直到經過多次跳轉，找到了學號為 5 的同學，才能取出這個同學的成績。如下圖所示：  * 第二種情況是按照具體的成績來查找。 同樣，假設在一個鏈表中，存儲了 10 個同學的考試成績。現在要查找出是否有人得分為 95 分。鏈表的價值在于用指針按照順序連接了數據結點，但對于每個結點的數值則沒有任何整合。當需要按照數值的條件進行查找時，除了按照先后順序進行遍歷，別無他法。 因此，解決方案是，判斷第一個結點的值是否等于 95： * 如果是，則返回有人得分為 95 分； * 如果不是，則需要通過指針去判斷下一個結點的值是否等于 95。以此類推，直到把所有結點都訪問完。   根據這里的分析不難發現，鏈表在新增、刪除數據都比較容易，可以在 O(1) 的時間復雜度內完成。但對于查找，不管是按照位置的查找還是按照數值條件的查找，都需要對全部數據進行遍歷。這顯然就是 O(n) 的時間復雜度。 雖然鏈表在新增和刪除數據上有優勢，但仔細思考就會發現，這個優勢并不實用。這主要是因為，在新增數據時，通常會伴隨一個查找的動作。例如，在第五個結點后，新增一個新的數據結點，那么執行的操作就包含兩個步驟： * 第一步，查找第五個結點； * 第二步，再新增一個數據結點。整體的復雜度就是 O(n) + O(1)。  根據我們前面所學的復雜度計算方法，這也等同于 O(n) 的時間復雜度。線性表真正的價值在于，它對數據的存儲方式是按照順序的存儲。如果數據的元素個數不確定，且需要經常進行數據的新增和刪除時，那么鏈表會比較合適。如果數據元素大小確定，刪除插入的操作并不多，那么數組可能更適合些。 關于數組的知識，我們在后續的課程中會詳細展開。 #### 線性表案例 關于線性表，最高頻的問題都會圍繞數據順序的處理。我們在這里給出一些例子來幫助你更好地理解。 例 1，鏈表的翻轉。給定一個鏈表，輸出翻轉后的鏈表。例如，輸入1 ->2 -> 3 -> 4 ->5，輸出 5 -> 4 -> 3 -> 2 -> 1。 我們來仔細看一下這個問題的難點在哪里，這里有兩種情況： * 如果是數組的翻轉，這會非常容易。原因在于，數組在連續的空間進行存儲，可以直接求解出數組的長度。而且，數組可以通過索引值去查找元素，然后對相應的數據進行交換操作而完成翻轉。 * 但對于某個單向鏈表，它的指針結構造成了它的數據通路有去無回，一旦修改了某個指針，后面的數據就會造成失聯的狀態。為了解決這個問題，我們需要構造三個指針 prev、curr 和 next，對當前結點、以及它之前和之后的結點進行緩存，再完成翻轉動作。具體如下圖所示： ``` while(curr){ next = curr.next; curr.next = prev； prev = curr; curr = next; } ```  例 2，給定一個奇數個元素的鏈表，查找出這個鏈表中間位置的結點的數值。 這個問題也是利用了鏈表的長度無法直接獲取的不足做文章，解決辦法如下： * 一個暴力的辦法是，先通過一次遍歷去計算鏈表的長度，這樣我們就知道了鏈表中間位置是第幾個。接著再通過一次遍歷去查找這個位置的數值。 * 除此之外，還有一個巧妙的辦法，就是利用快慢指針進行處理。其中快指針每次循環向后跳轉兩次，而慢指針每次向后跳轉一次。如下圖所示。  ``` while(fast && fast.next && fast.next.next){ fast = fast.next.next; slow = slow.next; } ``` 例 3，判斷鏈表是否有環。如下圖所示，這就是一個有環的鏈表。  鏈表的快慢指針方法，在很多鏈表操作的場景下都非常適用，對于這個問題也是一樣。 假設鏈表有環，這個環里面就像是一個跑步賽道的操場一樣。經過多次循環之后，快指針和慢指針都會進入到這個賽道中，就好像兩個跑步選手在比賽。#加動圖#快指針每次走兩格，而慢指針每次走一格，相對而言，快指針每次循環會多走一步。這就意味著： * 如果鏈表存在環，快指針和慢指針一定會在環內相遇，即 fast == slow 的情況一定會發生。 * 反之，則最終會完成循環，二者從未相遇。 根據這個性質我們就能對鏈表是否有環進行準確地判斷了。如下圖所示：  #### 總結 好的，這節課的內容就到這里了。這一節的內容主要圍繞線性表的原理、線性表對于數據的增刪查操作展開。線性鏈表結構的每個結點，由數據的數值和指向下一個元素的指針構成。根據結構組合方式的不同，除了單向鏈表以外，還有雙向鏈表、循環鏈表以及雙向循環鏈表等變形。 經過我們的分析，鏈表在增、刪方面比較容易實現，可以在 O(1) 的時間復雜度內完成。但對于查找，不管是按照位置的查找還是按照數值條件的查找，都需要對全部數據進行遍歷。 線性表的價值在于，它對數據的存儲方式是按照順序的存儲。當數據的元素個數不確定，且需要經常進行數據的新增和刪除時，那么鏈表會比較合適。鏈表的翻轉、快慢指針的方法，是你必須掌握的內容。 #### 練習題 最后我們留一道課后練習題。給定一個含有 n 個元素的鏈表，現在要求每 k 個節點一組進行翻轉，打印翻轉后的鏈表結果。其中，k 是一個正整數，且可被 n 整除。 例如，鏈表為 1 -> 2 -> 3 -> 4 -> 5 -> 6，k = 3，則打印 321654。我們給出一些提示，這個問題需要使用到鏈表翻轉的算法。