List - 리스트 추상화 4 - 직접 구현한 리스트의 성능 비교

package collection.list;

public class MyListPerformanceTest {
    public static void main(String[] args) {
        int size = 50_000;
        System.out.println("MyArrayList 추가==");
        addFirst(new MyArrayList<>(),size);
        addMid(new MyArrayList<>(),size); // 찾는데O(1), 데이터 추가O(밀기)(n)
        MyArrayList<Integer> arrayList = new MyArrayList<>(); //조회용 데이터로 사용
        addLast(arrayList,size); // 찾는데O(1), 데이터 추가O(밀기)(1)


        int loop = 10000;
        System.out.println("==MyArrayList 조회==");
        getIndex(arrayList,loop,0);
        getIndex(arrayList,loop,size/2);
        getIndex(arrayList,loop,size-1);

        System.out.println("==MyArrayList 검색==");
        search(arrayList,loop,0);
        search(arrayList,loop,size/2);
        search(arrayList,loop,size-1);


        System.out.println("MyLinkedList 추가==");
        addFirst(new MyLinkedList<>(),size);
        addMid(new MyLinkedList<>(),size); // 찾는데O(n), 데이터 추가O(1)
        MyLinkedList<Integer> linkedList = new MyLinkedList<>(); //조회용 데이터로 사용
        addLast(linkedList,size); // 찾는데O(n), 데이터 추가O(1)


        System.out.println("==MyLinkedList 조회==");
        getIndex(linkedList,loop,0);
        getIndex(linkedList,loop,size/2);
        getIndex(linkedList,loop,size-1);

        System.out.println("==MyLinkedList 검색==");
        search(linkedList,loop,0);
        search(linkedList,loop,size/2);
        search(linkedList,loop,size-1);

    }

    private static void addFirst(MyList<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0,i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }
    private static void addMid(MyList<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i/2,i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("평균 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }
    private static void addLast(MyList<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }

    private static void getIndex(MyList<Integer> list, int loop, int index){
        long startTime = System.currentTimeMillis();

        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("index : " + index + " 반복 : " + loop + " 계산 시간 : " + (endTime-startTime)+"ms");
    }
    private static void search(MyList<Integer> list, int loop, int findValue){
        long startTime = System.currentTimeMillis();

        for (int i = 0; i < loop; i++) {
            list.get(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue : " + findValue + " 반복 : " + loop + " 계산 시간 : " + (endTime-startTime)+"ms");
    }
}

 

실행 결과

MyArrayList 추가==
앞에 추가 - 크기 : 50000 계산시간 :3160ms
평균 추가 - 크기 : 50000 계산시간 :1509ms
앞에 추가 - 크기 : 50000 계산시간 :4ms
==MyArrayList 조회==
index : 0 반복 : 10000 계산 시간 : 1ms
index : 25000 반복 : 10000 계산 시간 : 1ms
index : 49999 반복 : 10000 계산 시간 : 0ms
==MyArrayList 검색==
findValue : 0 반복 : 10000 계산 시간 : 1ms
findValue : 25000 반복 : 10000 계산 시간 : 1ms
findValue : 49999 반복 : 10000 계산 시간 : 0ms
MyLinkedList 추가==
앞에 추가 - 크기 : 50000 계산시간 :4ms
평균 추가 - 크기 : 50000 계산시간 :1445ms
앞에 추가 - 크기 : 50000 계산시간 :3378ms
==MyLinkedList 조회==
index : 0 반복 : 10000 계산 시간 : 1ms
index : 25000 반복 : 10000 계산 시간 : 538ms
index : 49999 반복 : 10000 계산 시간 : 1030ms
==MyLinkedList 검색==
findValue : 0 반복 : 10000 계산 시간 : 0ms
findValue : 25000 반복 : 10000 계산 시간 : 561ms
findValue : 49999 반복 : 10000 계산 시간 : 1155ms

 

직접 만든 배열 리스트와 연결 리스트 - 성능 비교 표

성능 비교 표

 

시간 복잡도와 실제 성능

• 이론적으로 MyLinkedList의 평균 추가(중간 삽입)연산은 MyArrayList보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
• MyArrayList는 요소들이 메모리 상에서 연속적으로 위치하여 CPU캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
• 반면, MyLinkedList는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느릴 수 있따.
• MyArrayList의 경우 CAPACITY를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다. 하지만 한번에 2배씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 큰 영향을 주지 않는다.

정리하면 이론적으로 MyLinkedList가 평균 추가(중간 삽입)에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 MyArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

 

배열리스트 vs 연결 리스트

대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다.

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.