導(dǎo)言： 算法特性：有窮性、確定性、可行性、輸入、輸出。時(shí)間復(fù)雜度：T(n) = O(f(n))、空間復(fù)雜度：S(n) = O(f(n))

定義

若干個(gè)數(shù)據(jù)元素的有限序列。個(gè)人覺得可以類比Objective-C中的NSArray（有索引）、NSSet（無索引），對(duì)比理解就好。

線性表的順序?qū)崿F(xiàn)就是存儲(chǔ)地址連續(xù)，好比NSArray（隨機(jī)存儲(chǔ)特性）。鏈?zhǔn)綄?shí)現(xiàn)其實(shí)就是每個(gè)節(jié)點(diǎn)保存自己數(shù)據(jù)的同時(shí)，保留了相鄰節(jié)點(diǎn)的指針。

順序?qū)崿F(xiàn)的線性表：

隨機(jī)存儲(chǔ)（因?yàn)檫壿嬒噜彽膬蓚€(gè)數(shù)據(jù)元素的物理地址也相鄰），因?yàn)橹懒耸讉€(gè)數(shù)據(jù)元素的地址，所以每一個(gè)元素的地址都知道了，直接根據(jù)地址取任意一個(gè)元素（T(n) = O(1)）。對(duì)于，順序?qū)崿F(xiàn)的線性表，增刪查檢中比較吃虧的是插入和刪除。（在第i 個(gè)元素后插入一個(gè)新的元素或者刪除第i個(gè)元素，i后面的所有元素均需要移動(dòng)位置，T(n) = O(n)）

鏈?zhǔn)綄?shí)現(xiàn)的線性表：

無法隨機(jī)存儲(chǔ)（因?yàn)檫壿嬒噜彽膬蓚€(gè)數(shù)據(jù)元素的物理地址不相鄰），查找必須遍歷鏈表T(n) = O(n)。在第i 個(gè)節(jié)點(diǎn)之前插入一個(gè)新的節(jié)點(diǎn)，必須先查找到第i-1個(gè)節(jié)點(diǎn)T(n) = O(n)，然后再插入T(n) = O(1),所以插入刪除的T(n) = O(n)。

雙向鏈表對(duì)比于單向鏈表，在已知第i個(gè)數(shù)據(jù)元素的前提下，查找下一個(gè)元素，時(shí)間復(fù)雜度都是O(1)，但是查找上一個(gè)數(shù)據(jù)元素單向的時(shí)間復(fù)雜度是O(n)，因?yàn)闆]有指向上一個(gè)數(shù)據(jù)元素的指針，必須遍歷鏈表，找到指針指向自己的元素。對(duì)于雙向就不一樣，它存有上一個(gè)數(shù)據(jù)元素的指針。

合并：

無序：

兩個(gè)線性表LA、LB合并（不能含有相同元素）｜T(n) = O(n^2)

如果采用快速排序先對(duì)數(shù)組進(jìn)行排序 ｜ T(n) = O(n*log(n))

有序：

兩個(gè)線性表LA、LB合并（不能含有相同元素）｜T(n) = O(2n)

個(gè)人總結(jié)：

常規(guī)的線性表（順序?qū)崿F(xiàn)、鏈?zhǔn)綄?shí)現(xiàn)）多用來存儲(chǔ)數(shù)據(jù)，在Objective-C中對(duì)應(yīng)的NSArray就是如此。不過鏈?zhǔn)綄?shí)現(xiàn)也提供了一些思路：比如責(zé)任鏈的設(shè)計(jì)模式（雙向鏈表）。終歸到底，還是看個(gè)人把問題轉(zhuǎn)換為什么數(shù)據(jù)結(jié)構(gòu)去處理，P = (C , R)這個(gè)表達(dá)式很重要。

注：上述總結(jié)純屬本人對(duì)數(shù)據(jù)結(jié)構(gòu)掃盲的總結(jié)，不對(duì)之處希望指正。