컬렉션 프레임워크 - List

 

리스트 추상화 - 인터페이스 도입

다형성과 OCP 원칙을 가장 잘 활용할 수 있는 곳 중 하나가 자료구조 이다.

 

List 자료구조 

순서가 있고 중복을 허용하는 자료 구조를 List라고 한다. 

우리가 이전에 만든 MyArrayList와 MylinkedList는 내부 구현만 다를 뿐 같은 기능을 제공하는 리스트이다.

내부 구현이 다르기에 성능은 다를 수 있지만 핵심은 같은 기능을 제공하는 것이다.

이 둘의 공통 기능을 인터페이스로 추상화 한다면 다형성을 활용한 다양한 이득을 얻을 수 있다.

 

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);
}

 

MyArrayList와 MyLinkedList에 implements MyList<E> 추가 후 @Override 어노테이션 작성해주면 

MyList를 구현하는 ArrayList와 LinkedList를 만들 수 있다.

 

리스트 추상화 - 의존관계 주입

MyArrayList를 활용해 데이터를 처리하는 BatchProcessor 클래스를 개발하고 있다고 가정해보자.

개발을 하고보니 이 클래스는 데이터를 앞에서 추가하는 일이 많은 상황이다.

이럴 땐 MyLinkedList를 사용하는 것이 훨씬 성능이 좋다.

 

package collection.list;

public class BatchProcessor {

    private final MyArrayList<Integer> list = new MyArrayList<>();

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

 

그렇다면 MyArrayList에서 MyLinkedList로 변경을 해줘야 하는데, 위 코드는 구체적인 MyArrayList에 의존하는 형태이다.

구체적인 의존이란 MyArrayList는 실제하는 클래스에 직접 의존 하고 있는 형태이다.

MyLinkedList로 변경을 하려면 BatchProcessor 클래스의 코드를 직접 변경해줘야 한다.

 

하지만 직접 변경할 필요 없이, 위에서 만든 MyList 인터페이스를 의존하는 방법이 있다.

 

package collection.list;

public class BatchProcessor {

    private final MyList<Integer> list;

    // MyList = MyArrayList
    // MyList = MyLinkedList
    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);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
    }
}

 

BatchProcessor를 생성하는 시점에 생성자를 통해서 원하는 리스트 전략(알고리즘)을 선택해서 전달하게 하면 된다.

위 코드는 클라이언트 코드인 BatchProcessor를 전혀 변경하지 않고 원하는 리스트 전략을 런타임에 지정할 수 있다.

정리하자면 추상화를 활용해 편하게 사용할 수 있게 된 것이다.

 

package collection.list;

public class BatchProcessorMain {

    public static void main(String[] args) {
//        MyArrayList<Integer> list = new MyArrayList<>();
        MyLinkedList<Integer> list = new MyLinkedList<>();

        BatchProcessor processor = new BatchProcessor(list);
        processor.logic(10000000);
    }
}

 

결과값은 따로 올리지 않겠으나 성능 차이가 굉장히 많이난다.

이 단순한 데이터를 입력하는 코드만으로도 루프를 도는데 ArrayList의 경우 건수가 커질수록 훨씬 많은 처리시간이 필요하게 되었다.

왜냐하면 logic 메서드의 for문도 O(n)이지만 list.add 메서드도 O(n)으로 O(n * n)이 되기 때문이다.

 

정리

- MyList를 의존함으로써 런타임 시점에 생성자를 통해 리스트 전략이 결정되게 되었다.

- 의존관계를 런타임에서 객체를 생성하는 시점으로 미루기 때문에 MyList의 구현체를 변경해도

   BatchProcessor 코드를 변경하지 않아도 된다.

- BatchProcessor의 외부에서 의존관계가 결정되어서 BatchProcessor 인스턴스에 들어오는 것이다.

   이것을 의존관계 주입 (DI)라고 한다.

- 생성자를 통해 의존관계를 주입했기 때문에 생성자 의존관계 주입이라고 한다.

- BatchProcessor 클래스는 추상적인 MyList에 의존하기 때문에 런타임에서도 구현체를 얼마든지 변경할 수 있다.

