一、在C語言下數組array與鏈表linklist各自的優點和缺陷

數組可以通過下標訪問，隨機訪問效率高，鏈表需要通過指針遍歷，訪問效率低。

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

存相同的數據，鏈表占用的內存空間大，因為要分配額外的內存存下一個節點的內存地址。

ArrayList

ArrayList是動態擴展數組，底層是用數組實現，插入位置有三種情況，從首位插入，中間位置插入，尾部插入。線性表的插入刪除操作都是通過移動來實現的，由于數組長度固定不變，插入數據時，需要一個新的數組。1.當添加數據是在首位插入時，先將新的數據放入到新的數組內，然后將原始數組中的數據復制到新的數組。

2.當數據插入的位置是中間位置時，先將插入位置前面的數據先放到新的數組里，再放新的數據，再復制舊的數據完成添加。3.數據尾部插入，由于不會影響其他元素，因此會直接插入到后面。

同樣，刪除按位置也有三種情況：1.從頭部刪除，刪除頭結點然后移動后面的數據

2.從中間指定位置刪除，找到要刪除數據的位置，刪除后，后面的數據移動.3.從尾部刪除：直接刪除尾部數據完成刪除操作。

LinkedList

LinkedList是雙向鏈表的數據結構，底層是用鏈表實現，是由相互引用的節點組成的雙向鏈表，當插入數據到某個位置時，這個數據會形成一個新的節點，然后改變鏈表中對應的兩個節點的引用關系就可以完成插入。同樣，刪除數據時，刪除對應節點的引用就可以完成刪除操作。

延伸閱讀：

二、鏈表與數組的主要區別

（1）數組的元素個數是固定的,而組成鏈表的結點個數可按需要增減;

（2）數組元素的存諸單元在數組定義時分配，鏈表結點的存儲單元在程序執行時動態向系統申請:

（3）數組中的元素順序關系由元素在數組中的位置(即下標)確定,鏈表中的結點順序關系由結點所包含的指針來體現。

（4）對于不是固定長度的列表,用可能最大長度的數組來描述，會浪費許多內存空間。

（5）對于元素的插人、刪除操作非常頻繁的列表處理場合,用數組表示列表也是不適宜的。若用鏈表實現，會使程序結構清晰，處理的方法也較為簡便。

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

對于在一個列表中刪除一個元素情況，為保持數組中元素相對位置連續遞增，刪除處之后的元素都得向前移一個位置。如用鏈表實現列表.鏈表結點的插人或刪除操作不再需要移動結點，只需改變相關的結點中的后繼結點指針的值即可，與結點的實際存儲位置無關。