Java 직접 구현한 배열리스트, 연결리스트 성능 비교

#Java #ArrayList #LinkedList #Foundation #ProjectJF #Optimizer #Comparison

kiio

2025년 7월 16일 — 7 min read

직접 구현한 CList, CLinkedList를 갖고 온다.

추상화로 구현되어 있으므로 성능 측정 메소드를 만들어 측정한다.

Main.class - 데이터 맨 앞에 입력하기(First in)

public class Main {
    public static void main(String[] args) {
        int size = 77_777;
        System.out.println("**& IList 추가하기 &**");

        addFirst(new CList<>(), size);
        addFirst(new CLinkedList<>(), size);

    }
    private static void addFirst(IList<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("IList 앞의 추가 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }
}

**& CList 추가하기 &**
IList 앞의 추가 데이터 크기: 77777, 성능: 3453ms
**& CLinkedList 추가하기 &**
IList 앞의 추가 데이터 크기: 77777, 성능: 5ms

앞부분 데이터 입력 부분이 차이가 크다.
다음으로 중간에 데이터를 삽입할 경우 어떻게 되는지 살펴보자.

Main.class - addMid 중간에 데이터 삽입

private static void addMid(IList<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("IList 중간의 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
}

**& CList 추가하기 &**
IList 중간의 추가, 크기: 77777, 성능: 1848ms
**& CLinkedList 추가하기 &**
IList 중간의 추가, 크기: 77777, 성능: 2086ms

중간 삽입은 비슷비슷하다.

Main.class - addLast 마지막에 데이터 삽입

private static void addLast(IList<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("IList 마지막 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
}

**& CList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 6
**& CLinkedList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 4768ms

Main.class - 데이터 조회

public class Main {
    public static void main(String[] args) {
        int size = 77_777;
        int loop = 10_000;
        System.out.println("**& CList 추가하기 &**");
        CList<Integer> arr = new CList<>();
        addLast(arr, size);
        getIndex(arr, loop,0);
        getIndex(arr, loop,size / 2);
        getIndex(arr, loop,size - 1);


        System.out.println("**& CLinkedList 추가하기 &**");
        CLinkedList<Integer> link = new CLinkedList<>();
        addLast(link, size);
        getIndex(link, loop,0);
        getIndex(link, loop,size / 2);
        getIndex(link, loop,size - 1);
    }
    
    private static void addLast(IList<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("IList 마지막 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }

    private static void getIndex(IList<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("IList 인덱스 : " + index + ", 반복: " + loop + ", 조회 시간: " + (endTime - startTime) + "ms");
    }
}

**& CList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 5ms
IList 인덱스 : 0, 반복: 10000, 조회 시간: 0ms
IList 인덱스 : 38888, 반복: 10000, 조회 시간: 0ms
IList 인덱스 : 77776, 반복: 10000, 조회 시간: 0ms
**& CLinkedList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 4609ms
IList 인덱스 : 0, 반복: 10000, 조회 시간: 1ms
IList 인덱스 : 38888, 반복: 10000, 조회 시간: 671ms
IList 인덱스 : 77776, 반복: 10000, 조회 시간: 1306ms

Main.class - indexOf 조회

public class Main {
    public static void main(String[] args) {
        int size = 77_777;
        int loop = 10_000;
        System.out.println("**& CList 추가하기 &**");
        CList<Integer> arr = new CList<>();
        addLast(arr, size);
        search(arr, loop,0);
        search(arr, loop,size / 2);
        search(arr, loop,size - 1);


        System.out.println("**& CLinkedList 추가하기 &**");
        CLinkedList<Integer> link = new CLinkedList<>();
        addLast(link, size);
        search(link, loop,0);
        search(link, loop,size / 2);
        search(link, loop,size - 1);
    }

    private static void addLast(IList<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("IList 마지막 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }

    private static void getIndex(IList<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("IList 인덱스 : " + index + ", 반복: " + loop + ", 조회 시간: " + (endTime - startTime) + "ms");
    }

    private static void search(IList<Integer> list, int loop, int value) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(value);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("value : " + value + ", 반복: " + loop + ", 조회 시간: " + (endTime - startTime) + "ms");
    }
}

**& CList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 5ms
value : 0, 반복: 10000, 조회 시간: 1ms
value : 38888, 반복: 10000, 조회 시간: 343ms
value : 77776, 반복: 10000, 조회 시간: 503ms
**& CLinkedList 추가하기 &**
IList 마지막 추가, 크기: 77777, 성능: 4388ms
value : 0, 반복: 10000, 조회 시간: 0ms
value : 38888, 반복: 10000, 조회 시간: 598ms
value : 77776, 반복: 10000, 조회 시간: 1171ms

정리 - 성능 비교 표

기능	배열리스트	연결리스트
앞에 추가(삭제)	O(n) 3453ms	O(1) 5ms
평균 추가(삭제)	O(n) 1848ms	O(n) 2086ms
끝에 추가(삭제)	O(1) 6ms	O(n) 4768ms
인덱스 검색	O(1) 0ms	O(n) 671ms(평균)
검색	O(n) 343ms(평균)	O(n) 597ms(평균)

성능 추세 - 데이터 추가, 삭제

배열 리스트
- 맨 끝에 추가, 삭제 O(1)
- 인덱스를 통한 추가, 삭제 O(1)
연결 리스트
- 맨 앞에 추가, 삭제 O(1)

성능 추세 - 앞에 추가, 삭제

배열 리스트
- 추가 및 삭제는 O(1), 인덱스 기준으로 데이터를 모두 이동함. O(1) -> O(1)
연결 리스트
- 추가 및 삭제는 O(1), 노드만 변경함으로 O(1) -> O(1)

성능 추세 - 평균 추가, 삭제

배열 리스트
- 추가 및 삭제는 O(1), 인덱스 기준으로 데이터를 모두 이동함. O(O/2) -> O(1)
연결 리스트
- 추가 및 삭제는 O(1), 노드 변경에 O(1) -> O(n)

성능 추세 - 맨 끝 추가, 삭제

배열 리스트
- 추가 및 삭제는 O(1), 데이터 이동 없음. O(1) 고정
연결 리스트
- 추가 및 삭제는 O(n), 노드 변경에 O(1) -> O(n)

성능 추세 - 인덱스 조회

배열 리스트
- 인덱스 사용으로 바로 값을 발견함 O(1)
연결 리스트
- 노드를 인덱스만큼 이동 필요 O(n)

성능 추세 - 인덱스 조회

배열 리스트
- 데이터를 발견할 때까지 배열 순회 O(n)
연결 리스트

실제 시간 복잡도와 실제 성능의 괴리

실제 성능에는 요소의 순차 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도에 의한 요소에 영향을 받는다.
CList 요소들은 메모리에서 연속으로 위치하므로 CPU 캐시 효율이 좋다. 메모리 접근 속도가 빠르다.
CLinedList 각 요소마다 별도의 객체로 존재할 뿐 아니라 참조로 저장하기에 CPU 캐시 효율이 떨어지며, 메모리 접근 속도가 배열에 비해 느리다.
CList는 CAPACITY 넘어서면 배열을 다시 생성하고 복사하는 과정이 번거롭다. 그러나 2배씩 늘어나도록 했으므로 전체 성능에 영향을 주지 않는다.

직접 구현한 배열 리스트와 연결 리스트

배열 리스트가 성능상 유리한 부분이 많다. CPU 캐시와 메모리 접근이 낮아 속도가 빠르게 측정하고 있으므로 배열 리스트를 기본으로 사용하게 된다.
만약 채팅과 같이 맨 앞 단에 데이터를 추가하는 방식이라면 연결리스트를 사용한다.

Java 직접 구현한 배열리스트, 연결리스트 성능 비교

kiio

Main.class - 데이터 맨 앞에 입력하기(First in)

Main.class - addMid 중간에 데이터 삽입

Main.class - addLast 마지막에 데이터 삽입

Main.class - 데이터 조회

Main.class - indexOf 조회

정리 - 성능 비교 표

성능 추세 - 데이터 추가, 삭제

성능 추세 - 앞에 추가, 삭제

성능 추세 - 평균 추가, 삭제

성능 추세 - 맨 끝 추가, 삭제

성능 추세 - 인덱스 조회

성능 추세 - 인덱스 조회

실제 시간 복잡도와 실제 성능의 괴리

직접 구현한 배열 리스트와 연결 리스트

더 읽어볼 내용

Java Collection - List

언리얼 엔진 - Pawn 이동

언리얼 엔진 - 카메라 회전

Java Abstract - 컴파일, 런타임 의존 관계