一、在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷
數(shù)組可以通過下標(biāo)訪問，隨機(jī)訪問效率高，鏈表需要通過指針遍歷，訪問效率低。
數(shù)組在分配空間后不能再改變大小，如果滿了之后再放東西就必須重新分配一個較大的內(nèi)存空間，將原來的數(shù)組內(nèi)容拷貝進(jìn)去。而鏈表可以隨意插入，比數(shù)組靈活。
存相同的數(shù)據(jù)，鏈表占用的內(nèi)存空間大，因為要分配額外的內(nèi)存存下一個節(jié)點(diǎn)的內(nèi)存地址。
ArrayList
ArrayList是動態(tài)擴(kuò)展數(shù)組，底層是用數(shù)組實(shí)現(xiàn)，插入位置有三種情況，從首位插入，中間位置插入，尾部插入。線性表的插入刪除操作都是通過移動來實(shí)現(xiàn)的，由于數(shù)組長度固定不變，插入數(shù)據(jù)時，需要一個新的數(shù)組。1.當(dāng)添加數(shù)據(jù)是在首位插入時，先將新的數(shù)據(jù)放入到新的數(shù)組內(nèi)，然后將原始數(shù)組中的數(shù)據(jù)復(fù)制到新的數(shù)組。
2.當(dāng)數(shù)據(jù)插入的位置是中間位置時，先將插入位置前面的數(shù)據(jù)先放到新的數(shù)組里，再放新的數(shù)據(jù)，再復(fù)制舊的數(shù)據(jù)完成添加。3.數(shù)據(jù)尾部插入，由于不會影響其他元素，因此會直接插入到后面。
同樣，刪除按位置也有三種情況：1.從頭部刪除，刪除頭結(jié)點(diǎn)然后移動后面的數(shù)據(jù)
2.從中間指定位置刪除，找到要刪除數(shù)據(jù)的位置，刪除后，后面的數(shù)據(jù)移動.3.從尾部刪除：直接刪除尾部數(shù)據(jù)完成刪除操作。
LinkedList
LinkedList是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，底層是用鏈表實(shí)現(xiàn)，是由相互引用的節(jié)點(diǎn)組成的雙向鏈表，當(dāng)插入數(shù)據(jù)到某個位置時，這個數(shù)據(jù)會形成一個新的節(jié)點(diǎn)，然后改變鏈表中對應(yīng)的兩個節(jié)點(diǎn)的引用關(guān)系就可以完成插入。同樣，刪除數(shù)據(jù)時，刪除對應(yīng)節(jié)點(diǎn)的引用就可以完成刪除操作。
延伸閱讀：
二、鏈表與數(shù)組的主要區(qū)別
（1）數(shù)組的元素個數(shù)是固定的,而組成鏈表的結(jié)點(diǎn)個數(shù)可按需要增減;
（2）數(shù)組元素的存諸單元在數(shù)組定義時分配，鏈表結(jié)點(diǎn)的存儲單元在程序執(zhí)行時動態(tài)向系統(tǒng)申請:
（3）數(shù)組中的元素順序關(guān)系由元素在數(shù)組中的位置(即下標(biāo))確定,鏈表中的結(jié)點(diǎn)順序關(guān)系由結(jié)點(diǎn)所包含的指針來體現(xiàn)。
（4）對于不是固定長度的列表,用可能最大長度的數(shù)組來描述，會浪費(fèi)許多內(nèi)存空間。
（5）對于元素的插人、刪除操作非常頻繁的列表處理場合,用數(shù)組表示列表也是不適宜的。若用鏈表實(shí)現(xiàn)，會使程序結(jié)構(gòu)清晰，處理的方法也較為簡便。
例如：在一個列表中間要插人一個新元素，如用數(shù)組表示列表，為完成插人工作，插人處之后的全部元素必須向后移動一個位置空出的位置用于存儲新元素。
對于在一個列表中刪除一個元素情況，為保持?jǐn)?shù)組中元素相對位置連續(xù)遞增，刪除處之后的元素都得向前移一個位置。如用鏈表實(shí)現(xiàn)列表.鏈表結(jié)點(diǎn)的插人或刪除操作不再需要移動結(jié)點(diǎn)，只需改變相關(guān)的結(jié)點(diǎn)中的后繼結(jié)點(diǎn)指針的值即可，與結(jié)點(diǎn)的實(shí)際存儲位置無關(guān)。
京公網(wǎng)安備 11010802030320號