鍊錶是什麼

鍊錶是一種實體儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是透過鍊錶中的指標連結次序實現的。鍊錶由一系列結點（鍊錶中每一個元素稱為結點）組成，結點可以在運行時動態產生。每個結點包括兩個部分：一個是儲存資料元素的資料域，另一個是儲存下一個結點位址的指標域。相較於線性表順序結構，操作複雜。由於不必須按順序存儲，鍊錶在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或訪問特定編號的節點則需要O(n)的時間，而線性表和順序表對應的時間複雜度分別是O(logn)和O(1)。

使用鍊錶結構可以克服陣列鍊錶需要預先知道資料大小的缺點，鍊錶結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鍊錶失去了數組隨機讀取的優點，同時鍊錶由於增加了結點的指標域，空間開銷比較大。鍊錶最明顯的好處是，常規數組排列關聯項目的方式可能不同於這些資料項目在記憶體或磁碟上順序，資料的存取往往要在不同的排列順序中轉換。鍊錶允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊錶有很多種不同的類型：單向鍊錶，雙向鍊錶以及循環鍊錶。鍊錶可以在多種程式語言中實現。像Lisp和Scheme這樣的語言的內建資料型別中就包含了鍊錶的存取和操作。程式語言或物件導向語言，如C,C 和Java則依賴易變工具來產生鍊錶。

特點

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

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

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

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

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

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