[Java/김영한] List

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요. 🤗

 

 

 

리스트 추상화

인터페이스 도입

순서가 있고 중복을 허용하는 자료 구조를 리스트(`List`)라 한다. `MyArrayList`와 `MyLinkedList`는 내부 구현만 다를 뿐 같은 기능을 제공하는 리스트이다. 이 둘의 공통 기능을 인터페이스로 뽑아서 추상화하면 다형성을 활용한 다양한 이득을 얻을 수 있다.

 

 

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

}

 

 

앞서 만든 `MyArrayListV4`와 `MyLinkedListV4` 코드를 복사해서 `MyList` 인터페이스를 구현하는 `MyArrayList`와 `MyLinkedList`를 만들자.

public class MyArrayList<E> implements MyList<E> {
      //...
}

public class MyLinkedList<E> implements MyList<E> {
      //...
}

• 만약 메서드 정보가 다르면 오류가 발생할 수 있으니 `MyList` 인터페이스에 메서드 이름을 맞추어야 한다.
• 재정의한 메서드에 `@Override` 애노테이션을 넣어준다.

---

의존관계 주입

 

`MyArrayList`를 활용해서 많은 데이터를 처리하는 `BatchProcessor` 클래스를 개발하고 있다고 가정하자. 그런데 막상 프로그램을 개발하고 보니 데이터를 앞에서 추가하거나 삭제하는 일이 많다면 `MyArrayList`보다 `MyLinkedList`를 사용하는 것이 훨씬 효율적이다.

 

 

