線性表（List）：是零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列，它是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。

前提說(shuō)明，本篇文章只會(huì)介紹線性表相關(guān)概念的理論知識(shí)，對(duì)線性表操作的算法實(shí)現(xiàn)，會(huì)單獨(dú)用一篇文章來(lái)介紹，現(xiàn)已完成，感興趣請(qǐng)戳：線性表的算法實(shí)現(xiàn)之JS

基本概念和特點(diǎn)

線性表元素的個(gè)數(shù) n （n ≥ 0）定義為線性表的長(zhǎng)度，當(dāng) n = 0 時(shí)，稱(chēng)為空表。

在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（item）組成，在這種情況下，常把數(shù)據(jù)元素稱(chēng)為記錄（record），含有大量記錄的線性表又稱(chēng)為文件（file）。

線性表的常見(jiàn)操作有：創(chuàng)建和初始化、重置為空表、插入數(shù)據(jù)、刪除數(shù)據(jù)、合并線性表等。

當(dāng)數(shù)據(jù)元素為非空有限集合時(shí)，線性結(jié)構(gòu)具有如下特點(diǎn)：

• 存在唯一的一個(gè)被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素
• 存在唯一的一個(gè)被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素
• 除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)
• 除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼

順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，它的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。由于線性表的每個(gè)數(shù)據(jù)元素的類(lèi)型都相同，所以我們常用一維數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。

相關(guān)概念

通過(guò)以下三個(gè)屬性來(lái)描述順序存儲(chǔ)結(jié)構(gòu)：

• 存儲(chǔ)空間的起始位置：即數(shù)組 data，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置
• 線性表的最大存儲(chǔ)容量：數(shù)組長(zhǎng)度 MaxSize
• 線性表的當(dāng)前長(zhǎng)度：Length

要注意區(qū)分數(shù)據(jù)長(zhǎng)度和線性表長(zhǎng)度這兩個(gè)概念，數(shù)據(jù)的長(zhǎng)度即數(shù)組的長(zhǎng)度，是存放線性表的存儲(chǔ)空間的長(zhǎng)度，存儲(chǔ)分配后這個(gè)量就一般是不變的；而線性表長(zhǎng)度是線性表中數(shù)據(jù)元素的個(gè)數(shù)，是會(huì)隨著線性表的插入和刪除操作進(jìn)行相應(yīng)變化的。所以，線性表的長(zhǎng)度應(yīng)該小于等于數(shù)組長(zhǎng)度。

存儲(chǔ)器中每個(gè)存儲(chǔ)單元都有自己的編號(hào)，這個(gè)編號(hào)稱(chēng)之為地址。對(duì)于每個(gè)數(shù)據(jù)元素來(lái)說(shuō)，不管它是整型、實(shí)型還是字符型，它都是需要占用一定的存儲(chǔ)單元空間，我們假設(shè)占用的都是 c 個(gè)存儲(chǔ)單元，那么線性表中第 i+1 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和第 i 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿(mǎn)足下列關(guān)系：

LOC(a_i+1) = LOC(a_i) + c

其中 LOC 表示的是獲得存儲(chǔ)位置的函數(shù)。由此我們可得對(duì)于第 i 個(gè)數(shù)據(jù)元素 a_i的存儲(chǔ)位置可以由a₁推算得出

LOC(a_i) = LOC(a₁) + (i - 1) * c

通過(guò)這個(gè)公式，我們可以隨時(shí)算出線性表中任意位置的地址，也可以算出對(duì)每個(gè)線性表位置的存入或取出，算法復(fù)雜度都是一樣的，為 O(1)，我們把具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱(chēng)為隨機(jī)存取結(jié)構(gòu)。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
• 可以快速地存取表中任一位置的元素

缺點(diǎn)：

• 插入和刪除操作需要移動(dòng)大量元素
• 當(dāng)線性表長(zhǎng)度變化大時(shí)，難以確定存儲(chǔ)空間的容量
• 造成存儲(chǔ)空間的“碎片”

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，這意味著這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。

線性鏈表

為了表示每個(gè)數(shù)據(jù)元素 a_i 與其直接后繼數(shù)據(jù)元素 a_i+1 之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素 a_i 來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需要存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱(chēng)為指針域。指針域中存儲(chǔ)的信息稱(chēng)做指針或鏈。這兩部分信息組成數(shù)據(jù)元素 a_i 的存儲(chǔ)映像，稱(chēng)為結(jié)點(diǎn)（Node）。

n 個(gè)結(jié)點(diǎn)（a_i的存儲(chǔ)映像）鏈結(jié)成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，我們又稱(chēng)之為線性鏈表或單鏈表。單鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。

我們把鏈接中第一個(gè)結(jié)點(diǎn)的指針（即存儲(chǔ)位置）叫做頭指針；最后一個(gè)結(jié)點(diǎn)的指針為“空”（通常用 NULL 或 ^{^ 符號(hào)表示）。}

有時(shí)我們?yōu)榱朔奖銓?duì)鏈表進(jìn)行操作，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長(zhǎng)度等附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。

注意區(qū)別頭指針和頭結(jié)點(diǎn)：
頭指針：

• 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針
• 頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字
• 無(wú)論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必要元素

頭結(jié)點(diǎn)：

• 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義（也可存放鏈表的長(zhǎng)度）
• 有了頭結(jié)點(diǎn)，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其他結(jié)點(diǎn)的操作就統(tǒng)一了
• 頭結(jié)點(diǎn)不一定是鏈表必須元素

靜態(tài)鏈表

對(duì)于早期的編程高級(jí)語(yǔ)言，如：Basic、Fortran 由于沒(méi)有指針，那我們?cè)撛趺疵枋鏊鼈兊膯尉€表呢？我們的做法是用數(shù)組來(lái)代替指針，把這種用數(shù)組描述的鏈表稱(chēng)為靜態(tài)鏈表，這種描述方法還有起名叫做游標(biāo)實(shí)現(xiàn)法。

我們對(duì)數(shù)組的第一個(gè)和最后一個(gè)元素作為特殊元素處理，不存數(shù)據(jù)。

循環(huán)鏈表

將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表行程一個(gè)環(huán)，這種頭尾相接的單鏈表稱(chēng)為單循環(huán)鏈表，簡(jiǎn)稱(chēng)循環(huán)鏈表（circular linked list）。

雙向鏈表

雙向鏈表（double linked list）是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)。