1.5.1　順序表與鏈表

線性表是最簡單、最常用的一種數據結構，簡言之，一個線性表是n（n≥0）個數據元素的有限序列。

順序表和鏈表是常用的兩種數據結構，也是線性結構中最簡單的實例。兩者最大的區別是：順序表是隨機存取，而鏈表是順序存取的。

1．順序表

把線性表的元素按邏輯次序依次存放在一組地址連續的存儲單元，用這種方法存儲的線性表簡稱為順序表。

順序表的特點是邏輯上相鄰的數據元素其物理位置也相鄰，表中第i個元素a_i的存儲位置可用一個簡單且直觀的公式表示如下：

LOC（a_i）=LOC（a₁）+L×（i-1），1≤i≤n

其中，L是每個元素占用的存儲單元的個數；LOC（a₁）是第一個元素a₁的存儲地址（簡稱為基地址）；LOC（a_i）是元素a_i（2≤i≤n）的存儲地址。

由此可見，只要確定了順序表的起始存儲位置，表中任一數據元素都可隨機存取。所以順序表是一種隨機存取的存儲結構，其示意圖如圖1-3所示。

顯然，在這種存儲方式下，容易實現對表的遍歷。如果要在表的尾部插入一個新元素，也很容易。但是，要在表的中間位置插入一個新元素，就必須先將其后面的所有元素都后移一個單元，才能騰出新元素所需的位置。執行刪除運算的情形類似，如果被刪除的元素不是表中最后一個元素，則必須將它后面的所有元素前移一個位置，以填補由于刪除所造成的空缺。由于高級程序設計語言中的數組類型也有隨機存取的特性，因此，通常采用數組來描述順序表。

2．鏈表

鏈表是線性表的另一種存儲方式，其特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的），它由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。

鏈表的形式主要有線性鏈表（或單鏈表）、循環鏈表和雙向鏈表。

（1）在線性鏈表中，每個結點包括兩部分：一個是存儲數據元素信息的數據域；另一個是存儲直接后繼存儲位置的指針域，該域表示了元素與其直接后繼元素之間的邏輯關系，域中存儲的信息稱作指針或鏈。n個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于此鏈表的每個結點中只包含一個指針域，故稱為線性鏈表或單鏈表。

用鏈表來表示線性表時，數據元素之間的邏輯關系是由結點中的指針指示的，邏輯上相鄰的兩個元素其存儲的物理位置不要求緊鄰。因此，在使用鏈表時，人們關心的是它所表示的線性表中數據元素的邏輯順序，而不是每個數據元素在存儲器中的實際位置。那么如何設計鏈表的邏輯結構圖呢？通常把鏈表畫成用箭頭相鏈接的結點的序列，結點之間的箭頭表示鏈域中的指針。例如線性表（a₁，a₂，a₃）的線性鏈表存儲結構如圖1-4所示。

其中，H稱為頭指針，它指示鏈表中第一個結點的存儲位置，整個鏈表的存取必須從頭指針開始進行。由于最后一個元素a₃沒有直接后繼，因此它的指針域設置為空（NULL）。

（2）由于每次對線性鏈表進行存取都必須從頭指針開始，這給元素的查找及表的合并等操作帶來了不便，為了克服該缺點，循環鏈表順應而生。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。為此，從表中任一結點出發均可找到表中其他結點。進行表的合并時，僅需將一個表的表尾和另一個表的表頭相接即可。

（3）以上兩種鏈式存儲結構的結點中只有一個指示直接后繼的指針域，因此從某個結點出發只能順指針往后尋找其他結點。若要尋找某結點的直接前驅，則必須從表頭指針出發。換句話說，在單鏈表中，尋找某結點的直接后繼的執行時間為O（1），而尋找其直接前驅的執行時間則為O（n）。為了克服這種單向性的缺點，出現了雙向鏈表，其特點是每個結點中有兩個指針域，一個指向直接后繼；另一個指向直接前驅。

與順序表相比，鏈表在對空間的利用上較合理，且在實現數據元素的插入和刪除操作時，只需修改指針而不需要移動數據元素。因此，在很多場合下，它是線性表的首選存儲結構，但是它失去了順序表可隨機存取的優點。仁者見者，智者見智，讀者可根據實際情況選擇最合適的數據結構來使用。