구체적인 MyArrayList에 의존

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`를 사용하도록 코드를 변경해야 한다면 `BatchProcessor`의 내부 코드도 `MyArrayList`에서 `MyLinkedList`를 사용하도록 함께 변경해야 한다. 

 

 

구체적인 MyLinkedList에 의존

public class BatchProcessor {

    private final MyLinkedList<Integer> list = new MyLinkedList<>(); // 코드 변경
    
    public void logic(int size) {
        for (int i = 0; i < size; i++) {
            list.add(0, i); //앞에 추가 
        }
    } 
}

 

`BatchProcessor`는 구체적인 `MyArrayList` 또는 `MyLinkedList`를 사용하고 있다. 이것을 `BatchProcessor`가 구체적인 클래스에 의존한다고 표현한다. 이렇게 구체적인 클래스에 직접 의존하면 `MyArrayList`를 `MyLinkedList`로 변경할 때마다 여기에 의존하는 `BatchProcessor`의 코드도 함께 수정해야 한다. 

 

`BatchProcessor`가 구체적인 클래스에 의존하는 대신 추상적인 `MyList`에 의존하는 방법도 있다.

 

 

추상적인 MyList에 의존

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); //앞에 추가
        }
    }

}

 

• 어떤 `MyList list`의 구현체를 선택할 지는 실행 시점에 생성자를 통해서 결정한다.
  • `MyArraylist`의 인스턴스가 들어올 수도 있고, `MyLinkedList`의 인스턴스가 들어올 수도 있다.
• `BatchProcessor`의 외부에서 의존관계가 결정되어서 `BatchProcessor` 인스턴스에 들어오는 것 같다. 마치 의존관계가 외부에서 주입되는 것 같다고 해서 이것을 의존관계 주입(DI, Dependency Injection)이라 한다.
  • 생성자를 통해서 의존관계를 주입했기 때문에 생성자 의존관계 주입이라 한다.

 

main() {
    new BatchProcessor(new MyArrayList()); //MyArrayList를 사용하고 싶을 때 
    new BatchProcessor(new MyLinkedList()); //MyLinkedList를 사용하고 싶을 때
}

 

 `BatchProcessor`를 생성하는 시점에 생성자를 통해 원하는 리스트 전략(알고리즘)을 선택해서 전달하면 된다. 이렇게 하면 `MyList`를 사용하는 클라이언트 코드인 `BatchProcessor`를 전혀 변경하지 않고, 원하는 리스트 전략을 런타임에 지정할 수 있다.

 

 

 

실행 결과를 비교해보자.

크기: 50000, 계산 시간: 1361ms // MyArrayList
크기: 50000, 계산 시간: 2ms // MyLinkedList

 

`MyLinkedList`를 사용한 덕분에 O(n) → O(1)로 훨씬 더 성능이 개선된 것을 확인할 수 있다. 데이터가 증가할 수록 성능의 차이는 더 벌어진다.

---

컴파일 타임, 런타임 의존관계

의존 관계는 크게 컴파일 타임 의존관계와 런타임 의존관계로 나눌 수 있다.

• 컴파일 타임(compile time): 코드 컴파일 시점
• 런타임(runtime): 프로그램 실행 시점

 

컴파일 타임 의존관계

 

• 컴파일 단계 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스에 모든 의존관계가 다 나타난다.
• 쉽게 이야기해서 클래스에 바로 보이는 의존관계이다. 그리고 실행하지 않은 소스 코드에 정적으로 나타나는 의존관계다.
• `BatchProcessor` 클래스를 보면 `MyList` 인터페이스만 사용한다. 코드 어디에도 `MyArraylist`나 `MyLinkedList` 같은 정보는 보이지 않는다. 따라서 `BatchProcessor`는 `MyList` 인터페이스에만 의존한다.

 

 

런타임 의존관계

 

• 런타임 의존관계는 실제 프로그램이 작동할 때 보이는 의존관계다. 주로 생성된 인스턴스와 그것을 참조하는 의존관계이다.
• 쉽게 이야기해서 프로그램이 실행될 때 인스턴스 간의 의존관계로 보면 된다.
• 런타임 의존관계는 프로그램 실행 중에 계속 변할 수 있다.

 

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

• `BatchProcessor` 인스턴스의 `MyList list`는 생성자를 통해 `MyArrayList(x001)` 인스턴스를 참조한다.
  • `BatchProcessor` 인스턴스에 `MyArrayList(x001)` 의존 관계를 주입한다.
• `logic()`을 호출하면 `MyArrayList` 인스턴스를 사용하게 된다.

 

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

 

---

직접 구현한 리스트

성능 비교

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);
        MyArrayList<Integer> arrayList = new MyArrayList<>(); //조회용 데이터로 사용
        addLast(arrayList, size);

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

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

        System.out.println("==MyLinkedList 조회==");
        getIndex(linkedList, loop, 0);
        getIndex(linkedList, loop, size / 2);
        getIndex(linkedList, 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 검색==");
        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.indexOf(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
    }
}

 

 

실행 결과

==MyArrayList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 1349ms
평균 추가 - 크기: 50000, 계산 시간: 638ms
뒤에 추가 - 크기: 50000, 계산 시간: 2ms

==MyLinkedList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 2ms 
평균 추가 - 크기: 50000, 계산 시간: 1066ms 
뒤에 추가 - 크기: 50000, 계산 시간: 2169ms

==MyArrayList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms 
index: 25000, 반복: 10000, 계산 시간: 0ms 
index: 49999, 반복: 10000, 계산 시간: 0ms

==MyLinkedList 조회==
index: 0, 반복: 10000, 계산 시간: 1ms 
index: 25000, 반복: 10000, 계산 시간: 438ms 
index: 49999, 반복: 10000, 계산 시간: 873ms

==MyArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 0ms 
findValue: 25000, 반복: 10000, 계산 시간: 115ms
findValue: 49999, 반복: 10000, 계산 시간: 222ms

==MyLinkedList 검색==
findValue: 0, 반복: 10000, 계산 시간: 0ms 
findValue: 25000, 반복: 10000, 계산 시간: 492ms
findValue: 49999, 반복: 10000, 계산 시간: 983ms

 

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	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

 

추가, 삭제

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 실제 데이터의 추가는 간단한 참조 변경으로 빠르게 O(1)로 수행된다.

---

시간 복잡도와 실제 성능

 

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

 

 

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

 

 

배열 리스트 vs 연결리스트

대부분의 경우 배열 리스트가 성능 상 유리하다. 이런 이유로 실무에서 주로 배열 리스트를 기본으로 사용한다. 만약 데이터를 아쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하면 된다.

---

자바 리스트

 

Collection 인터페이스

`java.util` 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다. 이 인터페이스는 자바에서 다양한 컬렉션(데이터 그룹)을 다루기 위해 메서드를 정의한다. `List`, `Set, `Queue`와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다.

 

 

List 인터페이스

`java.util` 패키지에 있는 컬렉션 프레임워크의 일부다. `List`는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화하는 컬렉션을 다룰 때 유연하게 사용할 수 있다.

 

`List` 인터페이스는 `ArrayList`, `LinkedList`와 같은 여러 구현 클래스를 가지고 있으며, 각 클래스는 `List` 인터페이스의 메서드를 구현한다.

 

주요 메서드

메서드	설명
`add(E e)`	리스트의 끝에 지정된 요소를 추가한다.
`add(int index, E element)`	리스트의 지정된 위치에 요소를 삽입한다.
`addAll(Collection<? extends E> c)`	지정된 컬렉션의 모든 요소를 리스트의 끝에 추가한다.
`addAll(int index, Collection<? extends E> c)`	지정된 컬렉션의 모든 요소를 리스트의 지정된 위치에 추가한다.
`get(int index)`	리스트에서 지정된 위치의 요소를 반환한다.
`set(int index, E element)`	지정된 위치의 요소를 변경하고, 이전 요소를 반환한다.
`remove(int index)`	지정된 위치의 요소를 제거하고 그 요소를 반환한다.
`remove(Object o)`	리스트에서 지정된 첫 번째 요소를 제거한다.
`clear()`	리스트에서 모든 요소를 제거한다.
`indexOf(Object o)`	리스트에서 지정된 요소의 첫 번째 인덱스를 반환한다.
`lastIndexOf(Object o)`	리스트에서 지정된 요소의 마지막 인덱스를 반환한다.
`contains(Object o)`	리스트가 지정된 요소를 포함하고 있는지 여부를 반환한다.
`sort(Comparator<? super E> c)`	리스트의 요소를 지정된 비교자에 따라 정렬한다.
`subList(int fromIndex, int toIndex)`	리스트의 일부분의 뷰를 반환한다.
`size()`	리스트의 요소 수를 반환한다.
`isEmpty()`	리스트가 비어있는지 여부를 반환한다.
`iterator()`	리스트의 요소에 대한 반복자를 반환한다.
`toArray()`	리스트의 모든 요소를 배열로 반환한다.
`toArray(T[] a)`	리스트의 모든 요소를 지정된 배열로 반환한다.

 

