一、在C語(yǔ)言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷

數(shù)組可以通過(guò)下標(biāo)訪問(wèn)，隨機(jī)訪問(wèn)效率高，鏈表需要通過(guò)指針遍歷，訪問(wèn)效率低。

數(shù)組在分配空間后不能再改變大小，如果滿了之后再放東西就必須重新分配一個(gè)較大的內(nèi)存空間，將原來(lái)的數(shù)組內(nèi)容拷貝進(jìn)去。而鏈表可以隨意插入，比數(shù)組靈活。

存相同的數(shù)據(jù)，鏈表占用的內(nèi)存空間大，因?yàn)橐峙漕~外的內(nèi)存存下一個(gè)節(jié)點(diǎn)的內(nèi)存地址。

ArrayList

ArrayList是動(dòng)態(tài)擴(kuò)展數(shù)組，底層是用數(shù)組實(shí)現(xiàn)，插入位置有三種情況，從首位插入，中間位置插入，尾部插入。線性表的插入刪除操作都是通過(guò)移動(dòng)來(lái)實(shí)現(xiàn)的，由于數(shù)組長(zhǎng)度固定不變，插入數(shù)據(jù)時(shí)，需要一個(gè)新的數(shù)組。1.當(dāng)添加數(shù)據(jù)是在首位插入時(shí)，先將新的數(shù)據(jù)放入到新的數(shù)組內(nèi)，然后將原始數(shù)組中的數(shù)據(jù)復(fù)制到新的數(shù)組。

2.當(dāng)數(shù)據(jù)插入的位置是中間位置時(shí)，先將插入位置前面的數(shù)據(jù)先放到新的數(shù)組里，再放新的數(shù)據(jù)，再?gòu)?fù)制舊的數(shù)據(jù)完成添加。3.數(shù)據(jù)尾部插入，由于不會(huì)影響其他元素，因此會(huì)直接插入到后面。

同樣，刪除按位置也有三種情況：1.從頭部刪除，刪除頭結(jié)點(diǎn)然后移動(dòng)后面的數(shù)據(jù)

2.從中間指定位置刪除，找到要?jiǎng)h除數(shù)據(jù)的位置，刪除后，后面的數(shù)據(jù)移動(dòng).3.從尾部刪除：直接刪除尾部數(shù)據(jù)完成刪除操作。

LinkedList

LinkedList是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，底層是用鏈表實(shí)現(xiàn)，是由相互引用的節(jié)點(diǎn)組成的雙向鏈表，當(dāng)插入數(shù)據(jù)到某個(gè)位置時(shí)，這個(gè)數(shù)據(jù)會(huì)形成一個(gè)新的節(jié)點(diǎn)，然后改變鏈表中對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)的引用關(guān)系就可以完成插入。同樣，刪除數(shù)據(jù)時(shí)，刪除對(duì)應(yīng)節(jié)點(diǎn)的引用就可以完成刪除操作。

延伸閱讀：

二、鏈表與數(shù)組的主要區(qū)別

（1）數(shù)組的元素個(gè)數(shù)是固定的,而組成鏈表的結(jié)點(diǎn)個(gè)數(shù)可按需要增減;

（2）數(shù)組元素的存諸單元在數(shù)組定義時(shí)分配，鏈表結(jié)點(diǎn)的存儲(chǔ)單元在程序執(zhí)行時(shí)動(dòng)態(tài)向系統(tǒng)申請(qǐng):

（3）數(shù)組中的元素順序關(guān)系由元素在數(shù)組中的位置(即下標(biāo))確定,鏈表中的結(jié)點(diǎn)順序關(guān)系由結(jié)點(diǎn)所包含的指針來(lái)體現(xiàn)。

（4）對(duì)于不是固定長(zhǎng)度的列表,用可能最大長(zhǎng)度的數(shù)組來(lái)描述，會(huì)浪費(fèi)許多內(nèi)存空間。

（5）對(duì)于元素的插人、刪除操作非常頻繁的列表處理場(chǎng)合,用數(shù)組表示列表也是不適宜的。若用鏈表實(shí)現(xiàn)，會(huì)使程序結(jié)構(gòu)清晰，處理的方法也較為簡(jiǎn)便。

　　例如：在一個(gè)列表中間要插人一個(gè)新元素，如用數(shù)組表示列表，為完成插人工作，插人處之后的全部元素必須向后移動(dòng)一個(gè)位置空出的位置用于存儲(chǔ)新元素。

對(duì)于在一個(gè)列表中刪除一個(gè)元素情況，為保持?jǐn)?shù)組中元素相對(duì)位置連續(xù)遞增，刪除處之后的元素都得向前移一個(gè)位置。如用鏈表實(shí)現(xiàn)列表.鏈表結(jié)點(diǎn)的插人或刪除操作不再需要移動(dòng)結(jié)點(diǎn)，只需改變相關(guān)的結(jié)點(diǎn)中的后繼結(jié)點(diǎn)指針的值即可，與結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置無(wú)關(guān)。