鏈表結構原理 與 數組模擬鏈表 的應用

**鏈表（linked list）**是我們最常使用的一種數據結構。在信息學競賽中，經常需要使用鏈表作為遍歷等操作使用的數據結構參與解題過程。這是因為鏈表具有自己的優點。用數組模擬鏈表，可以簡化鏈表的使用，從而使鏈表更好的為我們服務。如果您已經知道鏈表數據結構的原理，可以跳過第一部分直接查看與數組模擬鏈表有關的內容。

「鏈表」數據結構

什麼是鏈表？

**鏈表(linked list)**是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

線性表（鏈接到百度百科的「線性表」詞條）的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素與其直接後繼數據元素之間的邏輯關係，對數據元素來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。由這兩部分信息組成一個"結點"（如下圖所示），表示線性表中的一個數據元素。

數據域 data

指針域 next

其中存儲數據元素信息的域稱作數據域（設域名為data），存儲直接後繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。

鏈表具有快速插入與刪除的優點，還能在運行時動態分配內存空間。

實現快速插入與刪除（鏈表的優點）

和普通的數組相比，鏈表具有能夠快速插入和刪除元素而不改變其它元素排列順序的優點。 舉例：對於一個長度為 n 的元素集合，如果這個集合用普通的非鏈表結構線性表來存儲（如一維數組），那麼，向其中插入一個元素需要花費大量的時間複雜度。如，在第一個元素後插入一個新元素 A，那麼這個數組從原來的第二個元素開始，都需要全部向後移動一個位置。而如果採用鏈表結構，只需要在一個新的存儲空間中記錄新元素 A，並且將第一個元素的 next 域（其內容記為 point_old）修改為指向 A 的指針（記為 point_new），並將 A 的 next 域設置為 point_old 即可，這裡只需要簡單的 O(1) 算法。

示意圖如下。原鏈表內容：

_point_

內存地址A

內存地址B

內存地址C

_data_

1

2

3

_next_

B

C

_null_

（注：null 代表空，即無後續元素指針。下文所提到的 null 均代表空。）

插入2.5到第一個元素位置後的鏈表內容：

_point_

內存地址A

內存地址B

內存地址C

內存地址D

_data_

1

2

3

2.5

_next_

D

C

_null_

B

（注：null 代表空，即無後續元素指針。下文所提到的 null 均代表空。）

從一次插入操作中可以得知以下結論：

1、可以看出，我們並不需要在為新元素提供連續的存儲位置，而是隨意開闢了一個新的地址D，只是在第一個元素的 next 域中對後繼元素地址進行了修改，並在新元素的 next 域鏈回原先的後繼元素即可。

2、對於一個鏈表，它遍歷一次所需要的時間要長於普通的數組，因為每次遍歷一個元素，都不能簡單的通過線性移動獲得下一個元素的內存地址，而需要通過指針進行定位，但鏈表的遍歷仍然是線性的操作。因此，鏈表特別適合需要大量編輯、插入、刪除等操作的時候使用。如果僅僅需要遍歷等操作，則可以直接使用普通數組。

刪除操作和遍歷類似，在此不再贅述。

鏈表的遍歷

鏈表的遍歷是線性算法。開始的時候，指針 p 在第一個元素上。處理完 p 後，指針 p <- p^.next（這句話是類 Pascal 偽語言，意思是 把 p 所代表的元素的 next 域的指針賦值給 p）。也就是傳遞它的後繼元素地址。然後，繼續進行對p的遍歷，如此循環，直到 p ==  null。（對於 Pascal，null 為 nil，== 為 =）

遍歷的 Pascal 偽代碼：

p := first; // fisrt 存儲第一個元素的內存地址。

while (p<>nil) do

begin

//處理p代表的這個元素。

p := p^.next;

end;

數組模擬鏈表

我們簡單的介紹了鏈表的基礎知識。要發揮鏈表動態分配內存空間的優勢，需要使用指針建立鏈表。但是，在信息學競賽中，我們基本上不需要過多考慮動態空間分配，所以，使用數組模擬鏈表就可以很好的實現鏈表數據結構。

