鏈結串列
数据结构,这是一个线性的数据元素的集合,称为节点,每一个指向下一个节点的指针 / 維基百科,自由的 encyclopedia
在電腦科學中,鏈結串列(英語:Linked list)是一種常見的基礎資料結構,是一種線性序列,但是並不會按線性的順序儲存資料,而是在每一個節點裡存到下一個節點的指標。由於不必須按順序儲存,鏈結串列在插入的時候可以達到O(1)的複雜度,比另一種線性序列順序表快得多,但是尋找一個節點或者存取特定編號的節點則需要O(n)的時間,而順序表相應的時間複雜度分別是O(logn)和O(1)。
此條目沒有列出任何參考或來源。 (2011年11月8日) |
使用鏈結串列結構可以克服陣列鏈結串列需要預先知道資料大小的缺點,鏈結串列結構可以充分利用電腦記憶體空間,實作靈活的記憶體動態管理。但是鏈結串列失去了陣列隨機讀取的優點,同時鏈結串列由於增加了結點的指標域,空間開銷比較大。
在電腦科學中,鏈結串列作為一種基礎的資料結構可以用來產生其它類型的資料結構。鏈結串列通常由一連串節點組成,每個節點包含任意的實例資料(data fields)和一或兩個用來指向上一個/或下一個節點的位置的鏈結("links")。鏈結串列最明顯的好處就是,常規陣列排列關聯專案的方式可能不同於這些資料專案在記憶體或磁碟上順序,資料的存取往往要在不同的排列順序中轉換。而鏈結串列是一種自我指示資料型態,因為它包含指向另一個相同類型的資料的指標(鏈結)。鏈結串列允許插入和移除表上任意位置上的節點,但是不允許隨機存取。鏈結串列有很多種不同的類型:單向鏈結串列,雙向鏈結串列以及環狀鏈結串列。
鏈結串列可以在多種程式語言中實作。像Lisp和Scheme這樣的語言的內建資料型態中就包含了鏈結串列的存取和操作。程式語言或物件導向語言,如C/C++和Java依靠易變工具來產生鏈結串列。