자바 중급 2편 - List(2)

📌 컴파일 타임(Compile Time) vs 런타임(Runtime) 의존관계

• 컴파일 타임(Compile Time)
  • 코드를 컴파일하는 시점
  • 자바 컴파일러가 보는 의존관계
  • 클래스 소스 코드 상에 정적으로 보이는 의존관계
  • 실행하지 않아도 보이는 관계
• 런타임(Runtime)
  • 프로그램 실행 시점
  • 실제 생성된 인스턴스들이 서로 참조하는 동적인 의존관계
  • 실행 중에 변경될 수 있음

 

컴파일 타임 의존관계

public class BatchProcessor {
    private final MyList<Integer> list; // 인터페이스 타입에만 의존

    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }

    public void logic(int size) {
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
    }
}

 

• BatchProcessor는 코드상 MyList 인터페이스만 의존
• MyArrayList나 MyLinkedList 구체 클래스에 대한 정보는 코드에 없음
• 이 상태를 컴파일 타임 의존관계라고 함

 

런타임 의존관계

MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor processor = new BatchProcessor(list); // 주입
processor.logic(50_000);

 

 

• 실행 시점에 MyList의 구현체로 MyArrayList 객체를 생성해서 주입
• 결과적으로 실행 중에는 BatchProcessor가 MyArrayList 인스턴스를 사용

MyLinkedList<Integer> list = new MyLinkedList<>();
BatchProcessor processor = new BatchProcessor(list); // 주입
processor.logic(50_000);

 

 

• 런타임에 MyLinkedList를 주입하면 실행 시점 의존관계가 변경됨
• 코드는 수정 없이 구현체를 교체 가능

 

컴파일 타임 의존관계

• 클래스 코드에서 어떤 타입(클래스, 인터페이스)에 의존하는지 나타냄
• BatchProcessor는 MyList 인터페이스에만 의존 → 구현 변경이 자유로움

 

런타임 의존관계

• 프로그램 실행 시점에 어떤 객체 인스턴스가 실제로 주입되고 사용되는지
• DI(Dependency Injection)를 통해 유연하게 변경 가능

 

장점

• OCP(개방-폐쇄 원칙) 준수 → 코드 수정 없이 새로운 구현체 확장 가능
• 런타임에 전략(알고리즘)을 교체하는 전략 패턴 적용 가능

 

. 전략 패턴(Strategy Pattern) 

• 전략(Strategy) = 알고리즘 인터페이스 (MyList)
• 구체 전략(Concrete Strategy) = 알고리즘 구현체 (MyArrayList, MyLinkedList)
• 컨텍스트(Context) = 전략을 사용하는 클래스 (BatchProcessor)
• 전략 패턴을 사용하면 클라이언트 코드 변경 없이 알고리즘 교체 가능

 

MyArrayList vs MyLinkedList 성능비교

 

package com.example.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> list = new MyArrayList<>(size);


        addLast(list, size); // 찾는데 O(1), 데이터 추가 O(1)


        int loop = 10000;

        System.out.println("== MyArrayList 조회 ==");

        getIndex(list, loop, 0); // 앞 조회
        getIndex(list, loop, size / 2); //중간 조회
        getIndex(list, loop, size - 1); // 마지막 조회

        System.out.println("== MyArrayList 검색 ==");

        search(list, loop, 0); // 앞 조회
        search(list, loop, size / 2); //중간 조회
        search(list, loop, size - 1); // 마지막 조회


        System.out.println("== MyLinkedList 추가 ==");

        addFirst(new MyLinkedList<>(), size);
        addMid(new MyLinkedList<>(), size); // 찾는데 O(n), 데이터 추가 O(1)

        MyLinkedList<Integer> list1 = new MyLinkedList<>();
        addLast(list1, size); // 찾는데 O(n), 데이터 추가 O(1)


        System.out.println("== MyLinkedList 조회 ==");

        getIndex(list1, loop, 0); // 앞 조회
        getIndex(list1, loop, size / 2); //중간 조회
        getIndex(list1, loop, size - 1); // 마지막 조회

        System.out.println("== MyLinkedList 검색 ==");

        search(list1, loop, 0); // 앞 조회
        search(list1, loop, size / 2); //중간 조회
        search(list1, 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.indexOf(findValue);

        }

        long endTime = System.currentTimeMillis();

        System.out.println("findValue : " + findValue +", 반복 : " + loop + ", 계산시간 : " + (endTime - startTime) + "ms");

    }
}

 

➤ 추가(삽입) 성능

• 앞에 추가
  • MyArrayList: O(n) → 1349ms
  • MyLinkedList: O(1) → 2ms
• 평균(중간) 추가
  • MyArrayList: O(n) → 638ms
  • MyLinkedList: O(n) → 1066ms
• 뒤에 추가
  • MyArrayList: O(1)→ 2ms
  • MyLinkedList: O(n) → 2169ms (단일 연결 + 꼬리 포인터 없음)

 

➤ 조회(인덱스 접근) 성능

• MyArrayList: index 0/중간/끝 모두 ≈0ms (O(1))
• MyLinkedList: index 0 1ms, 중간 438ms, 끝 873ms (O(n))

 

➤ 검색(값 탐색) 성능

• MyArrayList: 0 0ms, 중간 115ms, 끝 222ms (O(n))
• MyLinkedList: 0 0ms, 중간 492ms, 끝 983ms (O(n))

 

기능	배열 리스트(MyArrayList)	연결 리스트(MyLinkedList)
앞에 추가/삭제	O(n) – 1369ms	O(1) – 2ms
평균(중간) 추가/삭제	O(n) – 651ms	O(n) – 1112ms
뒤에 추가/삭제	O(1) – 2ms	O(n) – 2195ms
인덱스 조회	O(1) – 1ms	O(n) – 평균 438ms
검색	O(n) – 평균 115ms	O(n) – 평균 492ms

 

 

 

📌정리

• 직접 구현 버전 기준, 앞삽입은 LinkedList가 압도적, 뒤삽입은 ArrayList가 매우 유리.
• 중간 삽입은 이론상 비슷해도 실측에선 ArrayList가 더 빠를 가능성이 높음(캐시/메모리 복사 최적화 때문).
• 조회는 무조건 ArrayList 강세.
• 실무에선 ArrayList 기본, 특수 케이스(앞삽입 빈번)만 LinkedList 고려