78.鏈表和數組的區別在哪裡？
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點，現在公司招人的競爭可能就在細節上產生，誰比較仔細，誰獲
勝的機會就大。
/* 78.鏈表和數組的區別在哪裡？ 分析：主要在基本概念上的理解。 但是最好能考慮的全面一點，現在公司招人的競爭可能就在細節上產生，誰比較仔細，誰獲 勝的機會就大。 1.數組靜態分配內存，鏈表動態分配內存； 數組必須事先定義固定的長度（元素個數），不能適應數據動態地增減的情況， 即在使用數組之前，就必須對數組的大小進行確定。當數據增加時，可能超出原先定義的元素個數； 當數據減少時，造成內存浪費。數組中插入、刪除數據項時，需要移動其它數據項。 而鏈表採用動態分配內存的形式實現，可以適應數據動態地增減的情況， 需要時可以用new/malloc分配內存空間，不需要時用delete/free將已分配的空間釋放， 不會造成內存空間浪費，且可以方便地插入、刪除數據項。 2.數組在內存中連續，鏈表不連續； 數組中的數據在內存中是順序存儲的，而鏈表是隨機存儲的。 數組的隨機訪問效率很高，可以直接定位，但插入、刪除操作的效率比較低。 鏈表在插入、刪除操作上相對數組有很高的效率，而如果要訪問鏈表中的某個元素的話， 那就得從表頭逐個遍歷，直到找到所需要的元素為止，所以，鏈表的隨機訪問效率比數組低。 3.數組元素在棧區，鏈表元素在堆區； 數組從棧中分配空間，對於程序員方便快速，但是自由度小。 鏈表從堆中分配空間，自由度大，但是申請管理比較麻煩。 4.數組利用下標定位，時間複雜度為O(1)，鏈表定位元素時間複雜度O(n)； 5.數組插入或刪除元素的時間複雜度O(n)，鏈表的時間複雜度O(1)。 鏈表不存在越界問題，數組有越界問題。數組便於查詢， 鏈表便於插入刪除，數組節省空間但是長度固定，鏈表雖然變長但是佔了更多的存儲空間。 如果需要快速訪問數據，很少或不插入和刪除元素，就應該用數組； 相反,如果需要經常插入和刪除元素就需要用鏈表數據結構了 */