線性表結構是最常用且最簡單的一種數據結構。簡言之，一個線性表是n個數據元素的有限序列。至於每個數據元素的具體含義，在不同的情況下各不相同，它可以是一個數或一個符號，也可以是一頁書，甚至其他更複雜的信息。在稍複雜的線性表中，一個數據元素可以由若干個數據項組成。在這種情況下，常把數據元素稱為記錄，含有大量記錄的線性表又稱檔案。
基本介紹
- 中文名：線性表結構
- 外文名：Linear-list Structure
- 學科：計算機
- 定義：是n個數據元素的有限序列
- 領域：數據結構
- 有關術語：順序表、鍊表
簡介,順序表,鍊表,雙向鍊表,循環鍊表,單向鍊表,結構特點,
簡介
線性表結構是n個數據元素的有限序列，是一個種線性結構。線性結構的特點是：在數據元素的非空有限集中，(1)存在唯一的一個被稱做“第一個”的數據元素；(2)存在惟一的一個被稱做“最後一個”的數據元素；(3)除第一個之外，集合中的每個數據元素均只有一個前驅；(4)除最後一個之外，集合中每個數據元素均只有一個後繼。常見的線性表結構有順序表、鍊表。
順序表
存儲結構
/* 線性表的動態分配順序存儲結構 */
#define LIST_INIT_SIZE 10 /* 線性表存儲空間的初始分配量 */
#define LIST_INCREMENT 2 /* 線性表存儲空間的分配增量 */
typedef struct
{
ElemType *elem; /* 存儲空間基址 */
int length; /* 當前長度 */
int listsize; /* 當前分配的存儲容量(以sizeof(ElemType)為單位) */
}SqList;
鍊表
鍊表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。
使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機記憶體空間，實現靈活的記憶體動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。
在計算機科學中，鍊表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的連結（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁碟上順序，數據的訪問往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（連結）。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。
雙向鍊表
循環鍊表
循環鍊表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鍊表中的任何一個結點出發都能找到任何其他結點。循環鍊表的操作和單鍊表的操作基本一致，差別僅僅在於算法中的循環條件有所不同。
單向鍊表
鍊表中最簡單的一種是單向鍊表，它包含兩個域，一個信息域和一個指針域。這個連結指向列表中的下一個節點，而最後一個節點則指向一個空值。
一個單向鍊表的節點被分成兩個部分。第一個部分保存或者顯示關於節點的信息，第二個部分存儲下一個節點的地址。單向鍊表只可向一個方向遍歷。
鍊表最基本的結構是在每個節點保存數據和到下一個節點的地址，在最後一個節點保存一個特殊的結束標記，另外在一個固定的位置保存指向第一個節點的指針，有的時候也會同時儲存指向最後一個節點的指針。一般查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外保存起來，然後直接訪問。當然如果只是訪問數據就沒必要了，不如在鍊表上儲存指向實際數據的指針。這樣一般是為了訪問鍊表中的下一個或者前一個（需要儲存反向的指針，見下面的雙向鍊表）節點。
相對於下面的雙向鍊表，這種普通的，每個節點只有一個指針的鍊表也叫單向鍊表，或者單鍊表，通常用在每次都只會按順序遍歷這個鍊表的時候（例如圖的鄰接表，通常都是按固定順序訪問的）。
結構特點
1.均勻性：雖然不同數據表的數據元素可以是各種各樣的，但對於同一線性表的各數據元素必定具有相同的數據類型和長度。
2.有序性：各數據元素線上性表中的位置只取決於它們的序號，數據元素之前的相對位置是線性的，即存在唯一的“第一個“和“最後一個”的數據元素，除了第一個和最後一個外，其它元素前面均只有一個數據元素(直接前驅)和後面均只有一個數據元素（直接後繼）。
