一带膀、線性表的順序存儲(chǔ)設(shè)計(jì)與實(shí)現(xiàn)（順序表）
1.1?? 順序存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)原理概要
順序存儲(chǔ)結(jié)構(gòu)底層是利用數(shù)組來實(shí)現(xiàn)的舀射，而數(shù)組可以存儲(chǔ)具有相同數(shù)據(jù)類型的元素集合，，當(dāng)我們創(chuàng)建一個(gè)數(shù)組時(shí)成黄，計(jì)算機(jī)操作系統(tǒng)會(huì)為該數(shù)組分配一塊連續(xù)的內(nèi)存塊，這也就意味著數(shù)組中的每個(gè)存儲(chǔ)單元的地址都是連續(xù)的逻杖，因此只要知道了數(shù)組的起始內(nèi)存地址就可以通過簡單的乘法和加法計(jì)算出數(shù)組中第n-1個(gè)存儲(chǔ)單元的內(nèi)存地址奋岁，就如下圖所示：
??通過上圖可以發(fā)現(xiàn)為了訪問一個(gè)數(shù)組元素，該元素的內(nèi)存地址需要計(jì)算其距離數(shù)組基地址的偏移量荸百，即用一個(gè)乘法計(jì)算偏移量然后加上基地址闻伶，就可以獲得數(shù)組中某個(gè)元素的內(nèi)存地址。其中c代表的是元素?cái)?shù)據(jù)類型的存儲(chǔ)空間大小够话，而序號(hào)則為數(shù)組的下標(biāo)索引蓝翰。
整個(gè)過程需要一次乘法和一次加法運(yùn)算，因?yàn)檫@兩個(gè)操作的執(zhí)行時(shí)間是常數(shù)時(shí)間女嘲，所以我們可以認(rèn)為數(shù)組訪問操作能再常數(shù)時(shí)間內(nèi)完成畜份，即時(shí)間復(fù)雜度為O(1)，這種存取任何一個(gè)元素的時(shí)間復(fù)雜度為O(1)的數(shù)據(jù)結(jié)構(gòu)稱之為隨機(jī)存取結(jié)構(gòu)欣尼。而順序表的存儲(chǔ)原理正如上圖所示爆雹，因此順序表的定義如下（引用）：
線性表的順序存儲(chǔ)結(jié)構(gòu)稱之為順序表(Sequential List),它使用一維數(shù)組依次存放從a0到an-1的數(shù)據(jù)元素(a0,a1,…,an-1)，將ai(0< i <> n-1)存放在數(shù)組的第i個(gè)元素愕鼓，使得ai與其前驅(qū)ai-1及后繼ai+1的存儲(chǔ)位置相鄰钙态，因此數(shù)據(jù)元素在內(nèi)存的物理存儲(chǔ)次序反映了線性表數(shù)據(jù)元素之間的邏輯次序。
1.2 順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)分析
接著我們來分析一下順序表的實(shí)現(xiàn)菇晃，先聲明一個(gè)順序表接口類SeqList册倒，然后實(shí)現(xiàn)該接口并實(shí)現(xiàn)接口方法的代碼窃躲，SeqList接口代碼如下：
我們創(chuàng)建ArraySeqList一個(gè)順序表實(shí)現(xiàn)這個(gè)接口不傅。
private final Object[]EMPTY_ELEMENTDATA = {};
private final Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY =10;
/*** * 元素的個(gè)數(shù) */
private int size;
ArraySeqList的構(gòu)造方法
無參構(gòu)造方法忧勿，我們默認(rèn)是空數(shù)組烫映，有參構(gòu)造構(gòu)造方法中伯顶，我們新建一個(gè)長度為size的空數(shù)組斟冕。
get(int index) 實(shí)現(xiàn)分析?
從順序表中獲取值是一種相當(dāng)簡單的操作并且效率很高坷澡，這是由于順序表內(nèi)部采用了數(shù)組作為存儲(chǔ)數(shù)據(jù)的容器讨便。因此只要根據(jù)傳遞的索引值甲捏，然后直接獲取數(shù)組中相對(duì)應(yīng)下標(biāo)的值即可演熟，代碼實(shí)現(xiàn)如下：
set(int index, T data) 實(shí)現(xiàn)分析
在順序表中替換值也是非常高效和簡單的，只要根據(jù)傳遞的索引值index找到需要替換的元素司顿，然后把對(duì)應(yīng)元素值替換成傳遞的data值即可芒粹，代碼如下：
add(int index, T data)和add(T data)實(shí)現(xiàn)分析
在順序表中執(zhí)行插入操作時(shí)，如果其內(nèi)部數(shù)組的容量尚未達(dá)到最大值時(shí)大溜，可以歸結(jié)為兩種情況：一種是在頭部插入或者中間插入化漆，這種情況下需要移動(dòng)數(shù)組中的數(shù)據(jù)元素，效率較低钦奋；另一種是在尾部插入座云，無需移動(dòng)數(shù)組中的元素，效率高付材。
但是當(dāng)順序表內(nèi)部數(shù)組的容量已達(dá)到最大值無法插入時(shí)朦拖，則需要申請(qǐng)另一個(gè)更大容量的數(shù)組并復(fù)制全部數(shù)組元素到新的數(shù)組，這樣的時(shí)間和空間開銷是比較大的厌衔，也就導(dǎo)致了效率更為糟糕了璧帝。
因此在插入頻繁的場(chǎng)景下，順序表的插入操作并不是理想的選擇富寿。下面是順序表在數(shù)組容量充足下頭部或中間插入操作示意圖（尾部插入比較簡單就不演示了）：
理解了以上幾種順序表的插入操作后睬隶，我們通過代碼來實(shí)現(xiàn)這個(gè)插入操作如下。
每次插入元素之前页徐，我們都應(yīng)該判斷數(shù)組是否夠用苏潜，如果數(shù)組長度夠用，就將index以后 的元素右移一位变勇，然后將新元素添加到下標(biāo)為index的位置窖贤。元素個(gè)數(shù)size++
數(shù)組長度不夠的時(shí)候，元素的個(gè)數(shù)大于當(dāng)前數(shù)組的長度時(shí)贰锁，我們就應(yīng)該擴(kuò)容數(shù)組赃梧。代碼如下：
remove(int index) 實(shí)現(xiàn)分析
順序表的刪除操作和前的插入操作情況是類似的，如果是在中間或者頭部刪除順序表中的元素豌熄，那么在刪除位置之后的元素都必須依次往前移動(dòng)授嘀，效率較低，如果是在順序表的尾部直接刪除的話锣险，則無需移動(dòng)元素蹄皱，此情況下刪除效率高览闰。如下圖所示在順序表中刪除元素ai時(shí)，ai之后的元素都依次往前移動(dòng)：
刪除操作的代碼實(shí)現(xiàn)如下：
remove(E e) 實(shí)現(xiàn)分析
在順序表中根據(jù)數(shù)據(jù)data找到需要?jiǎng)h除的數(shù)據(jù)元素和前面分析的根據(jù)index刪除順序表中的數(shù)據(jù)元素是一樣的道理巷折，因此我們只要通過比較找到與data相等的數(shù)據(jù)元素并獲取其下標(biāo)压鉴，然后調(diào)用前面實(shí)現(xiàn)的remove(int index)方法來移除即可。代碼實(shí)現(xiàn)如下：
源碼實(shí)現(xiàn)：源碼
1.3 順序存儲(chǔ)結(jié)構(gòu)的效率分析
數(shù)組的訪問操作能在常數(shù)時(shí)間內(nèi)完成锻拘，即順序表的訪問操作(獲取和修改元素值)的時(shí)間復(fù)雜為O(1)油吭。
對(duì)于在順序表中插入或者刪除元素，從效率上則顯得不太理想了署拟，由于插入或者刪除操作是基于位置的婉宰，需要移動(dòng)數(shù)組中的其他元素，所以順序表的插入或刪除操作推穷，算法所花費(fèi)的時(shí)間主要是用于移動(dòng)元素心包，如在順序表頭部插入或刪除時(shí)，效率就顯得相當(dāng)糟糕了馒铃。若在最前插入或刪除蟹腾，則需要移動(dòng)n（這里假設(shè)長度為n）個(gè)元素；若在最后插入或刪除区宇，則需要移動(dòng)的元素為0岭佳。這里我們假設(shè)插入或刪除值為第i(0）。
也就是說萧锉，在等概率的情況下珊随，插入或者刪除一個(gè)順序表的元素平均需要移動(dòng)順序表元素總量的一半，其時(shí)間復(fù)雜度是O(n)柿隙。當(dāng)然如果在插入時(shí)叶洞，內(nèi)部數(shù)組容量不足時(shí)，也會(huì)造成其他開銷禀崖，如復(fù)制元素的時(shí)間開銷和新建數(shù)組的空間開銷衩辟。
因此總得來說順序表有以下優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)
使用數(shù)組作為內(nèi)部容器簡單且易用；
在訪問元素方面效率高波附；
數(shù)組具有內(nèi)存空間局部性的特點(diǎn)艺晴，由于本身定義為連續(xù)的內(nèi)存塊，所以任何元素與其相鄰的元素在物理地址上也是相鄰的掸屡。
缺點(diǎn)
內(nèi)部數(shù)組大小是靜態(tài)的封寞，在使用前必須指定大小，如果遇到容量不足時(shí)仅财，需動(dòng)態(tài)拓展內(nèi)部數(shù)組的大小狈究，會(huì)造成額外的時(shí)間和空間開銷
在內(nèi)部創(chuàng)建數(shù)組時(shí)提供的是一塊連續(xù)的空間塊，當(dāng)規(guī)模較大時(shí)可能會(huì)無法分配數(shù)組所需要的內(nèi)存空間
順序表的插入和刪除是基于位置的操作盏求，如果需要在數(shù)組中的指定位置插入或者刪除元素抖锥，可能需要移動(dòng)內(nèi)部數(shù)組中的其他元素亿眠，這樣會(huì)造成較大的時(shí)間開銷，時(shí)間復(fù)雜度為O(n)
二磅废、線性表的鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)與實(shí)現(xiàn)（鏈表）
2.1 鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)原理概要
通過前面對(duì)線性順序表的分析纳像，我們知道當(dāng)創(chuàng)建順序表時(shí)必須分配一塊連續(xù)的內(nèi)存存儲(chǔ)空間，而當(dāng)順序表內(nèi)部數(shù)組的容量不足時(shí)拯勉，則必須創(chuàng)建一個(gè)新的數(shù)組竟趾，然后把原數(shù)組的的元素復(fù)制到新的數(shù)組中，這將浪費(fèi)大量的時(shí)間谜喊。而在插入或刪除元素時(shí)，可能需要移動(dòng)數(shù)組中的元素倦始，這也將消耗一定的時(shí)間斗遏。
鑒于這種種原因，于是鏈表就出場(chǎng)了鞋邑，鏈表在初始化時(shí)僅需要分配一個(gè)元素的存儲(chǔ)空間诵次，并且插入和刪除新的元素也相當(dāng)便捷，同時(shí)鏈表在內(nèi)存分配上可以是不連續(xù)的內(nèi)存枚碗，也不需要做任何內(nèi)存復(fù)制和重新分配的操作逾一，由此看來順序表的缺點(diǎn)在鏈表中都變成了優(yōu)勢(shì)，實(shí)際上也是如此肮雨，當(dāng)然鏈表也有缺點(diǎn)遵堵，主要是在訪問單個(gè)元素的時(shí)間開銷上，這個(gè)問題留著后面分析怨规，我們先通過一張圖來初步認(rèn)識(shí)一下鏈表的存儲(chǔ)結(jié)構(gòu)陌宿，如下：
從圖可以看出線性鏈表的存儲(chǔ)結(jié)構(gòu)是用若干個(gè)地址分散的存儲(chǔ)單元存放數(shù)據(jù)元素的，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰波丰，因此每個(gè)存儲(chǔ)單元中都會(huì)有一個(gè)地址指向域壳坪，這個(gè)地址指向域指明其后繼元素的位置。在鏈表中存儲(chǔ)數(shù)據(jù)的單元稱為結(jié)點(diǎn)(Node)掰烟，從圖中可以看出一個(gè)結(jié)點(diǎn)至少包含了數(shù)據(jù)域和地址域爽蝴，其中數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)，而地址域用于存儲(chǔ)前驅(qū)或后繼元素的地址纫骑。
前面我們說過鏈表的插入和刪除都相當(dāng)便捷，這是由于鏈表中的結(jié)點(diǎn)的存儲(chǔ)空間是在插入或者刪除過程中動(dòng)態(tài)申請(qǐng)和釋放的先馆，不需要預(yù)先給單鏈表分配存儲(chǔ)空間的颖对，從而避免了順序表因存儲(chǔ)空間不足需要擴(kuò)充空間和復(fù)制元素的過程，提高了運(yùn)行效率和存儲(chǔ)空間的利用率磨隘。
2.2 單鏈表的儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)分析
同樣地缤底，先來定義一個(gè)頂級(jí)的鏈表接口:ILinkedList和存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)類Node顾患，該類是代表一個(gè)最基本的存儲(chǔ)單元，Node代碼如下：
接著頂級(jí)的鏈表接口ILinkedList个唧，該接口聲明了我們所有需要實(shí)現(xiàn)的方法江解。
boolean isEmpty()實(shí)現(xiàn)分析
需要判斷鏈表是否為空的依據(jù)是頭結(jié)點(diǎn)head是否為null，當(dāng)head=null時(shí)鏈表即為空鏈表徙歼，因此我們只需判斷頭結(jié)點(diǎn)是否為空即可犁河，isEmpty方法實(shí)現(xiàn)如下：
int length()實(shí)現(xiàn)分析
獲取鏈表的長度，我們提供2種方法魄梯，第一種就是增加一個(gè)變量size桨螺，用它倆記錄鏈表的長度。
第二種方法酿秸，因此我們只要遍歷整個(gè)鏈表并獲取結(jié)點(diǎn)的數(shù)量即可獲取到鏈表的長度灭翔。遍歷鏈表需要從頭結(jié)點(diǎn)HeadNode開始，為了不改變頭結(jié)點(diǎn)的存儲(chǔ)單元辣苏，聲明變量p指向當(dāng)前頭結(jié)點(diǎn)和局部變量length肝箱，然后p從頭結(jié)點(diǎn)開始訪問，沿著next地址鏈到達(dá)后繼結(jié)點(diǎn)稀蟋，逐個(gè)訪問煌张，直到最后一個(gè)結(jié)點(diǎn)，每經(jīng)過一個(gè)結(jié)點(diǎn)length就加一退客，最后length的大小就是鏈表的大小骏融。實(shí)現(xiàn)代碼如下：
E get(int index)實(shí)現(xiàn)分析
在單鏈表中獲取某個(gè)元素的值是一種比較費(fèi)時(shí)間的操作，需要從頭結(jié)點(diǎn)開始遍歷直至傳入值index指向的位置萌狂，其查詢獲取值的過程如下圖所示：
代碼如下：
T set(int index, T data)實(shí)現(xiàn)分析?
根據(jù)傳遞的index查找某個(gè)值并替換其值為data绎谦，其實(shí)現(xiàn)過程的原理跟get(int index)是基本一樣的，先找到對(duì)應(yīng)值所在的位置然后刪除即可粥脚，不清晰可以看看前面的get方法的圖解窃肠，這里直接給出代碼實(shí)現(xiàn)：
add(int index, T data)實(shí)現(xiàn)分析?
單鏈表的插入操作分四種情況:?
a.空表插入一個(gè)新結(jié)點(diǎn)，插語句如下：
head=new Node(x,null);
b.在鏈表的表頭插入一個(gè)新結(jié)點(diǎn)(即鏈表的開始處)刷允，此時(shí)表頭head!=null冤留，因此head后繼指針next應(yīng)該指向新插入結(jié)點(diǎn)p，而p的后繼指針應(yīng)該指向head原來的結(jié)點(diǎn)树灶，代碼如下：
以上代碼可以合并為如下代碼：
執(zhí)行過程如下圖：
c.在鏈表的中間插入一個(gè)新結(jié)點(diǎn)p纤怒，需要先找到給定插入位置的前一個(gè)結(jié)點(diǎn)，假設(shè)該結(jié)點(diǎn)為front天通，然后改變front的后繼指向?yàn)樾陆Y(jié)點(diǎn)p泊窘，同時(shí)更新新結(jié)點(diǎn)p的后繼指向?yàn)閒ront原來的后繼結(jié)點(diǎn)，即front.next，其執(zhí)行過程如下圖所示：
代碼實(shí)現(xiàn)如下：
d.在鏈表的表尾插入一個(gè)新結(jié)點(diǎn)(鏈表的結(jié)尾)在尾部插入時(shí)烘豹，同樣需要查找到插入結(jié)點(diǎn)P的前一個(gè)位置的結(jié)點(diǎn)front（假設(shè)為front）瓜贾，該結(jié)點(diǎn)front為尾部結(jié)點(diǎn)，更改尾部結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)P携悯，新結(jié)點(diǎn)P的后繼指針設(shè)置為null祭芦，執(zhí)行過程如下：
具體代碼如下：
T remove(int index) 刪除結(jié)點(diǎn)實(shí)現(xiàn)分析
在單向鏈表中，根據(jù)傳遞index位置刪除結(jié)點(diǎn)的操作分3種情況憔鬼，并且刪除后返回被刪除結(jié)點(diǎn)的數(shù)據(jù)：
a.刪除鏈表頭部（第一個(gè)）結(jié)點(diǎn)龟劲，此時(shí)需要?jiǎng)h除頭部head指向的結(jié)點(diǎn)，并更新head的結(jié)點(diǎn)指向轴或，執(zhí)行圖示如下：
代碼如下：
b.刪除鏈表的中間結(jié)點(diǎn)昌跌，與添加是同樣的道理，需要先找到要?jiǎng)h除結(jié)點(diǎn)r（假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為r）位置的前一個(gè)結(jié)點(diǎn)front(假設(shè)為front)照雁，然后把front.next指向r.next即要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)蚕愤，執(zhí)行過程如下：
代碼如下：
void clear() 實(shí)現(xiàn)分析
清空鏈表是一件非常簡單的事，直接將所有的節(jié)點(diǎn)置空囊榜。代碼如下：
ok~,到此單鏈表主要的添加审胸、刪除亥宿、獲取值卸勺、設(shè)置替換值、獲取長度等方法已分析完畢烫扼，其他未分析的方法都比較簡單這里就不一一分析了曙求，單鏈表的整體代碼最后會(huì)分享到github給大家。
2.3 帶頭結(jié)點(diǎn)的單鏈表以及循環(huán)單鏈表的實(shí)現(xiàn)
帶頭結(jié)點(diǎn)的單鏈表
前面分析的單鏈表是不帶特殊頭結(jié)點(diǎn)的映企，所謂的特殊頭結(jié)點(diǎn)就是一個(gè)沒有值的結(jié)點(diǎn)即：
此時(shí)空鏈表的情況如下：
那么多了頭結(jié)點(diǎn)的單向鏈表有什么好處呢悟狱？通過對(duì)沒有帶頭結(jié)點(diǎn)的單鏈表的分析，我們可以知道堰氓，在鏈表插入和刪除時(shí)都需要區(qū)分操作位挤渐，比如插入操作就分頭部插入和中間或尾部插入兩種情況（中間或尾部插入視為一種情況對(duì)待即可），如果現(xiàn)在有不帶數(shù)據(jù)的頭結(jié)點(diǎn)双絮，那么對(duì)于單鏈表的插入和刪除不再區(qū)分操作的位置浴麻，也就是說頭部、中間囤攀、尾部插入都可以視為一種情況處理了软免，這是因?yàn)榇藭r(shí)頭部插入和頭部刪除無需改變head的指向了，頭部插入如下所示：
代碼如下所示：
接著再看看在頭部刪除的情況：
代碼如下：
帶頭結(jié)點(diǎn)遍歷從head.next開始：
因此無論是插入還是刪除焚挠，在有了不帶數(shù)據(jù)的頭結(jié)點(diǎn)后膏萧，在插入或者刪除時(shí)都無需區(qū)分操作位了，好~，到此我們來小結(jié)一下帶頭結(jié)點(diǎn)的單鏈表特點(diǎn)：
a.空單鏈表只有一個(gè)結(jié)點(diǎn)榛泛，head.next=null蝌蹂。
b.遍歷的起點(diǎn)為p=head.next。
c.頭部插入和頭部刪除無需改變head的指向挟鸠。
??同時(shí)為了使鏈表在尾部插入時(shí)達(dá)到更加高效叉信，我們可在鏈表內(nèi)增加一個(gè)尾部指向的結(jié)點(diǎn)rear（代碼中使用的是last,上面代碼中已經(jīng)使用），如果我們是在尾部添加結(jié)點(diǎn)艘希，那么此時(shí)只要通過尾部結(jié)點(diǎn)rear進(jìn)行直接操作即可硼身，無需從表頭遍歷到表尾，帶尾部結(jié)點(diǎn)的單鏈表如下所示：
從尾部直接插入的代碼實(shí)現(xiàn)如下：
下面看看根據(jù)index插入的代碼實(shí)現(xiàn)覆享，由于有了頭結(jié)點(diǎn)佳遂，頭部、中間撒顿、尾部插入無需區(qū)分操作位都視為一種情況處理丑罪。
代碼如下：
??最后在看看刪除的代碼實(shí)現(xiàn)，由于刪除和插入的邏輯和之前不帶頭結(jié)點(diǎn)的單鏈表分析過的原理的是一樣的凤壁，因此我們這里不重復(fù)了吩屹，主要注意遍歷的起始結(jié)點(diǎn)變化就行。
ok~拧抖，關(guān)于帶頭結(jié)點(diǎn)的單向鏈表就分析到這煤搜，這里貼出實(shí)現(xiàn)源碼，同樣地唧席，稍后在github上也會(huì)提供擦盾。。文章末尾提供下載地址淌哟。
循環(huán)單鏈表
有上述的分析基礎(chǔ)迹卢，循環(huán)單鏈表(Circular Single Linked List)相對(duì)來說就比較簡單了，所謂的循環(huán)單鏈表是指鏈表中的最后一個(gè)結(jié)點(diǎn)的next域指向了頭結(jié)點(diǎn)head徒仓，形成環(huán)形的結(jié)構(gòu)腐碱，我們通過圖示來理解：?
此時(shí)的循環(huán)單鏈表有如下特點(diǎn)：?
a.當(dāng)循環(huán)鏈表為空鏈表時(shí)，head指向頭結(jié)點(diǎn)掉弛，head.next=head症见。?
b.尾部指向rear代表最后一個(gè)結(jié)點(diǎn)，則有rear.next=head狰晚。?
在處理循環(huán)單鏈表時(shí)筒饰，我們只需要注意在遍歷循環(huán)鏈表時(shí)，避免進(jìn)入死循環(huán)即可壁晒，也就是在判斷循環(huán)鏈表是否到達(dá)結(jié)尾時(shí)瓷们，由之前的如下判斷：
//從head.next開始遍歷
Node item=head.next;
while (item!=null){
? ? item=item.next;
}
在循環(huán)單鏈表中改為如下判斷：
Node p=head;
while (p!=head){
p=p.next;
}
具體代碼實(shí)現(xiàn)，詳見github地址，文章末尾給出谬晕。
查找CircleHeadILinkedList.java文件碘裕。
2.3 單鏈表的效率分析
由于單鏈表并不是隨機(jī)存取結(jié)構(gòu)，即使單鏈表在訪問第一個(gè)結(jié)點(diǎn)時(shí)花費(fèi)的時(shí)間為常數(shù)時(shí)間攒钳，但是如果需要訪問第i(0）帮孔，也就是說get(i)和set(i,x)的時(shí)間復(fù)雜度都為O(n)。
由于鏈表在插入和刪除結(jié)點(diǎn)方面十分高效的不撑，因此鏈表比較適合那些插入刪除頻繁的場(chǎng)景使用文兢。如果是單鏈表的話，插入和刪除的時(shí)間復(fù)雜度都是O(n)焕檬。
問題是大部分情況下查找所需時(shí)間比移動(dòng)短多了姆坚，還有就是鏈表不需要連續(xù)空間也不需要擴(kuò)容操作，因此即使時(shí)間復(fù)雜度都是O(n)实愚，所以相對(duì)來說鏈表更適合插入刪除操作兼呵。
參考文章：順序表和鏈表的深入分析。
