ArrayList,LinkedList 查詢及修改效能比較

在專案中常常會用到Collection的ArrayList,LinkedList這兩種，這兩種在使用者或許沒有多大不同，但是在本質上卻有很大的不相同，今天來探討這兩者本質部份以及效能部分

1.ArrayList 資料結構

2.LinkedList資料結構

3.1 比較兩者隨機查詢資料效能

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

public class ListTest {
 //資料大小
 int dataSize = 100000;
 // 紀錄開始時間
 long[]   testBeginTime = new long[4];
 // 紀錄結束時間
 long[]   testEndTime  = new long[4];
 // 基本資料長度
 Integer[]  ia    = new Integer[dataSize];
 // 初始化隨機物件
 Random   random   = new Random();
 // 初始化ArrayList
 List<Integer> arraylist  = null;
 // 初始化linkList
 List<Integer> linklist  = null;
 
 {
  // 初始化ia陣列資料
  for (int i = 0; i < ia.length; i++) {
   ia[i] = i;
  }
  arraylist = new ArrayList<Integer>(Arrays.asList(ia));
  linklist = new LinkedList<Integer>(Arrays.asList(ia));
 }

 void testListRandomQuery() {
  testBaginTime[0] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   arraylist.get(random.nextInt(dataSize));
  }
  testEndTime[0] = System.currentTimeMillis();
  testBaginTime[1] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   linklist.get(random.nextInt(dataSize));
  }
  testEndTime[1] = System.currentTimeMillis();
  System.out.println("ArrayList time : " + ((testEndTime[0] - testBeginTime[0]) / 1000) + " sec");
  System.out.println("LinkedList time : " + ((testEndTime[1] - testBeginTime[1]) / 1000) + " sec");
 };

 void testListModify() {
 };

 public static void main(String[] args) throws InterruptedException {
  new ListTest().testListRandomQuery();
 }
}

執行結果:
ArrayList time : 0 sec
LinkedList time : 7 sec

從執行結果來看，於讀取隨機資料LinkedList 所花的時間足足比ArrayList多花上七秒的時間
這是以十萬筆資料的情況來進行模擬，從這裡可以展現出ArrayList比LinkedList在進行隨機
讀取資料上效能的展現

3.2 比較兩者隨機插入資料效能

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

public class ListTest {
 //資料大小
 int dataSize = 100000;
 // 紀錄開始時間
 long[]   testBeginTime = new long[4];
 // 紀錄結束時間
 long[]   testEndTime  = new long[4];
 // 基本資料長度
 Integer[]  ia    = new Integer[dataSize];
 // 初始化隨機物件
 Random   random   = new Random();
 // 初始化ArrayList
 List<Integer> arraylist  = null;
 // 初始化linkList
 List<Integer> linklist  = null;
 
 {
  // 初始化ia陣列資料
  for (int i = 0; i < ia.length; i++) {
   ia[i] = i;
  }
  arraylist = new ArrayList<Integer>(Arrays.asList(ia));
  linklist = new LinkedList<Integer>(Arrays.asList(ia));
 }

 void testListModify() {
  testBaginTime[0] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   arraylist.add(random.nextInt(dataSize),i);
  }
  testEndTime[0] = System.currentTimeMillis();
  testBaginTime[1] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   linklist.add(random.nextInt(dataSize),i);
  }
   testEndTime[1] = System.currentTimeMillis();
   System.out.println("ArrayList time : " + ((testEndTime[0] - testBeginTime[0]) / 1000) + " sec");
   System.out.println("LinkedList time : " + ((testEndTime[1] - testBeginTime[1]) / 1000) + " sec");
 };

 public static void main(String[] args) throws InterruptedException {
  new ListTest().testListModify();
 }
}

執行結果:
ArrayList time : 4 sec
LinkedList time : 128 sec
這個實驗數據很重要，因為常常看到網路上文章提到，LinkedList在進行插入動作時候效能
是優於ArrayList，但是實驗數據出來差異頗大。

3.3 比較兩者依序插入資料效能

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

public class ListTest {
 //資料大小
 int dataSize = 100000;
 // 紀錄開始時間
 long[]   testBaginTime = new long[4];
 // 紀錄結束時間
 long[]   testEndTime  = new long[4];
 // 基本資料長度
 Integer[]  ia    = new Integer[dataSize];
 // 初始化隨機物件
 Random   random   = new Random();
 // 初始化ArrayList
 List<Integer> arraylist  = null;
 // 初始化linkList
 List<Integer> linklist  = null;
 
 {
  // 初始化ia陣列資料
  for (int i = 0; i < ia.length; i++) {
   ia[i] = i;
  }
  arraylist = new ArrayList<Integer>(Arrays.asList(ia));
  linklist = new LinkedList<Integer>(Arrays.asList(ia));
 }

 
 void testListAdd() {
  testBaginTime[0] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   arraylist.add(i,random.nextInt(dataSize));
  }
  testEndTime[0] = System.currentTimeMillis();
  testBaginTime[1] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   linklist.add(i,random.nextInt(dataSize));
  }
  testEndTime[1] = System.currentTimeMillis();
  System.out.println("ArrayList time : " + ((testEndTime[0] - testBaginTime[0]) / 1000) + " sec");
  System.out.println("LinkedList time : " + ((testEndTime[1] - testBaginTime[1]) / 1000) + " sec");
 };

 public static void main(String[] args) throws InterruptedException {
  new ListTest().testListAdd();
 }
}

執行結果:
ArrayList time : 5 sec 
LinkedList time : 44 sec 
這個實驗數據很重要，因為常常看到網路上文章提到，LinkedList在進行插入動作時候效能 是優於ArrayList，但是實驗數據出來差異頗大。

3.4 比較兩者插入資料列首筆資料效能

     //以上類別變數可參考上面測試範例
 void testListHeadAdd(){
  testBaginTime[0] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   arraylist.add(dataSize,random.nextInt(dataSize));
  }
  testEndTime[0] = System.currentTimeMillis();
  testBaginTime[1] = System.currentTimeMillis();
  for (int i = 0; i < dataSize; i++) {
   linklist.add(dataSize,random.nextInt(dataSize));
  }
  testEndTime[1] = System.currentTimeMillis();
  System.out.println("ArrayList time : " + ((testEndTime[0] - testBaginTime[0]) / 1000) + " sec");
  System.out.println("LinkedList time : " + ((testEndTime[1] - testBaginTime[1]) / 1000) + " sec");
 }

執行結果:
ArrayList time : 7 sec 
LinkedList time : 0 sec 

4 .結論:

• 讀取資料無論是隨機或是循序，使用優先順序為ArrayList > LinkedList
• 插入資料無論是危機或是循序，使用優先順序為ArrayList > LinkedList

5.個人看法:

      從上面我所列出的資料結構圖形部分，基本的認知就是，當使用arraylist進行資料刪除候，就會產生"牽一髮動全身"的效應，所以感覺起來arraylist比較使用土方法在搬運資料。

      

       而使用linkedlist進行資料刪除時候，只要記憶體指針指向另外一個地方，就完成了看起來很快。

        但是無論使用哪一種的list，刪除元素都必須經過"找尋位置"，"執行搬運"這兩個動作，但很多時候大家都只看到了"執行搬運"這類的動作，但是缺忽略了"找尋位置"這類記憶體操作更是消耗時間，因此會有上面的測試程式這類的情形發生。

         以上是我個人研究的淺見，歡迎大家互相討論。