重學數據結構（二）：線性表

線性表（List）：是零個或多個數據元素的有限序列，它是最常用且最簡單的一種數據結構商佛。

前提說明喉钢，本篇文章只會介紹線性表相關概念的理論知識，對線性表操作的算法實現良姆，會單獨用一篇文章來介紹肠虽，現已完成，感興趣請戳：線性表的算法實現之JS

基本概念和特點

線性表元素的個數 n （n ≥ 0）定義為線性表的長度玛追，當 n = 0 時税课，稱為空表。

在較復雜的線性表中痊剖，一個數據元素可以由若干個數據項（item）組成韩玩，在這種情況下，常把數據元素稱為記錄（record）陆馁，含有大量記錄的線性表又稱為文件（file）啸如。

線性表的常見操作有：創(chuàng)建和初始化、重置為空表氮惯、插入數據叮雳、刪除數據、合并線性表等妇汗。

當數據元素為非空有限集合時帘不，線性結構具有如下特點：

存在唯一的一個被稱為“第一個”的數據元素
存在唯一的一個被稱為“最后一個”的數據元素
除第一個之外，集合中的每個數據元素均只有一個前驅
除最后一個之外杨箭，集合中的每個數據元素均只有一個后繼

順序存儲結構

線性表的順序存儲結構寞焙，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數據元素，它的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰互婿。由于線性表的每個數據元素的類型都相同捣郊，所以我們常用一維數組來實現順序存儲結構。

優(yōu)缺點

優(yōu)點：

無須為表示表中元素之間的邏輯關系而增加額外的存儲空間
可以快速地存取表中任一位置的元素

缺點：

插入和刪除操作需要移動大量元素
當線性表長度變化大時历筝，難以確定存儲空間的容量
造成存儲空間的“碎片”

鏈式存儲結構

鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續(xù)的廊谓，也可以是不連續(xù)的梳猪，這意味著這些數據元素可以存在內存未被占用的任意位置。

線性鏈表

為了表示每個數據元素 a_i 與其直接后繼數據元素 a_i+1 之間的邏輯關系蒸痹，對數據元素 a_i 來說春弥，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）叠荠。我們把存儲數據元素信息的域稱為數據域匿沛，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈榛鼎。這兩部分信息組成數據元素 a_i 的存儲映像逃呼，稱為結點（Node）。

n 個結點（a_i的存儲映像）鏈結成一個鏈表者娱，即為線性表的鏈式存儲結構抡笼，因為此鏈表的每個結點中只包含一個指針域，我們又稱之為線性鏈表或單鏈表黄鳍。單鏈表正是通過每個結點的指針域將線性表的數據元素按其邏輯次序鏈接在一起推姻。

我們把鏈接中第一個結點的指針（即存儲位置）叫做頭指針；最后一個結點的指針為“空”（通常用 NULL 或 ^{^^{符號表示）际起。}}

有時我們?yōu)榱朔奖銓︽湵磉M行操作拾碌，會在單鏈表的第一個結點前附設一個結點吐葱，稱為頭結點街望，頭結點的數據域可以不存儲任何信息校翔，也可以存儲如線性表的長度等附加信息，頭結點的指針域存儲指向第一個結點的指針灾前。

注意區(qū)別頭指針和頭結點：
頭指針：

頭指針是指鏈表指向第一個結點的指針防症，若鏈表有頭結點，則是指向頭結點的指針
頭指針具有標識作用哎甲，所以常用頭指針冠以鏈表的名字
無論鏈表是否為空蔫敲，頭指針均不為空，頭指針是鏈表的必要元素

頭結點：

頭結點是為了操作的統一和方便而設立的炭玫，放在第一元素的結點之前奈嘿，其數據域一般無意義（也可存放鏈表的長度）
有了頭結點，對在第一元素結點前插入結點和刪除第一結點吞加，其操作與其他結點的操作就統一了
頭結點不一定是鏈表必須元素

靜態(tài)鏈表

對于早期的編程高級語言裙犹，如：Basic、Fortran 由于沒有指針衔憨，那我們該怎么描述它們的單線表呢叶圃？我們的做法是用數組來代替指針，把這種用數組描述的鏈表稱為靜態(tài)鏈表践图，這種描述方法還有起名叫做游標實現法掺冠。

我們對數組的第一個和最后一個元素作為特殊元素處理，不存數據码党。

循環(huán)鏈表

將單鏈表中終端結點的指針端由空指針改為指向頭結點德崭，就使整個單鏈表行程一個環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表揖盘，簡稱循環(huán)鏈表（circular linked list）眉厨。

雙向鏈表

雙向鏈表（double linked list）是在單鏈表的每個結點中，再設置一個指向其前驅結點的指針域扣讼。所以在雙向鏈表中的結點都有兩個指針域缺猛，一個指向直接后繼，一個指向直接前驅椭符。