---

ArrayList

`java.util.ArrayList`

 

• 배열을 사용해서 데이터를 관리한다.
• 기본 `CAPACITY`는 10이다. (`DEFAULT_CAPACITY = 10`)
  • `CAPACITY`를 넘어가면 배열을 50% 증가한다.
  • 10 → 15 → 22 → 33 → 49로 증가한다. (최적화는 자바 버전에 따라 달라질 수 있다.)
• 메모리 고속 복사 연산을 사용한다.
  • `ArrayList`의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한 칸씩 뒤로 이동시켜야 한다. 
  • 자바가 제공하는 `ArrayList`는 이 부분을 최적화하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 `System.arraycopy()`를 사용한다.
    • OS, 하드웨어에 따라 성능이 다르기 때문에 정확한 측정이 어렵지만, 한 칸씩 이동하는 방식과 비교하면 보통 수 배 이상의 빠른 성능을 제공한다.

---

LinkedList

`java.util.LinkedList`

 

• 이중 연결 리스트 구조
• 첫 번째 노드와 마지막 노드 둘 다 참조

 

단일 연결 리스트

• 직접 만든 `MyLinkedList`의 노드는 다음 노드로만 이동할 수 있는 단일 연결 구조이다. 따라서 이전 노드로 이동할 수 없다는 단점이 있다.

 

이중 연결 리스트

• 자바가 제공하는 `LinkedList`는 이중 연결 구조를 사용한다. 이 구조는 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있다.
  • 예) `node.next`를 호출하면 다음 노드로, `node.prev`를 호출하면 이전 노드로 이동한다.
• 마지막 노드에 대한 참조를 제공한다. 따라서 데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공한다.
  • 인덱스 조회 성능을 최적화할 수 있다.

class Node<E> {
    E item;
    Node next;
    Node prev;
}

class LinkedList {
    Node first;  // 첫 번째 노드 참조
    Node last;   // 마지막 노드 참조
    int size;
}

---

자바 리스트의 성능 비교

기존에 만들었던 `MyListPerformanceTest` 코드를 복사해서 자바의 리스트를 사용하도록 일부 수정해서 테스트했다.

 

 

실행 결과

==ArrayList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 106ms
평균 추가 - 크기: 50000, 계산 시간: 49ms
뒤에 추가 - 크기: 50000, 계산 시간: 1ms 

==LinkedList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 2ms
평균 추가 - 크기: 50000, 계산 시간: 1116ms 
뒤에 추가 - 크기: 50000, 계산 시간: 2ms 

==ArrayList 조회==
index: 0, 반복: 10000, 계산 시간: 1ms 
index: 25000, 반복: 10000, 계산 시간: 0ms 
index: 49999, 반복: 10000, 계산 시간: 1ms 

==LinkedList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms 
index: 25000, 반복: 10000, 계산 시간: 439ms
index: 49999, 반복: 10000, 계산 시간: 1ms 

==ArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 0ms 
findValue: 25000, 반복: 10000, 계산 시간: 104ms
findValue: 49999, 반복: 10000, 계산 시간: 218ms

==LinkedList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms 
findValue: 25000, 반복: 10000, 계산 시간: 473ms
findValue: 49999, 반복: 10000, 계산 시간: 945ms

 

 

 

직접 만든 배열 리스트와 연결 리스트

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	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

 

 

자바가 제공하는 배열 리스트와 연결 리스트

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 106ms	O(1) - 2ms
평균 추가(삭제)	O(n) - 49ms	O(n) - 1116ms
뒤에 추가(삭제)	O(1) - 1ms	O(n) - 2ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 439ms
검색	O(n) - 평균 104ms	O(n) - 평균 473ms

 

 

 

데이터를 추가할 때 자바 ArrayList가 직접 구현한 MyArrayList보다 빠른 이유

• 자바의 배열 리스트는 이때 메모리 고속 복사를 사용하기 때문에 성능이 최적화된다.
• 메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략 O(n/10) 정도로 추정하자. 상수를 제거하면 O(n)이 된다. 하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.

 

시간 복잡도와 실제 성능

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

 

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