# Java 的 List ArrayList 和 LinkList的差異測試
###### tags: `Java`
## 更新 2022.3.14
發現stackoverflow上有相關探討，需要重新測試方案，以測試實際差異
https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java

## 測試環境
### 電腦環境
* MacBook Pro (13-inch, 2017, Two Thunderbolt 3 ports)
* cpu : 2.3 GHz Intel Core i5
* memory : 8 GB 2133 MHz LPDDR3
* 硬碟 : Macintosh HD

### Java version
* java version "1.8.0_91"
* Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
* Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

### Java 測試執行指令

java -jar LinkTest.jar

:::danger
JVM 採用預設無調整記憶體
:::

## 測試方式
### 資料的新增
#### 新增單純 class

在 Test class 無任何方法、成員時，以下表格為測試結果

| List類型 | class 數量 | 執行時間(毫秒) |
| -------- | -------- | -------- |
| ArrayList | 70_091_000 | 21_011 |
| | 41_741_000 | 11_660 |
| LinkList | 70_091_000 | error |
| | 41_741_000 | 23_571 |

:::warning
* 70_091_000 為目前 ArrayList 能儲存的最大物件數量
* 41_741_000 為目前 LinkList 能儲存的最大物件數量
* error : Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
:::

##### ArrayList 測試程式碼

public static void  testArrayListAddObject(long objSize) {
    List<Test> list = new ArrayList<>();
    long starTime = System.currentTimeMillis();
    for(int i = 0; i < objSize; i++) {
        list.add(new Test());
    }
    long endTime = System.currentTimeMillis();
    System.out.println(endTime - starTime);
}

##### LinkedList 測試程式碼

public static void  testLinkedListAddObject(long objSize) {
    List<Test> list = new LinkedList<>();
    long starTime = System.currentTimeMillis();
    for(int i = 0; i < objSize; i++) {
        list.add(new Test();
    }
    long endTime = System.currentTimeMillis();
    System.out.println(endTime - starTime);
}

#### 新增兩個屬性的 class
在 Test class 擁有兩個私有成員、四個方法時，以下表格為測試結果

| List類型 | class 數量 | 執行時間(毫秒) |
| -------- | -------- | -------- |
| ArrayList | 11_213_000 | 54_774 |
| | 9_940_000 | 13_038 |
| LinkList | 11_213_000 | error |
| | 9_940_000 | 27_220 |
:::warning
* 11_213_000 為目前 ArrayList 能儲存的最大物件數量
* 9_940_000 為目前 LinkList 能儲存的最大物件數量
* error : Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
:::
##### ArrayList 測試程式碼

public static void  testArrayListAddObject(long objSize) {
    List<Test> list = new ArrayList<>();
    long starTime = System.currentTimeMillis();
    for(int i = 0; i < objSize; i++) {
        list.add(new Test(String.valueOf(i), String.valueOf(i + "name")));
    }
    long endTime = System.currentTimeMillis();
    System.out.println(endTime - starTime);
}

##### LinkedList 測試程式碼

public static void  testLinkedListAddObject(long objSize) {
    List<Test> list = new LinkedList<>();
    long starTime = System.currentTimeMillis();
    for(int i = 0; i < objSize; i++) {
        list.add(new Test(String.valueOf(i), String.valueOf(i + "name"));
    }
    long endTime = System.currentTimeMillis();
    System.out.println(endTime - starTime);
}

#### 總結
* LinkList在新增物件的速度比ArrayList慢
* class 的內部屬性的增加，會減少記憶體的儲存空間、增加新增的時間

#### 下次測試改良
* 加大 JVM 的記憶體使用空間
* 增加 class 內部成員，測試對效能影響的時間曲線

### 資料的搜尋
LinkList在搜尋中間資料的速度比ArrayList慢
未完成 測試get的實際情況
array
obj_num : 9_940_000
add : 19631
get : 8871

17469
11946

array
30485
20404

link
30427
19363

### 資料的刪除
LinkList在刪除中間隨機資料的速度比ArrayList慢
未完成 測試刪除的實際情況