- 클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존관계 주입을 통해 구현체를 주입받아 사용한다.

 

전략 패턴

- 알고리즘을 클라이언트 코드의 변경 없이 쉽게 교체할 수 있는 패턴. 위의 코드가 전략패턴을 사용한 코드이다.

- MyList 인터페이스가 전략을 정의하는 인터페이스가 되고, 각각 구현체들(MyArrayList, MyLinkedList)은

  전략의 구체적인 구현이 된다. 그러므로 코드 변경없이 쉽게 교체할 수 있게 되는 것이다.

---

핵심은 재사용성이 높은 코드를 작성하려면 결정을 나중으로 미루는 것

메서드에 매개변수를 넣은 이유를 생각해보면 이해하기 편함.

매개변수가 없이 문자열을 출력하는 메서드인데 다른 문자를 출력하려면 또 메서드를 만들어야함. (재사용성 떨어짐)

매개변수가 있다면 그럴 필요 없음 (재사용성 높음)

제네릭도 똑같다. 타입 결정을 나중으로 미루면 제네릭을 통해 재사용성이 증가됨.

전략패턴도 비슷한 원리임. 지금 구체적인 타입을 정하지 않고 추상적인것에 의존해 결정을 나중으로 미루는 것

---

 

리스트 성능 비교

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 = 10_000;
        System.out.println("==MyArrayList 조회==");
        getIndex(arrayList, loop, 0); // 앞에서 조회 O(1)
        getIndex(arrayList, loop, size / 2); // 평균 조회 O(1)
        getIndex(arrayList, loop, size - 1); // 마지막 조회 O(1)

        System.out.println("==MyArrayList 검색==");
        search(arrayList, loop, 0); // 앞에서 검색 O(1)
        search(arrayList, loop, size / 2); // 평균 검색 O(n)
        search(arrayList, loop, size - 1); // 마지막 검색 O(n)

        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); // 앞에서 조회 O(1)
        getIndex(linkedList, loop, size / 2); // 평균 조회 O(n)
        getIndex(linkedList, loop, size - 1); // 마지막 조회 O(n)

        System.out.println("==MyLinkedList 검색==");
        search(linkedList, loop, 0); // 앞에서 검색 O(1)
        search(linkedList, loop, size / 2); // 평균 검색 O(n)
        search(linkedList, loop, size - 1); // 마지막 검색 O(n)
    }

    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");
    }
}

 

 

추가/삭제

배열 리스트 : 삭제할 위치를 O(1)로 빠르게 찾으나 이후에 추가할 때 데이터를 한칸씩 밀어야하므로 O(n)

연결 리스트 : 삭제할 위치를 O(n)으로 느리게 찾으나 추가할 때 간단한 참조 변경으로 O(1)

 

앞에서 추가/삭제

배열 리스트 : 위치를 찾는데 O(1), 데이터를 밀어야하므로 O(n) -> O(n)

연결 리스트 : 위치를 찾는데 O(1), 노드 변경하는데 O(1) -> O(1)

 

평균 추가/삭제

배열 리스트 : 위치를 찾는데 O(1), 데이터를 밀어야 하므로 O(n) -> O(n)

연결 리스트 : 위치를 찾는데 O(n), 노드를 변경하는데 O(1) -> O(n)

 

뒤에 추가/삭제

배열 리스트 : 위치를 찾는데 O(1), 데이터를 밀지 않아도 되므로 O(1) -> O(1)

연결 리스트 : 위치를 찾는데 O(n), 노드를 변경하는데 O(1) -> O(n)

 

인덱스 조회

배열 리스트 : 배열에 인덱스를 사용해서 한번에 찾을 수 있음 -> O(1)

연결 리스트 : 노드를 인덱스 수 만큼 이동해야 함 -> O(n)

 

검색

배열 리스트 : 데이터를 찾을 때 까지 배열을 순회 -> O(n)

연결 리스트 : 데이터를 찾을 때 까지 노드를 순회 -> O(n)

 

시간 복잡도와 실제 성능

이론적으로 LinkedList의 평균 추가 연산은 ArrayList보다 빠를 수 있다. (미는 것 보다 찾아가서 O(1)로 추가하면 되니까)

