Linked, ArrayList 누가누가 더 빠를까요?

Array를 먼저 비교하려 했지만, 그냥 하나의 테스트가 완성되면 바로 글로 쓰려한다.

왜?

그냥 궁금했다. 직접 눈으로 보고싶었다.

직접 실험해 보자!!

이 글을 이제서야 작성하는 이유는 아직도 잘 확인하지 못한 이유도 있지만
최대한 직접 테스트 해보고 싶었기 때문이다.

일단 첫번째 실험은 순차적인 입력이다.

// main
int testLength = 100_000;

ArrayList<String> testArrList = new ArrayList<>();
LinkedList<String> testLinkedList = new LinkedList<>();

System.out.println("Start ArrayList : " + FromStart.sequenceAdd(testArrList, TEST_ADD, testLength));
System.out.println("Start LinkedList : " + FromStart.sequenceAdd(testLinkedList, TEST_ADD, testLength));

// start class
public static Long sequenceAdd(List<String> list, String testStr, int testLength) {
    long before = System.currentTimeMillis();
    for (int i = 0; i < testLength; i++) {
        list.add(testStr);
    }
    long after = System.currentTimeMillis();
    return (after - before);
}

위 코드의 실행 결과 임의의 문자열 100,000개를 집어 add() 한 결과
ArrayList : 3
LinkedList : 3

그럼 중간부터 실험한 결과는 어떻게 될까?

// main
int testLength = 100_000;

ArrayList<String> testArrList = new ArrayList<>();
LinkedList<String> testLinkedList = new LinkedList<>();

System.out.println("Middle ArrayList : " + FromMiddle.sequenceMiddleAdd(testArrList, testLength));
System.out.println("Middle LinkedList : " + FromMiddle.sequenceMiddleAdd(testLinkedList, testLength));

// middle class
public static Long sequenceMiddleAdd(List<String> list, int testLength) {
    long before = System.currentTimeMillis();
    for (int i = 0; i < testLength; i++) {
        list.add(500, "테스트");
    }
    long after = System.currentTimeMillis();
    return (after - before);
}

당연하게 LinkedList가 빠를거라는 예상과는 다르게
ArrayList : 1224, LinkedList : 10311이라는 시간이 나왔다.

다른 결과는?

이번엔 반복문의 길이를 500으로 줄이고 다시 테스트 해봤다.

// main
int testLength = 100_000;

ArrayList<String> testArrList = new ArrayList<>();
LinkedList<String> testLinkedList = new LinkedList<>();

System.out.println("Middle ArrayList : " + FromMiddle.sequenceMiddleAdd(testArrList, testLength));
System.out.println("Middle LinkedList : " + FromMiddle.sequenceMiddleAdd(testLinkedList, testLength));

// middle class
public static Long sequenceMiddleAdd(List<String> list, int testLength) {
    long before = System.currentTimeMillis();
    for (int i = 0; i < testLength; i++) {
        list.add(500, "테스트");
    }
    long after = System.currentTimeMillis();
    return (after - before);
}

이번 결과는 예상대로 LinkedList가 더욱 빨랐다.
ArrayList : 1828
LinkedList : 97

왜 이런 결과가 나왔을까?

내가 알기로 LinkedList는 연결리스트로 요소의 추가 삭제가 빠르고,
ArrayList는 중간에 요소를 추가할 경우 모든 요소들을 하나씩 밀어야 하기 때문에
당연히 LinkedList가 빠르다고 생각했다.

공부해본 결과 간단히 설명하자면

ArrayList는 [1,2,3,4,5,6]의 3과4 사이에 7이라는 수를 삽입하려면
4,5,6을 이동시키는 시간이 걸린다.

LinkedList는 각 요소가 다음 요소와 이전 요소와 연결되어 있다.
따라 1 <-> 2 <-> 3 <-> 4 <-> 5 <->의 형식으로 되어있는데
여기서 6을 4의 자리에 삽입하려면 4까지 탐색하는 과정의 시간이 들어간다.

때문에 반복문을 500으로 할 경우에는 뒤로 밀어야할 요소가 많은 ArrayList가
더욱 많은 시간이 걸렸지만

100,000의 절반인 50,000으로 테스트하면 LinkedList는 50,000번의
탐색을 시도한 후 삽입을 진행하기 때문에 더욱 많은 시간이 걸리는 것이었다. 😱