鍊錶是什麼資料結構

鍊錶是一種實體儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是透過鍊錶中的指標連結順序來實現的；簡單來說，線性表的鍊式儲存結構產生的表，稱為「鍊錶」。鍊錶中每個資料元素都由兩部分組成：1、本身的訊息，稱為「資料域」；2、指向直接後繼的指針，稱為「指針域」。這兩部分資訊組成資料元素的儲存結構，稱為「結點」；n個結點透過指標域相互鏈接，組成一個鍊錶。

本教學操作環境：windows7系統、Dell G3電腦。

資料結構是電腦儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下，精心選擇的資料結構可以帶來更高的運作或儲存效率。資料結構往往與高效率的檢索演算法和索引技術有關。

資料結構中的鍊錶

鍊錶是一種實體儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是透過鍊錶中的指標連結次序來實現的。鍊錶由一系列結點（鍊錶中每一個元素稱為結點）組成，結點可以在運行時動態產生。

邏輯結構上一個挨一個的數據，在實際儲存時，並沒有像順序表那樣也相互緊挨著。恰恰相反，資料隨機分佈在記憶體中的各個位置，這種儲存結構稱為線性表的鍊式儲存。

由於分散存儲，為了能夠體現資料元素之間的邏輯關係，每個資料元素在儲存的同時，要配備一個指針，用於指向它的直接後繼元素，即每一個資料元素都指向下一個資料元素（最後一個指向NULL(空)）。

如上圖所示，當每一個資料元素都和它下一個資料元素用指標連結在一起時，就形成了一個鏈，這個鍊子的頭就位於第一個資料元素，這樣的儲存方式就是鍊式儲存。

線性表的鍊式儲存結構所產生的表，稱為「鍊錶」。

鍊錶中資料元素的組成

每個元素本身由兩部分組成：

• 本身的訊息，稱為「資料域」；

• 指向直接後繼的指針，稱為「指針域」。

這兩部分資訊組成資料元素的儲存結構，稱為「結點」。 n個結點透過指標域相互鏈接，組成一個鍊錶。

頭結點、頭指標與首元結點

頭結點：有時，在鍊錶的第一個結點之前會額外增設一個結點，結點的資料域一般不存放資料（有些情況下也可以存放鍊錶的長度等資訊），此結點稱為頭結點。

若頭結點的指標域為空（NULL），表示鍊錶是空表。頭結點對於鍊錶來說，不是必須的，在處理某些問題時，給鍊錶添加頭結點會使問題變得簡單。

首元結點：鍊錶中第一個元素所在的結點，它是頭結點後邊的第一個結點。

頭指標：永遠指向鍊錶中第一個結點的位置（如果鍊錶有頭結點，頭指標指向頭結點；否則，頭指標指向首元結點）。

頭結點和頭指針的區別：頭指針是指針，頭指針指向鍊錶的頭結點或者首元結點；頭結點是一個實際存在的結點，它包含有資料域和指標域。兩者在程式中的直接體現就是：頭指標只聲明而沒有分配儲存空間，頭結點進行了聲明並分配了一個結點的實際物理記憶體。

使用鍊錶結構可以克服陣列鍊錶需要預先知道資料大小的缺點，鍊錶結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鍊錶失去了數組隨機讀取的優點，同時鍊錶由於增加了結點的指標域，空間開銷比較大。鍊錶最明顯的好處是，常規數組排列關聯項目的方式可能不同於這些資料項目在記憶體或磁碟上順序，資料的存取往往要在不同的排列順序中轉換。

特點

線性表的鍊式儲存表示的特點是用一組任意的儲存單元儲存線性表的資料元素（這組儲存單元可以是連續的，也可以是不連續的）。因此，為了表示每個資料元素與其直接後繼資料元素之間的邏輯關係，對資料元素來說，除了儲存本身的資訊之外，還需儲存一個指示其直接後繼的資訊（即直接後繼的存儲位置）。由這兩部分資訊組成一個"結點"（如下圖所示），表示線性表中一個資料元素。線性表的鍊式儲存表示，有一個缺點就是要找一個數，必須從頭開始找起，十分麻煩。

根據情況，也可以自己設計鍊錶的其它擴展。但是一般不會在邊上附加數據，因為鍊錶的點和邊基本上是一一對應的（除了第一個或最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鍊錶支援在鍊錶的一段中把前和後指針反向，反向標記加在邊上可能會更方便。

對於非線性的鍊錶，可以參見相關的其他資料結構，例如樹、圖。另外有一種基於多個線性鍊錶的資料結構：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二元樹一樣。

其中儲存資料元素資訊的域稱為資料域（設網域為data），儲存直接後繼儲存位置的域稱為指標域（設網域為next）。指標域中儲存的資訊又稱做指標或鏈。

由分別表示,，…，的N 個結點依次相鏈構成的鍊錶，稱為線性表的鍊式存儲表示，由於此類鍊錶的每個結點中只包含一個指針域，故又稱單鍊錶或線性鍊錶。

鍊錶插入和移除節點

鍊錶允許插入和移除表上任意位置上的節點，但不允許隨機存取。

1、在鍊錶中插入結點

• 鍊錶中插入頭結點，依插入位置的不同，分為3種：

• 插入到鍊錶的首部，也就是頭結點和首元結點中間；

• 插入到鍊錶中間的某個位置；

• 插入到鍊錶最末端；

#雖然插入位置有差別，都使用相同的插入手法。分成兩步，如上圖所示：

• 將新結點的next指標指向插入位置後的結點；

• ##將插入位置前的結點的next指標指向插入結點；

提示：在做插入操作時，首先要找到插入位置的上一個結點，圖4中，也就是找到結點1，對應的結點2 可透過結點1 的next 指針表示，這樣，先進行步驟1，後進行步驟2，實現過程中不需要添加其他輔助指針。

2、從鍊錶中刪除節點

當需要從鍊錶中刪除某個結點時，需要進行兩步驟操作：

• 將結點從鍊錶中摘下來;

• 手動釋放掉結點，回收被結點佔用的記憶體空間;

更多相關知識，請訪問

常見問題欄位！

以上是鍊錶是什麼資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！