프로파일 - LinkedListAddEnd

>>>>>>> 소스코드.git

 

시작에 요소를 추가하는 연산은 LinkedList 클래스가 ArrayList 클래스보다 빠르다. 하지만 요소를 끝에 더하는 것은 LinkedList가 더 느리다. 여기에서는 전체 리스트를 순회하여 끝에 요소를 추가하며 선형이다. 따라서 n번 추가하는 연산의 전체 시간은 이차가 되리라 기대한다. 하지만 그렇지 않다. 소스 코드를 보자.

public static void profileLinkedListAddEnd() {
    Timeable timeable = new Timeable() {
        List<String> list;

        public void setup(int n) {
            list = new LinkedList<String>();
        }

        public void timeMe(int n) {
            for (int i = 0; i < n; i++) {
                list.add("a string");
            }
        }
    };
    int startN = 64000;
    int endMillis = 1000;
    runProfiler("LinkedList add end", timeable, startN, endMillis);
}

결과는 다음과 같다.

64000, 21
128000, 16
256000, 74
512000, 98
1024000, 416
2048000, 1039
Estimated slope= 1.2185682346724795

측정값에는 잡음이 많고 선은 완벽한 직선은 아니다. 추정 기울기는 1.21이고 요소를 시작에 추가하는 연산과 비슷하지만, 분석에서 추정한 2에는 가깝지 않다. 사실 이것은 1에 가까우며 요소를 끝에 추가하는 각 연산이 상수 시간임을 의미한다. 왜 그럴까?