我的理解如下，若有錯煩請指教：
一、就記憶體空間使用來看，陣列所佔用之記憶體空間為連續且固定大小的空間，元素之間各自相連，但需要在宣告時就指定陣列大小，且不可修改，由於不需儲存指針，因此記憶體利用效率高；鏈結串列所佔用之記憶體空間為不連續的，每個元素之間透過指針相連，且不需最開始就鎖定鏈結串列的大小，可簡易增減，但需要消耗額外記憶體空間儲存指針。
二、就存取方式來看，陣列的存取方式是透過索引直接存取，在知道索引的情況下，時間複雜度為O(1)，而陣列若要增減元素，在開頭增加元素需要將所有元素後移，時間複雜度為O(n)，而若是後方留有空間，則可以O(1)的複雜度直接新增；鏈結串列之存取方式無論如何都必須由最前面開始存取，時間複雜度為O(n)，但在知道位置的情況下，增減元素更為便利，只需修改指針即可，因此即使要在中途插入元素，時間複雜的也僅有O(1)，但若不知道插入的位置，則時間複雜度為O(n)。
阿摩線上測驗
登入