[김영한의 실전 자바 중급편2] Collection-List 구현 최종

jkky98·2024년 6월 9일

Java

목록 보기

27/51

InterFace 도입

이전에 직접 구현한 ArrayList 와 LinkedList의 public 메서드들은 내부로직만 다를 뿐 동일한 이름으로 구현되어있다. 이를 통합할 하나의 인터페이스를 구성하고, 만든 두 리스트 클래스를 구현하는 방식으로 동작하기 위해 MyList 인터페이스를 도입한다.

package collection.list;

public interface MyList <E> {
    int size();

    void add(E e);

    void add(int index, E e);

    E get (int index);

    E set(int index, E element);

    E remove(int index);

    int indexOf(E o);
}

의존관계 주입

package collection.list;

public class BatchProcessor {
    private final MyArrayList<Integer> list;

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

위와 같은 BatchProcessor는 logic 메서드를 통해 리스트의 0번째 부분에 엄청난 양의 데이터를 계속해서 추가한다. 0번째 인덱스에 데이터를 추가하는 관점에서는 ArrayList보다 LinkedList가 훌륭하다는 점을 깨닫게 된다. 만약 위의 코드를 LinkedList로 수정한다면, BatchProcessor는 내부에서 사용하는 리스트가 MyArrayList로 고정되게 된다.

하지만, 만약 우리가 Main이라는 최종적인 부분이 존재할 때, OCP (Open/Closed Principle) 원칙에 의해 내부의 수정은 최대한 기피해야 한다. 즉, BatchProcessor의 리스트 부분에 새로운 구현체를 적용하려면 구체적 의존성을 최소화하고, BatchProcessor가 MyArrayList나 MyLinkedList와 같은 구체적 클래스에 의존하지 않도록 해야 한다.

이를 위해, 새로 만든 인터페이스를 적용하여, BatchProcessor가 구체적인 리스트 구현체에 의존하지 않도록 하고, 다양한 리스트 구현체를 유연하게 사용할 수 있도록 설계할 수 있다.

package collection.list;

public class BatchProcessor {
    private final MyList<Integer> list;

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

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

위와 같이 구성할 경우, 생성자를 추가하고 MyList 인터페이스를 도입함으로써 BatchProcessor 내부의 리스트 사용에 대한 결정을 호출한 쪽으로 미룰 수 있다. 즉, 만약 main에서 BatchProcessor 객체를 생성한다면, 생성자를 통해 리스트 자료구조를 선택할 수 있게 된다. 이전 구조에서는 BatchProcessor 클래스 내부에서 리스트 구현체가 고정되어 있었으므로, 만약 다른 자료구조를 사용하려면 BatchProcessor 클래스를 수정해야 했다.

이 방식은 BatchProcessor의 외부에서 의존관계를 결정하게 되어, BatchProcessor 인스턴스에 들어오는 리스트 구현체가 외부에서 주입된다는 점에서 의존관계 주입(Dependency Injection, DI)을 활용한 설계이다. 이를 통해 유연한 의존성 관리가 가능하고, 클래스 변경 없이 새로운 리스트 구현체를 적용할 수 있다.

Main

package collection.list;

public class BatchProcessorMain {
    public static void main(String[] args) {

        BatchProcessor processor = new BatchProcessor(new MyArrayList<Integer>());
        processor.logic(100_000);

        BatchProcessor processor1 = new BatchProcessor(new MyLinkedList<Integer>());
        processor1.logic(100_000);
    }
}

우리의 목적대로 main에서 두 리스트를 넣어 테스트해볼 수 있었다. 의존관계주입의 구조로 설계 하지 않았다면 BatchProcessorArrayList, BatchProcessorLinkedList와 같은 각각의 구현 리스트를 실행시킬 두 개의 배치 클래스가 필요했을 것이다.

실제로 10만건의 Integer데이터를 0번째에 추가하는 작업시에 MacOs M1기준으로 다음과 같은 속도차이를 보였다.

Compile-Time 의존관계

컴파일 타임 의존관계는 자바 컴파일러가 처리하는 의존관계이다. 예를 들어, BatchProcessor는 MyList에 의존하며, MyArrayList와 MyLinkedList는 MyList 인터페이스에 의존한다. 따라서, 현재 예시 구조에서는 컴파일 시점에 BatchProcessor, MyArrayList, MyLinkedList 모두가 MyList 인터페이스에 의존하고 있다고 할 수 있다.

이러한 구조에서는 BatchProcessor와 리스트 구현체들이 MyList 인터페이스에 의존하고, 실제 사용되는 구체적인 리스트 구현체는 런타임 시에 결정된다. 이를 통해 유연한 의존성 주입(Dependency Injection)이 가능해진다.

Runtime 의존관계

런타임 의존관계는 실제 프로그램이 실행될 때 발생하는 의존관계이다. 예를 들어, Main에서 MyList의 생성자로 MyArrayList를 선택했다면, 런타임 의존관계에서 BatchProcessor는 실질적으로 MyArrayList에 의존하게 된다. 즉, MyList 인터페이스를 통해 외부에서 선택된 MyArrayList가 실제로 동작을 시작하는 것이다. 따라서, 런타임에서 실제 동작하는 것은 MyList가 아닌 MyArrayList임을 알 수 있다.

이러한 방식은 의존성 주입(Dependency Injection)을 통해 런타임 시에 의존관계를 동적으로 결정할 수 있음을 의미한다. 이를 통해 유연한 설계가 가능해지고, 다양한 구현체를 쉽게 교체할 수 있다.

List of Collection Framework

MyList를 통해 직접 인터페이스 아래의 ArrayList와 LinkedList를 구현했다. 이제는 자바가 제공하는 Collection의 리스트로 대체해보려고 한다.

위 이미지는 자바의 Collection Framework의 계층 구조를 보여준다. 우리는 왼쪽 부분에 있는 List 인터페이스의 일부를 구현했다. 실제로 List 인터페이스는 Collection 인터페이스의 구현체로, Collection이 Set과 List를 포함하는 더 큰 구조를 형성하고 있음을 알 수 있다.

Java ArrayList

자바가 제공하는 ArrayList는 직접 구현한 MyArrayList와 비슷하지만 더 개선된 성능과 더 다양한 메서드들을 지원한다.

메모리 고속 복사 연산

우리의 MyArrayList에서 추가나 삭제 연산 시 기존 데이터들이 for문을 통해 한 칸씩 밀어냈다. 반면, 실제 자바의 ArrayList는 메모리 고속 복사 연산인 System.arraycopy()를 사용하여 더 나은 속도를 구현한다.

즉, 자바의 ArrayList는 데이터 하나하나를 일일이 이동시키는 것이 아니라, 한 번에 묶어서 시스템 레벨에서 복사하여 데이터를 효율적으로 처리한다.

Java LinkedList

이중 연결 리스트

우리의 MyLinkedList의 경우 단일 연결리스트로 구현했었다. 실제로 자바 컬렉션의 LinkedList는 이중 연결리스트로 구현되어있다. 즉 들어가는 문을 양 끝에 두어 앞쪽에서의 접근 뿐만 아니라 뒤쪽에서의 접근도 열어둔 것이다.

이렇게 되면 만약 접근해야할 인덱스가 길이의 반을 넘어가면 last에서 접근하는 것이 더 빠를 것이다. 즉 이중 연결 리스트 구조에서 아파트 0~10단지까지 있을 때 가장 오래걸려 도착할 단지는 5단지가 된다.

실제 적용

MyList -> List
MyArrayList -> ArrayList
MyLinkedList -> LinkedList

기존의 코드를 위처럼 수정해서 자바의 컬렉션 List를 사용해보자. 실제로 이전에 예시에 제작한 코드들의 메서드의 틀은 이름만 바꿔도 문제없게 코딩되어있다.

package collection.list;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class JavaListPerformanceTest {
    public static void main(String[] args) {
        int size = 50_000;
        System.out.println("==ArrayList 추가==");
        addFirst(new ArrayList<>(), size);
        addMid(new ArrayList<>(), size);
        ArrayList<Integer> arrayList = new ArrayList<>();
        addLast(arrayList, size);

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


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


        System.out.println("==LinkedList 추가==");
        addFirst(new LinkedList<>(), size);
        addMid(new LinkedList<>(), size);

        LinkedList<Integer> linkedList = new LinkedList<>();
        addLast(linkedList, size);

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

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

    private static void addFirst(List<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(List<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(List<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(List<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(List<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");
    }
}

input데이터를 똑같이 5만건을 하여 My시리즈와 자바가 제공하는 List들과 비교한 표는 다음과 같다.

배열 고속 복사로 자바 ArrayList의 전체적인 속도가 상승했으며, 연결리스트의 끝 부분 추가에 대한 속도도 눈에 띄게 개선되었다. 하지만 조회와 검색에 있어서는 우리가 직접 만든 버전과 크게 차이가 나지 않았다.

이론 vs 실제

자바가 제공하는 리스트들을 비교해보면, 대부분의 경우 ArrayList가 유리하다는 점을 느낄 수 있다. 실제 실무에서는 99% 이상 ArrayList가 사용된다. 이론적으로는 평균적인 추가 부분에서 속도가 비슷하거나 LinkedList가 우수할 것이라고 예상했지만, 실제로는 ArrayList가 훨씬 빨랐다.
이는 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소가 영향을 미쳤기 때문이다. 메모리 고속 복사의 영향도 있다. ArrayList는 기존의 배열을 더 중점적으로 이용하기 때문에 데이터들이 연속적으로 메모리 상에 위치하게 되어, CPU 캐시 효율이 높아지고 메모리 접근 속도가 빨라진다.

하지만 O(1)에서 추가 및 삭제에서는 여전히 LinkedList가 우위를 점한다. 배열 고속 복사 기능이 적용되더라도, 주소 해제와 추가만 이루어지는 LinkedList의 로직보다 여전히 느릴 수밖에 없다. 99%의 경우는 ArrayList가 유리하지만, 1%의 예외는 "엄청난 양의 데이터 추가 및 삭제가 주로 이루어질 때"일 수 있다. 이때는 LinkedList가 유리할 수 있다.

이번 실습을 통해 Collection - List - (ArrayList, LinkedList)로 이어지는 설계를 다루면서 전략 패턴에 대한 익숙함을 얻을 수 있었고, 실제로 수 년 이상 최적화된 자료구조들이 실무에서 어떻게 쓰이는지, 특히 "대부분의 경우 ArrayList가 성능상 유리하다"는 결론을 내리게 되었다. 직접 코드를 작성하고 테스트를 진행하며 이론적으로 배운 것을 실제로 어떻게 구현할 수 있는지, 가장 많이 사용되는 List의 실제 구현을 깊이 있게 공부할 수 있었다.