Java學習筆記之ArrayList和LinkedList差別

ArrayList

LinkedList

相同點：

1. 都實作了List接口，具有一系列相同的操作方法。
2. 都可以轉化為數組。

不同點：

1. ArrayList本質上是一個數組（Object[]），LinkedList本質上是一個雙向連結清單（Node()）。
2. 增加的時候，ArrayList本質上是重新建立一個更長的數組，然後指派。LinkedList是添加一個Node對象，速度上LinkedList更快。
3. 删除的時候，ArrayList是把删除的資料後面的所有資料都向前挪動，LinkedList是把需要删除的資料關聯的兩個資料的Node關聯參數修改掉。
4. 修改資料（set）和查詢資料（get）的時候，ArrayList要優于LinkedList，因為LinkedList要移動指針。

測試Add：

int addNum = 500000;
    private void addArray(){
        long time1=System.currentTimeMillis();
        ArrayList<String> arrayList = new ArrayList<>();
        for(int i = 0;i<addNum;i++){
            arrayList.add("a"+i);
        }
        long time2=System.currentTimeMillis();
        Log.w("列印","時間："+(time2-time1));
    }
    private void addLinked(){
        long time1=System.currentTimeMillis();
        LinkedList<String> arrayList = new LinkedList<>();
        for(int i = 0;i<addNum;i++){
            arrayList.add("a"+i);
        }
        long time2=System.currentTimeMillis();
        Log.w("列印","時間："+(time2-time1));
    }
           

ArrayLst十次輸出結果

2019-01-03 18:54:07.150 21855-22130/fun.bingo.rxapplication W/列印: 時間：127
2019-01-03 18:54:08.112 21855-22131/fun.bingo.rxapplication W/列印: 時間：146
2019-01-03 18:54:08.904 21855-22132/fun.bingo.rxapplication W/列印: 時間：161
2019-01-03 18:54:09.649 21855-22133/fun.bingo.rxapplication W/列印: 時間：154
2019-01-03 18:54:10.407 21855-22134/fun.bingo.rxapplication W/列印: 時間：120
2019-01-03 18:54:11.756 21855-22136/fun.bingo.rxapplication W/列印: 時間：149
2019-01-03 18:54:12.486 21855-22137/fun.bingo.rxapplication W/列印: 時間：140
2019-01-03 18:54:13.198 21855-22138/fun.bingo.rxapplication W/列印: 時間：149
2019-01-03 18:54:13.846 21855-22139/fun.bingo.rxapplication W/列印: 時間：143
2019-01-03 18:54:14.554 21855-22145/fun.bingo.rxapplication W/列印: 時間：130
           

LinkedList十次輸出結果

2019-01-03 18:55:06.068 21855-22165/fun.bingo.rxapplication W/列印: 時間：110
2019-01-03 18:55:07.031 21855-22166/fun.bingo.rxapplication W/列印: 時間：95
2019-01-03 18:55:07.876 21855-22168/fun.bingo.rxapplication W/列印: 時間：101
2019-01-03 18:55:08.594 21855-22173/fun.bingo.rxapplication W/列印: 時間：114
2019-01-03 18:55:09.306 21855-22175/fun.bingo.rxapplication W/列印: 時間：101
2019-01-03 18:55:10.029 21855-22176/fun.bingo.rxapplication W/列印: 時間：104
2019-01-03 18:55:10.697 21855-22177/fun.bingo.rxapplication W/列印: 時間：93
2019-01-03 18:55:11.391 21855-22178/fun.bingo.rxapplication W/列印: 時間：96
2019-01-03 18:55:12.040 21855-22179/fun.bingo.rxapplication W/列印: 時間：99
2019-01-03 18:55:12.686 21855-22180/fun.bingo.rxapplication W/列印: 時間：104
           

修改addNum為100W之後列印

ArrayList：

