算法系列教程05 - 你真的瞭解線性表嗎？
閱讀本文大概需要 7 分鐘。
線性表是資料結構最最基本的一個概念，可是你真的瞭解線性表嗎？
線性表的儲存方式是什麼？棧和佇列是線性表嗎？
如果能正確地回答這兩個問題，那麼你就不用浪費時間看本文的內容了。否則，不管你覺得線性表是多麼基礎的東西都還是花幾分鐘把本文看完吧。
本系列教程的接下來幾篇文章都是講資料結構的 基礎 ，有人已經學過並掌握了，也有人沒學過或者早已忘記了。不管怎麼樣，就當是複習一下吧。對於還沒有系統學過資料結構的同學，正好可以用碎片時間快速系統地學習一下。本系列教程關於資料結構的知識不會講每種資料結構的程式碼實現，因為幾乎所有語言都內建實現好了。
基本概念
在本文開始之前，我們先了解一下線性表、順序表和連結串列這三個基本概念：
線性表 （Linear List）：線性表是最基礎、最簡單、最常用的一種基本資料結構。線性表儲存的每個資料稱為一個元素。一個線性表是 n 個具有相同特性的元素的有限序列。線性表有兩種儲存方式：順序儲存方式和鏈式儲存方式。
順序表 （Sequence List）：順序表就是線性表的順序儲存方式，以陣列的形式儲存。陣列的順序儲存方式使得邏輯上相鄰的元素，其在物理儲存單元中也是相鄰的。並且陣列是靜態分配的，即在使用陣列之前需要分配固定大小的空間。可以通過索引直接得到陣列中的元素，即獲取陣列中元素的時間複雜度為 O(1)。
連結串列 （Linked List）：連結串列就是線性表的鏈式儲存方式。連結串列中的元素在記憶體中不是連續分配的，即邏輯上相鄰的兩個元素在物理儲存單元中不一定是相鄰的。而且它的分配是動態的，即建立連結串列時不需要事先指定大小。連結串列每個元素都過指標來指向下一個元素地址，將連結串列中的元素有序地串起來。
綜上，線性表有順序和鏈式兩種儲存方式，分別由順序表和連結串列這兩種資料結構實現。
順序表很簡單，它就是下標和元素一一對應的陣列，沒什麼好講的。下面重點講一下連結串列。
連結串列
連結串列（Linked List）是一種各元素按線性排列的資料結構。與陣列不同的是，陣列的線性順序由陣列的下標決定，連結串列的順序是由各個元素的指標來決定的。連結串列主要分為三種：
-
單向連結串列（Singly Linked List）
-
雙向連結串列（Doubly Linked List）
-
迴圈連結串列（Circular Linked List）
三種連結串列的元素節點都包含資料和指標，它們的操作有插入、刪除和查詢。當其中一個節點被刪除或在節點前插入一個新節點時，都需要改變相關節點的指標指向。
單向連結串列
單向連結串列又稱單鏈表，是連結串列中最簡單的一種。一個單向連結串列的元素節點被分成兩個部分。第一個部分儲存節點的資訊，第二個部分儲存下一個節點的地址，最後一個節點則指向一個空值。一般第一個節點稱為鏈頭，最後一個節點稱為鏈尾。單向連結串列只可向一個方向遍歷。下面是單向連結串列的簡單示意圖：
一般查詢一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外儲存起來，然後直接訪問。
雙向連結串列
雙向連結串列又稱雙鏈表。相對於一個節點只有一處指標的單鏈表，雙鏈表中的一個節點有前、後兩個指標，通用分別用 Prev 和 Next 表示。Prev 指向前一個節點，稱為前驅，Next 指向後一個節點，稱為後繼。第一個節點的 Prev 指向空值或者空列表，最後一個節點的 Next 也指向空值或者空列表。下面是雙向連結串列的簡單示意圖：
查詢一個結點可以從任何結點開始，每次可以訪問節點的前一個節點也可以訪問後一個節點。
迴圈連結串列
迴圈連結串列和單向連結串列、雙向連結串列基本一樣，區別是它的首節點和尾節點連線在了一起，即尾節點的 Next 指向的是首節點而不是空值，這種操作在單向和雙向連結串列中皆可實現。迴圈連結串列可以看著是無頭無尾單向或雙向連結串列。下面是迴圈連結串列的單向與雙向實現示意圖：
迴圈連結串列是閉環的，所以沒有鏈頭和鏈尾的說法。迴圈連結串列的設計對於演算法插入操作更加容易，因為不需要考慮鏈頭和鏈尾的情況。
到這我們已經知道線性表儲存的儲存方式了。接下來我們再來看看堆疊和佇列這兩種資料結構。
棧和佇列
棧和佇列是我們常用的兩種資料結構，棧的後進先出和佇列的先進先出，我們早已耳熟能詳了。其實知道這點我覺得就夠了，只是你可能會好奇它們是不是屬於線性表呢？我先不直接回答這個問題，我們還是先看看棧和佇列是都是什麼樣的結構和有什麼操作吧。
棧
棧（Stack），又稱為堆疊，它實現的是一種 後進先出 （Last In First Out, LIFO）策略，被刪除的是最後插入的元素。棧的插入操作稱為 壓入 （Push），它的刪除操作稱為 彈出 （Pop）。棧有棧底（Bottom）和棧頂（Top），壓入和彈出都是在棧頂進行操作。下面是棧的簡單示意圖：
從圖中我們可以看到，棧中的元素是線性儲存的，元素的組成其實就是一個線性表，只是它被限制了只能在一端進行進出操作。棧既然是線性表，在具體應用中就可以用順序表或者連結串列來實現。
佇列
佇列（Queue）實現的是一種 先進先出 （First In First Out, FIFO）策略，被刪除的是在集合中最先插入的元素。佇列的插入操作稱為 入隊 （Enqueue），刪除操作稱為 出隊 （Dequeue）。佇列有隊頭（Head）和隊尾（Tail），當有一個新元素入隊時，它會被放在隊尾的位置。下面是佇列的簡單示意圖：
和棧一樣，佇列也是一種線性表，只是被限制在兩端進行進出操作，在具體應用中也可以用順序表或者連結串列來實現。
總結
線性表是一個大的概念。從儲存方式上來說它有順序儲存和鏈式儲存，分別對應順序表和連結串列兩種資料結構。棧和佇列都屬於線性表中的一種特例。雖都是基礎知識，但看完本文，你有些許收穫嗎？反正我是挺有收穫的。
本文圖片來源：
http://t.cn/EZUNyFi
http://t.cn/EZUCgaV
本文參考：
演算法導論，第三版，第 10 章