數組模擬鏈表，是一種半靜態鏈表，是鏈表的線性存儲，比鏈式存儲要簡單的多了。每個鏈表可以用一對數組或一個記錄數組表示，每個元素是有兩個數據域：分別是數據_data_ 域和下一個結點在數組中的位置_next_ 域（整型的）。這樣插入，刪除，遍歷等，都可以歸結到數組操作了，這就比鏈式存儲容易多了，卻不喪失鏈表快速插入刪除的優勢。以下所說的指針，都是模擬指針，代表某元素在數字中的位置。

下面是一個用數組模擬鏈表操作的簡單例子。

//By Ceeji
//From https://ceeji.net/blog
Program Example;
Const max=10000;
Type node=record
           data,next:longint;
          end;
Var table:array[1..max]of node;
    i,j,k: longint;
Begin
   // 加入初始元素
   table[1].data:=1;
   for i:=2 to 500 do
   begin
     table[i].data:=i;
     table[i-1].next:=i;
   end;
   table[500].next:=0;
   //在元素200後插入數據
   table[501].data:=-1;
   j:=table[200].next;
   table[200].next:=501;
   table[501].next:=j;
   //遍歷數據
   i:=1;
   while i<>0 do
   begin
      writeln(table[i].data);
      i:=table[i].next;
   end;
End.

如此簡短的代碼，就實現了數組模擬鏈表，它能夠很快插入和刪除數據（見代碼），和很快的遍歷，卻又非常易於編寫。

那麼，數組模擬列表有哪些應用呢？

數組模擬鏈表的應用

例 現有 n 個城市，給出他們之間有哪些城市之間有道路和道路的長度（大於0。如果不給出，說明這兩個城市之間沒有路）。求從城市1到城市 n 的最短路徑（編號從1開始）。（n≤5000，道路數量不超過 20000 個）。

分析 我們並不是要分析這個題目本身，而是要分析這個題目所使用的數據結構。在解決這個問題的時候，我們必須存儲所有的道路長度。在一種最大眾化的圖論的最短路算法中我們可以知道，我們需要不斷的遍歷從某一城市出發的到其它城市的所有道路。無疑，使用數組存儲最適合遍歷。假設使用數組A

代表 某兩個城市間的道路長度，那麼所需要的空間為 5000 * 5000 = 25,000,000 = 2.5 億。這是個巨大的數字，很多情況下我們無法承受，不是超時，就是內存溢出。

但是，如果我們採用數組B

存儲，（1..3分別代表某個道路的開始城市，結束城市，道路長度）空間問題解決了。因為最多需要空間為 20000 * 2 * 3。但是此時，我們要找從某個城市出發的道路，每次都需要遍歷最多 20000 * 2 個元素，去查找哪一個道路的開始城市為我們所需要的。顯然這是不現實的。（* 2 是因為本題目中的道路是沒有方向的，從A到B有一條道路，那麼從B到A也要重新存儲。）

此時，我們想到了鏈表。

我們使用數組C

存儲。C

代表 記錄以第i個城市為起始端的第一條道路的指針（整形）。那麼，我們能夠很輕易的遍歷到第一條道路，然後，我們把這些道路串成鏈表，就可以輕易的繼續遍歷到底。我們把存儲具體道路的鏈表數組記為D（類型 node，其中 每個 node 有兩個域 data 和 next，data 表示道路的結束城市的編號），那麼D數組最多才有 40000 個元素，80000 個整數。每當讀入一條道路，我們就把結束城市的編號加入D數組的尾部，並將這個指針插入到相對應的開始城市的道路鏈表的第一個位置（這個鏈表的頭是C

，i是開始城市編號），維護C數組（記錄第一條道路的指針），然後，如果原先已經插入過道路，讓新的道路的 next 掛接上第二個道路。那麼我們遍歷就方便多了。空間上可行，時間上也可行。

為什麼要插入到第一個位置？因為如果插入到其他位置，我們需要先遍歷到這個位置，然後才能插入。而第一個位置不需要遍歷，可以直接由 C 數組取出指針。

由於編程簡單，數組模擬鏈表是圖論、大規模數據遍歷、樹等數據結構最佳的存儲方式。