Vector，ArrayList，LinkedList的異同
2019-11-09 16:52:48
供稿：網友
一.概況三者都來自于List，其中vector，ArrayList底層實現是數組，而LinkedList的底層實現是單鏈表。三者有如下特點：1.Vector，ArrayList查找快，增刪慢。LinkedList相反，查找慢，增刪快；2.vector是線程安全的。ArrayList，LinkedLIst是線程不安全的二.本文主要分析內容1.ArrayList和LInkedLIst為什么有如上差異，增刪數據的速度差距；為什么查找多，增刪少時候用ArrayList，相反情況用LinkedList2.數組和鏈表的概念和各自的特性3.動態分配內存，靜態分配內存的概念和特點4.Android內存分區和各自的特點用途三.問題的解決1.“Vector，ArrayList查找快，增刪慢。LinkedList相反，查找慢，增刪快”的原因：由于前兩者的底部實現是數組而后者的底部實現是單鏈表。2.為什么數組和鏈表在查詢和增加刪除會存在前者查找快，增刪慢的原因：先看區別：數組靜態分配內存，鏈表動態分配內存；數組元素在棧區，鏈表元素在堆區；數組在內存中連續，鏈表不連續；數組利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n)；數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1)。所以：查找元素時候在數組中可以根據下標直接定位，而鏈表只能順序查詢，數組中即要去第i個元素，a[i]即可，而鏈表是線性結構，要取第i個元素，需用指針往后遍歷i次才能找到（數組利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n)），造成前者查快，后者查慢。增刪的時候由于數組在內存中是連續的增加或者刪除一個別的元素也都要跟著動，而鏈表在內存中是不連續的只是持有下個元素的node信息，所以增加和刪除元素時候只要前后的元素做改變就可以了，也就造成前者增刪慢，后者快（數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1)）。3. 數組必須事先定義固定的長度（元素個數），不能適應數據動態地增減的情況。當數據增加時，可能超出原先定義的元素個數；當數據減少時，造成內存浪費。同時數組從棧中靜態分配空間, 對于程序員方便快速,但自由度?。绘湵韯討B地進行存儲分配，可以適應數據動態地增減的情況。4. Android內存分區：1.寄存器：最快的存儲區, 由編譯器根據需求進行分配,我們在程序中無法控制.2. 棧：存放基本類型的變量數據和對象的引用，但對象本身不存放在棧中，而是存放在堆（new 出來的對象）或者常量池中（字符串常量對象存放在常量池中。）3. 堆：存放所有new出來的對象。4. 靜態域：存放靜態成員（static定義的）5. 常量池：存放字符串常量和基本類型常量（public static final）。這里我們主要關心棧，堆。對于棧和常量池中的對象可以共享，對于堆中的對象不可以共享。棧中的數據大小和生命周期是可以確定的，當沒有引用指向數據時，這個數據就會消失。堆中的對象的由垃圾回收器負責回收，因此大小和生命周期不需要確定 ，具有很大的靈活性。四.總結1.三者各自的特性2.ArrayList和LInkedLIst的特性對比和形成差異的原因3.簡單介紹了Android中內存RAM。這里只是簡單的說了一下堆棧，后面會有一個文章來介紹我們的代碼到底在內存的哪里運行參考：http://blog.csdn.net/aa449649823/article/details/50116895
