記錄是一組相關數據項的集合，用於描述一個對象在某方面的屬性。一個記錄應包含哪些數據項，取決於需要描述對象的哪個方面。鏈式結構記錄是指記錄採用鏈式結構來進行存儲，這裡記錄可以是連續的，也可以是不連續的。
基本介紹
- 中文名：鏈式結構記錄
- 外文名：chained structure record
- 學科：計算機
- 定義：記錄採用鏈式結構來進行存儲
- 有關術語：記錄
- 領域：資料庫
簡介,鍊表,雙向鍊表,循環鍊表,單向鍊表,
簡介
鏈式結構記錄是指記錄採用鏈式結構來進行存儲。鏈式存儲結構，一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的，也可以是不連續的)，即不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的弱點，但同時也失去了順序表可隨機存取的優點。鏈式結構一般採用鍊表表示，鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。
鍊表
鍊表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。
使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機記憶體空間，實現靈活的記憶體動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。
在計算機科學中，鍊表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的連結（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁碟上順序，數據的訪問往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（連結）。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。
雙向鍊表
循環鍊表
循環鍊表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鍊表中的任何一個結點出發都能找到任何其他結點。循環鍊表的操作和單鍊表的操作基本一致，差別僅僅在於算法中的循環條件有所不同。
單向鍊表
鍊表中最簡單的一種是單向鍊表，它包含兩個域，一個信息域和一個指針域。這個連結指向列表中的下一個節點，而最後一個節點則指向一個空值。
一個單向鍊表的節點被分成兩個部分。第一個部分保存或者顯示關於節點的信息，第二個部分存儲下一個節點的地址。單向鍊表只可向一個方向遍歷。
鍊表最基本的結構是在每個節點保存數據和到下一個節點的地址，在最後一個節點保存一個特殊的結束標記，另外在一個固定的位置保存指向第一個節點的指針，有的時候也會同時儲存指向最後一個節點的指針。一般查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外保存起來，然後直接訪問。當然如果只是訪問數據就沒必要了，不如在鍊表上儲存指向實際數據的指針。這樣一般是為了訪問鍊表中的下一個或者前一個（需要儲存反向的指針，見下面的雙向鍊表）節點。
相對於下面的雙向鍊表，這種普通的，每個節點只有一個指針的鍊表也叫單向鍊表，或者單鍊表，通常用在每次都只會按順序遍歷這個鍊表的時候（例如圖的鄰接表，通常都是按固定順序訪問的）。