2019-01-03 18:57:05.484 22431-22453/fun.bingo.rxapplication W/列印: 時間：296
2019-01-03 18:57:06.419 22431-22454/fun.bingo.rxapplication W/列印: 時間：269
2019-01-03 18:57:07.551 22431-22455/fun.bingo.rxapplication W/列印: 時間：333
2019-01-03 18:57:08.421 22431-22456/fun.bingo.rxapplication W/列印: 時間：276
2019-01-03 18:57:09.379 22431-22459/fun.bingo.rxapplication W/列印: 時間：378
2019-01-03 18:57:10.097 22431-22460/fun.bingo.rxapplication W/列印: 時間：280
2019-01-03 18:57:14.283 22431-22462/fun.bingo.rxapplication W/列印: 時間：304
2019-01-03 18:57:15.214 22431-22463/fun.bingo.rxapplication W/列印: 時間：286
2019-01-03 18:57:16.123 22431-22464/fun.bingo.rxapplication W/列印: 時間：282
2019-01-03 18:57:16.990 22431-22465/fun.bingo.rxapplication W/列印: 時間：250
           

LinkedList

2019-01-03 18:58:14.855 22431-22487/fun.bingo.rxapplication W/列印: 時間：212
2019-01-03 18:58:15.825 22431-22488/fun.bingo.rxapplication W/列印: 時間：198
2019-01-03 18:58:16.662 22431-22489/fun.bingo.rxapplication W/列印: 時間：199
2019-01-03 18:58:17.482 22431-22490/fun.bingo.rxapplication W/列印: 時間：194
2019-01-03 18:58:18.277 22431-22491/fun.bingo.rxapplication W/列印: 時間：196
2019-01-03 18:58:19.070 22431-22492/fun.bingo.rxapplication W/列印: 時間：213
2019-01-03 18:58:19.864 22431-22493/fun.bingo.rxapplication W/列印: 時間：192
2019-01-03 18:58:20.662 22431-22494/fun.bingo.rxapplication W/列印: 時間：207
2019-01-03 18:58:21.441 22431-22495/fun.bingo.rxapplication W/列印: 時間：194
2019-01-03 18:58:22.215 22431-22496/fun.bingo.rxapplication W/列印: 時間：193
           

測試查：

addNum為100W：

long time1=System.currentTimeMillis();
        list.contains("a"+999999);
        long time2=System.currentTimeMillis();
        Log.w("列印","時間："+(time2-time1));
           

ArrayList：記憶體峰值357.5M，平穩後150M

2019-01-03 19:09:12.685 23306-23339/fun.bingo.rxapplication W/列印: 時間：18
2019-01-03 19:09:14.006 23306-23340/fun.bingo.rxapplication W/列印: 時間：11
2019-01-03 19:09:15.086 23306-23341/fun.bingo.rxapplication W/列印: 時間：12
2019-01-03 19:09:16.227 23306-23342/fun.bingo.rxapplication W/列印: 時間：9
2019-01-03 19:09:17.207 23306-23343/fun.bingo.rxapplication W/列印: 時間：13
2019-01-03 19:09:17.899 23306-23344/fun.bingo.rxapplication W/列印: 時間：9
2019-01-03 19:09:18.516 23306-23345/fun.bingo.rxapplication W/列印: 時間：9
2019-01-03 19:09:19.143 23306-23346/fun.bingo.rxapplication W/列印: 時間：12
2019-01-03 19:09:19.731 23306-23347/fun.bingo.rxapplication W/列印: 時間：9
2019-01-03 19:09:20.399 23306-23348/fun.bingo.rxapplication W/列印: 時間：9
           

LinkedList：記憶體峰值443.6M，平穩後180M

