連結串列是一種物理儲存單元上非連續、非順序的儲存結構,資料元素的邏輯順序是透過連結串列中的指標連結次序實現的。連結串列由一系列結點(連結串列中每一個元素稱為結點)組成,結點可以在執行時動態生成。每個結點包括兩個部分:一個是儲存資料元素的資料域,另一個是儲存下一個結點地址的指標域。 相比於線性表順序結構,操作複雜。由於不必須按順序儲存,連結串列在插入的時候可以達到O(1)的複雜度,比另一種線性表順序錶快得多,但是查詢一個節點或者訪問特定編號的節點則需要O(n)的時間,而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。
使用連結串列結構可以克服陣列連結串列需要預先知道資料大小的缺點,連結串列結構可以充分利用計算機記憶體空間,實現靈活的記憶體動態管理。但是連結串列失去了陣列隨機讀取的優點,同時連結串列由於增加了結點的指標域,空間開銷比較大。連結串列最明顯的好處就是,常規陣列排列關聯專案的方式可能不同於這些資料專案在記憶體或磁碟上順序,資料的存取往往要在不同的排列順序中轉換。連結串列允許插入和移除表上任意位置上的節點,但是不允許隨機存取。連結串列有很多種不同的型別:單向連結串列,雙向連結串列以及迴圈連結串列。連結串列可以在多種程式語言中實現。像Lisp和Scheme這樣的語言的內建資料型別中就包含了連結串列的存取和操作。程式語言或面嚮物件語言,如C,C++和Java依靠易變工具來生成連結串列。
連結串列是一種物理儲存單元上非連續、非順序的儲存結構,資料元素的邏輯順序是透過連結串列中的指標連結次序實現的。連結串列由一系列結點(連結串列中每一個元素稱為結點)組成,結點可以在執行時動態生成。每個結點包括兩個部分:一個是儲存資料元素的資料域,另一個是儲存下一個結點地址的指標域。 相比於線性表順序結構,操作複雜。由於不必須按順序儲存,連結串列在插入的時候可以達到O(1)的複雜度,比另一種線性表順序錶快得多,但是查詢一個節點或者訪問特定編號的節點則需要O(n)的時間,而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。
使用連結串列結構可以克服陣列連結串列需要預先知道資料大小的缺點,連結串列結構可以充分利用計算機記憶體空間,實現靈活的記憶體動態管理。但是連結串列失去了陣列隨機讀取的優點,同時連結串列由於增加了結點的指標域,空間開銷比較大。連結串列最明顯的好處就是,常規陣列排列關聯專案的方式可能不同於這些資料專案在記憶體或磁碟上順序,資料的存取往往要在不同的排列順序中轉換。連結串列允許插入和移除表上任意位置上的節點,但是不允許隨機存取。連結串列有很多種不同的型別:單向連結串列,雙向連結串列以及迴圈連結串列。連結串列可以在多種程式語言中實現。像Lisp和Scheme這樣的語言的內建資料型別中就包含了連結串列的存取和操作。程式語言或面嚮物件語言,如C,C++和Java依靠易變工具來生成連結串列。