다만 실제 성능은 조금 다를 수 있다. 순차적 접근 속도, 메모리 할당 및 해제비용, CPU 캐시 활용도 등 다양한 요소에 영향을 받는다.

ArrayList는 요소들이 메모리 상에 연속적으로 위치해 CPU 효율이 좋고 메모리 접근 속도가 빠르다.

반면 LinkedList는 각 요소가 별도의 객체로 존재하고 요소의 참조를 저장하므로 CPU 캐시 효율이 떨어지고 메모리 접근 속도가

상대적으로 느릴 수 있다.

배열의 capacity가 초과해 배열을 다시 만들고 복사하는 과정이 발생한다고 해도, 이 과정은 자주 일어나는 일이 아니기 때문에

전체 성능에 큰 영향을 주지 않는다.

 

따라서 LinkedList가 효율적일 수 있지만, 컴퓨터 시스템의 구조 (메모리 접근 패턴, CPU 캐시 최적화 등)을 고려할 때

ArrayList가 실제 사용환경에서 더 나은 성능을 보여주는 경우가 많다.

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

만약 데이터를 앞쪽에 자주 추가하거나 삭제할 일이 있으면 LinkedList를 사용하는 것을 고려하면 된다.

 

자바 리스트

 

순서가 있고, 중복을 허용하는 자료 구조를 리스트라고 한다.

자바의 컬렉션 프레임워크가 제공하는 가장 대표적인 자료구조가 바로 리스트이다.

이전에 우리가 직접 구현했던 MyList, MyArrayList, MyLinkedList와 같다고 생각하면 된다.

 

Collection  인터페이스는 java.util 패키지의 핵심 인터페이스 중 하나이다.

이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다.

List, Set, Queue와 같은 다양한 하위 인터페이스와 함께 사용되며 이를 통해 데이터를 리스트, 세트, 큐 형태로 관리할 수 있다.

 

List 인터페이스의 주요 메서드는 검색을 통해 확인해보자.

 

자바 ArrayList

- 배열을 통해 데이터를 관리한다.

- 기본 CAPACITY는 10이다. 초과시 50% 증가한다.

- 메모리 고속 복사 연산을 사용한다. -> System.arraycopy()

ArrayList의 중간위치에 데이터를 추가하면 모든 요소를 한칸씩 이동 시켜야 한다. 자바가 제공하는 ArrayList는 이 부분을 최적화해서

직접 구현했을 땐 for문으로 다소 시간이 오래 걸렸으나 메모리 고속 복사연산을 사용하면 비교적 빠르게 수행이 가능하다.

 

자바 LinkedList

 

- 이중 연결 리스트 구조

- 첫번째 노드와 마지막 노드 둘다 참조

우리가 구현했던 MyLinkedList는 단일 연결 리스트이다. prev 없이 next만 있었기에 이전 노드로 이동할 수 없는 단점이 있었다.

자바 LinkedList는 이중 연결 리스트 구조이기 때문에 prev를 통해 이전 노드로 이동할 수 있다.

 

 

자바 리스트의 성능 비교

 

직접 구현했던 코드를 자바 리스트로 변경해 성능을 비교해봤다.

 

자바의 배열 리스트는 메모리 고속복사로 인해 성능이 확실히 최적화 된것을 확인할 수 있다.

연결 리스트도 마지막 노드를 참조할 수 있으므로 성능이 상승했다.

비교표를 보면 대부분 배열리스트의 성능이 더 좋다. 그렇기에 실무에서 배열 리스트를 사용한다는 것이다.

차이가 있다면 앞에서 추가/삭제 할 경우에만 차이가 있는 것이다.

 

우리가 개발할 때 앞에서 추가/삭제가 이뤄진다고 한 들, 데이터의 건수가 얼마 안되면 이 또한 성능이 크게 차이가 나는게 아니다.

따라서 배열리스트를 주로 사용하되 연결 리스트가 필요할 때를 잘 생각하고 고민해봐야 한다는 것이다.

 

결론: 배열 리스트를 쓰자. 간혹 연결 리스트를 사용하는것도 고려해볼 수 있다.