2019-01-03 19:11:29.288 23444-23468/fun.bingo.rxapplication W/列印: 時間：24
2019-01-03 19:11:30.808 23444-23469/fun.bingo.rxapplication W/列印: 時間：10
2019-01-03 19:11:34.670 23444-23471/fun.bingo.rxapplication W/列印: 時間：15
2019-01-03 19:11:35.700 23444-23474/fun.bingo.rxapplication W/列印: 時間：14
2019-01-03 19:11:36.635 23444-23475/fun.bingo.rxapplication W/列印: 時間：13
2019-01-03 19:11:37.404 23444-23476/fun.bingo.rxapplication W/列印: 時間：14
2019-01-03 19:11:38.069 23444-23477/fun.bingo.rxapplication W/列印: 時間：15
2019-01-03 19:11:38.691 23444-23478/fun.bingo.rxapplication W/列印: 時間：13
2019-01-03 19:11:39.319 23444-23479/fun.bingo.rxapplication W/列印: 時間：12
2019-01-03 19:11:39.926 23444-23480/fun.bingo.rxapplication W/列印: 時間：11
           

addNum為200W：

long time1=System.currentTimeMillis();
        list.contains("a"+1999999);
        long time2=System.currentTimeMillis();
        Log.w("列印","時間："+(time2-time1));
           

ArrayList:添加過程中記憶體峰值646.1M,平穩後270M

2019-01-04 10:14:14.960 10488-11012/fun.bingo.rxapplication W/列印: 時間：33
2019-01-04 10:14:16.299 10488-11013/fun.bingo.rxapplication W/列印: 時間：20
2019-01-04 10:14:17.110 10488-11014/fun.bingo.rxapplication W/列印: 時間：21
2019-01-04 10:14:17.784 10488-11015/fun.bingo.rxapplication W/列印: 時間：18
2019-01-04 10:14:18.401 10488-11022/fun.bingo.rxapplication W/列印: 時間：20
2019-01-04 10:14:18.893 10488-11023/fun.bingo.rxapplication W/列印: 時間：20
2019-01-04 10:14:19.350 10488-11024/fun.bingo.rxapplication W/列印: 時間：23
2019-01-04 10:14:19.772 10488-11025/fun.bingo.rxapplication W/列印: 時間：23
2019-01-04 10:14:20.171 10488-11026/fun.bingo.rxapplication W/列印: 時間：22
2019-01-04 10:14:20.595 10488-11027/fun.bingo.rxapplication W/列印: 時間：21
           

LinkedList:添加過程中記憶體峰值0.8G，平穩後0.3G。

2019-01-04 10:18:06.116 12456-14470/fun.bingo.rxapplication W/列印: 時間：51
2019-01-04 10:18:06.813 12456-14478/fun.bingo.rxapplication W/列印: 時間：28
2019-01-04 10:18:07.427 12456-14485/fun.bingo.rxapplication W/列印: 時間：21
2019-01-04 10:18:08.022 12456-14490/fun.bingo.rxapplication W/列印: 時間：19
2019-01-04 10:18:08.617 12456-14500/fun.bingo.rxapplication W/列印: 時間：21
2019-01-04 10:18:09.289 12456-14505/fun.bingo.rxapplication W/列印: 時間：25
2019-01-04 10:18:09.964 12456-14512/fun.bingo.rxapplication W/列印: 時間：21
2019-01-04 10:18:10.556 12456-14517/fun.bingo.rxapplication W/列印: 時間：20
2019-01-04 10:18:11.179 12456-14524/fun.bingo.rxapplication W/列印: 時間：28
2019-01-04 10:18:11.814 12456-14530/fun.bingo.rxapplication W/列印: 時間：23
           

結論1：增加和删除的時候，LinkedList資料量越大越占優勢，但Linked由于需要建立大量對象，占用記憶體比ArrayList記憶體高很多。

結論2: 修改和查詢的時候，ArrayList資料量越大越占優勢。

結論3: 有人說資料量小的時候用哪個都可以，我反而覺得資料量小的時候也應該用ArrayList，節省記憶體啊！！！至于LinkedList，個人覺得除非需要雙向連結清單的結構，或者小量資料需要頻繁的進行增加和删除操作，不然不建議使用，至于修改和查詢，直接ArrayList。

結論4: 資料量大的時候，不要懷疑，無論是增删改查都用ArrayList，想辦法優化算法就可以了，因為LinkedList占用記憶體太大！