01. ArrayList vs LinkedList Speed Test

OS	Windows 10 Home 64bit 버전 2004 (OS 빌드 19041.630)
언어	Java 8

# 코드

public class ArrayListAndLinkedListSpeedTest {

    private static final ArrayList<Integer> ARRAY_LIST = new ArrayList<>();
    private static final LinkedList<Integer> LINKED_LIST = new LinkedList<>();

    public static void main(String[] args) {

        // 100, 100000, 1000000, 1000000
        int size = 100000;

        // 처음 데이터 추가 작업 시간
        arrayListFirstAddTime(size);
        linkedListFirstAddTime(size);
        System.out.println();

        // 중간 데이터 추가 작업 시간
        arrayListMiddleAddTime(size);
        linkedListMiddleAddTime(size);
        System.out.println();

        // 마지막 데이터 추가 작업 시간
        arrayListLastAddTime(size);
        linkedListLastAddTime(size);
        System.out.println();

//         첫번째 데이터 제거 시간
        arrayListFirstRemoveTime(size);
        linkedListFirstRemoveTime(size);
        System.out.println();

//         마지막 데이터 제거 시간
        arrayListLastRemoveTime(size);
        linkedListLastRemoveTime(size);

    }

    private static void arrayListFirstRemoveTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            ARRAY_LIST.remove(0);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("arrayListFirstRemoveTime= %.4f", time));

    }

    private static void linkedListFirstRemoveTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            LINKED_LIST.remove(0);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("linkedListFirstRemoveTime= %.4f", time));
    }

    private static void linkedListLastRemoveTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            LINKED_LIST.remove(LINKED_LIST.size()-1);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("linkedListLastRemoveTime= %.4f", time));
    }

    private static void arrayListLastRemoveTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            ARRAY_LIST.remove(ARRAY_LIST.size()-1);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("arrayListLastRemoveTime= %.4f", time));
    }

    private static void linkedListLastAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            LINKED_LIST.add(LINKED_LIST.size()-1, i);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("arrayListLastAddTime= %.4f", time));
    }

    private static void arrayListLastAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            ARRAY_LIST.add(ARRAY_LIST.size()-1, i);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("arrayListLastAddTime= %.4f", time));
    }

    private static void linkedListMiddleAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            LINKED_LIST.add((LINKED_LIST.size()-1)/2, i);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("linkedListMiddleAddTime= %.4f", time));
    }

    private static void arrayListMiddleAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            ARRAY_LIST.add((ARRAY_LIST.size()-1)/2, i);
        }
        double time = (System.currentTimeMillis() - startTime) / 1000;
        System.out.println(String.format("arrayListMiddleAddTime= %.4f", time));
    }

    private static void linkedListFirstAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            LINKED_LIST.add(i);
        }
        double time = (System.currentTimeMillis() - startTime) /1000;
        System.out.println(String.format("LinkedListFirstAddTime= %.4f", time));
    }

    private static void arrayListFirstAddTime(int size) {
        double startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            ARRAY_LIST.add(i);
        }
        double time = (System.currentTimeMillis() - startTime) /1000;
        System.out.println(String.format("ArrayListFirstAddTime= %.4f", time));
    }
}

 

# First Add Test

1000 개 반복 추가 (이미지 클릭)

 

10000 개 반복 추가 (이미지 클릭)

 

100000 개 반복 추가 (이미지 클릭)

 

100000 개 반복 추가 (이미지 클릭)

 

1000000 개 반복 추가 (이미지 클릭)

 

데이터 양이 많아 질 수록 LinkedList 가 느리다

그 이유는 검색속도 때문이다

예시	100			100000			10000000
	검색	삽입	작업 시간	검색	삽입	작업 시간	검색	삽입	작업 시간
ArrayList	1s	5s	6s	2s	5s	7s	3s	5s	8s
LinkedList	2s	1s	3s	4s	1s	5s	8s	1s	9s

삽입 속도는 1개씩 들어가서 처리하기 떄문에 같다고 치지만,

검색속도는 데이터가 추가 될 때마다 갯수가 늘어난다

ArrayList 에서는 1개 데이터가 추가될 때마다 검색속도가 1초 씩 증가 한다고 치고

LinkedList 에서는 1개 데이터가 추가 될 때마다 검색속도가 2^n초 씩 증가 한다고 친다면

데이터양이 적을 땐 LinkedList 가 빠르지만, 많아 질 수록 ArrayList 더 빨라진다