一.鏈表（靈活的內(nèi)存動(dòng)態(tài)管理鬼吵，反結(jié)構(gòu)：線性表順序結(jié)構(gòu)）

含義：一種物理存儲(chǔ)單元上非連續(xù)荣倾、非順序的存儲(chǔ)結(jié)構(gòu)枉证，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

生成：鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成符相，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。

結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域帘靡，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域淆攻。

特點(diǎn)：鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多已日，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間垛耳，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

缺點(diǎn)：

鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)飘千，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域堂鲜，空間開銷比較大。

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

鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)护奈，但是不允許隨機(jī)存取缔莲。

鏈表有很多種不同的類型：

1.單向鏈表：有一個(gè)缺點(diǎn)就是要找一個(gè)數(shù)，必須要從頭開始找起霉旗，十分麻煩痴奏。

2.雙向鏈表：

必須使其最后一個(gè)結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn)，而不是象單鏈表那樣置為NULL厌秒。

是判斷該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)读拆，當(dāng)鏈域值等于表頭指針時(shí)，說明已到表尾简僧。而非象單鏈表那樣判斷鏈域值是否為NULL建椰。

循環(huán)鏈表：結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個(gè)鏈域岛马，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址棉姐，一般稱之為右鏈域屠列；一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域伞矩。

優(yōu)化：

插入操作處理順序：中間節(jié)點(diǎn)的邏輯笛洛，后節(jié)點(diǎn)邏輯，前節(jié)點(diǎn)邏輯乃坤。按照這個(gè)順序處理可以完成任何鏈表的插入操作苛让。

刪除操作的處理順序：前節(jié)點(diǎn)邏輯，后節(jié)點(diǎn)邏輯湿诊，中間節(jié)點(diǎn)邏輯狱杰。

按照此順序可以處理任何鏈表的刪除操作。

如果不存在其中的某個(gè)節(jié)點(diǎn)略過即可厅须。

二.線性表

分類：

一般線性表：就是我們通常所說的“線性表”仿畸，可以自由的刪除或添加結(jié)點(diǎn)。

受限線性表：包括棧和隊(duì)列和字符串朗和，受限表示對(duì)結(jié)點(diǎn)的操作受限制错沽。

特點(diǎn)：

均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對(duì)于同一線性表的各數(shù)據(jù)元素必定具有相同的數(shù)據(jù)類型和長(zhǎng)度眶拉。

有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序號(hào)千埃，數(shù)據(jù)元素之前的相對(duì)位置是線性的，即存在唯一的“第一個(gè)“和“最后一個(gè)”的數(shù)據(jù)元素忆植，除了第一個(gè)和最后一個(gè)外放可，其它元素前面均只有一個(gè)數(shù)據(jù)元素(直接前驅(qū))和后面均只有一個(gè)數(shù)據(jù)元素（直接后繼）。

三.鏈表和線性表區(qū)別

1.數(shù)組是將元素在內(nèi)存中連續(xù)存放唱逢，由于每個(gè)元素占用內(nèi)存相同吴侦，可以通過下標(biāo)迅速訪問數(shù)組中任何元素。但是如果要在數(shù)組中增加一個(gè)元素坞古，需要移動(dòng)大量元素，在內(nèi)存中空出一個(gè)元素的空間劫樟，然后將要增加的元素放在其中痪枫。同樣的道理，如果想刪除一個(gè)元素叠艳，同樣需要移動(dòng)大量元素去填掉被移動(dòng)的元素奶陈。如果應(yīng)用需要快速訪問數(shù)據(jù)，很少或不插入和刪除元素附较，就應(yīng)該用數(shù)組吃粒。

2.鏈表恰好相反，鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的拒课，而是通過存在元素中的指針聯(lián)系到一起徐勃。比如：上一個(gè)元素有個(gè)指針指到下一個(gè)元素事示，以此類推，直到最后一個(gè)元素僻肖。如果要訪問鏈表中一個(gè)元素肖爵，需要從第一個(gè)元素開始，一直找到需要的元素位置臀脏。但是增加和刪除一個(gè)元素對(duì)于鏈表數(shù)據(jù)結(jié)構(gòu)就非常簡(jiǎn)單了劝堪，只要修改元素中的指針就可以了。如果應(yīng)用需要經(jīng)常插入和刪除元素你就需要用鏈表數(shù)據(jù)結(jié)構(gòu)了揉稚。

3.邏輯結(jié)構(gòu)和內(nèi)存存儲(chǔ)角度來看

(1) 從邏輯結(jié)構(gòu)角度來看

a, 數(shù)組必須事先定義固定的長(zhǎng)度（元素個(gè)數(shù)）秒啦，不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況。當(dāng)數(shù)據(jù)增加時(shí)搀玖，可能超出原先定義的元素個(gè)數(shù)帝蒿；當(dāng)數(shù)據(jù)減少時(shí)，造成內(nèi)存浪費(fèi)巷怜。

b,鏈表動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配葛超，可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況，且可以方便地插入延塑、刪除數(shù)據(jù)項(xiàng)绣张。（數(shù)組中插入、刪除數(shù)據(jù)項(xiàng)時(shí)关带，需要移動(dòng)其它數(shù)據(jù)項(xiàng)）

(2)從內(nèi)存存儲(chǔ)角度來看

a,(靜態(tài))數(shù)組從棧中分配空間, 對(duì)于程序員方便快速,但自由度小侥涵。

b, 鏈表從堆中分配空間, 自由度大但申請(qǐng)管理比較麻煩.