JAVA_ArrayList和LinkedList效能比較


當你是要對資料集合去做固定尾端增、刪時
請愛用 ArrayList


當你是要去特定位置做增、刪時
請愛用LinkedList



固定尾端增、刪

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package linkedlistex;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author chous
 */
public class LinkedListEx {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        //ArrayList: If you only want to add or remove items to the end of list.
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        //LinkedList: If you want to add or remove items from anywhere in the list such as beginning or middle.
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        
        doThings("ArrayList" , arrayList);
        doThings("LinkedList" , linkedList);
    }
    
    public static void doThings(String type, List<Integer> list){
        long StartTime = System.currentTimeMillis();
        for (int i=0;i<1E6;i++){//1,000,000 times
            list.add(i);
        }
        long EndTime = System.currentTimeMillis();
        
        System.out.println("Time taken: "+(EndTime-StartTime) + "ms for"+type);
    }
}



ArrayList中每個成員是以Array模式去存放每一資料成員
所以實際中會記錄每一資料之index,會去自動更新當前List的初始大小

ArrayList內部則是會於每次增加新成員時去額外重建一個Array
內部會是兩個Array再做資料交替的過程!!!!!!

假設在新增完第10筆資料成員後(共0~9  十個成員)
再下一筆(第11筆)要增加進來時
則會再生成一個全新Array去做存放(並重新指派更大的空間)
之後再將舊有的成員集copy進來放
再去放置第11筆於尾端位置

也因此在針對尾端增、刪操作上會來的更有效率!!!!!


特定位置做增、刪

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package linkedlistex;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author chous
 */
public class LinkedListEx {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        //ArrayList: If you only want to add or remove items to the end of list.
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        //LinkedList: If you want to add or remove items from anywhere in the list such as beginning or middle.
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        
        doThings("ArrayList" , arrayList);
        doThings("LinkedList" , linkedList);
    }
    
    public static void doThings(String type, List<Integer> list){
        long StartTime = System.currentTimeMillis();
//        for (int i=0;i<1E6;i++){//1,000,000 times
//            list.add(i);
//        }
        for(int i=0;i<1E6;i++){
            list.add(0, i);
        }
        long EndTime = System.currentTimeMillis();
        
        System.out.println("Time taken: "+(EndTime-StartTime) + "ms for"+type);
    }
}





LinkedList:
[0]->[1]->[2]->[3]->[4]->[5]->[6]->....


ArrayList:
[0] [1] [2] [3] [4] [5] [6] [7] .....

LinkedList 中每一個成員都有前一個成員位置的reference,下一個亦然。
也因此可以比ArrayList更有效率去獲得特定位置
它不需要和ArrayList一樣去做很大量資料的搬動

假設 是要去對集合(假設是塞滿500個)中間可能是第255去做增、刪
則會要先將中間之後的245個先刪除才在加入尾端之後在補上剛剛刪掉的後半部分
所以就有一段時差!!!







參考Link:
Java ArrayList.indexOf() Method
https://www.w3resource.com/java-tutorial/arraylist/arraylist_indexof.php

C 語言:鏈結串列(LINKED LIST)的建立與刪除
https://hellolynn.hpd.io/2017/06/02/c-語言:鏈結串列linked-list的建立與刪除/

Difference between ArrayList and LinkedList in Java with example
http://www.dreamscoder.com/viewprogram.php?id=111

坑人无数的Java面试题之ArrayList
https://zhuanlan.zhihu.com/p/34301705

留言

這個網誌中的熱門文章

何謂淨重(Net Weight)、皮重(Tare Weight)與毛重(Gross Weight)

Architecture(架構) 和 Framework(框架) 有何不同?_軟體設計前的事前規劃的藍圖概念

(2021年度)駕訓學科筆試準備題庫歸納分析_法規是非題