컬렉션 프레임워크 - List

리스트 추상화

List 자료 구조

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

 

---

인터페이스 도입

 

다형성과 추상화를 활용하면 클라이언트 코드를 변경하지 않고, 원하는 리스트 전략을 런타임에 지정할 수 있다.

 

의존관계 주입

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

-------------------------------------------------------------
package collection.list;

public class BatchProcessorMain {

    public static void main(String[] args) {
        BatchProcessor arrayListProcessor = new BatchProcessor(new MyArrayList<>());
        arrayListProcessor.logic(100_000);

        BatchProcessor linkedListProcessor = new BatchProcessor(new MyLinkedList<>());
        linkedListProcessor.logic(100_000);

    }
}

 

실행 결과

크기: 100000, 계산 시간: 12982ms
크기: 100000, 계산 시간: 39ms

---

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

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

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

 

• 컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스에 모든 의존관계가 다 나타난다.
• BatchProcess 클래스를 보면 MyList 인터페이스만 의존한다.

 

 

 

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

 

정리

• MyList 인터페이스의 도입으로 같은 리스트 자료구조를 그대로 사용하면서 원하는 구현을 변경할 수 있게 되었다.
• BatchProcessor 클래스는 구체적인 MyArrayList나 MyLinkedList에 의존하는 것이 아니라 추상적인 MyLIst에 의존함으로써 런타임에 MyList의 구현체를 선택할 수 있다.
• 이렇게 생성자를 통해 런타임 의존관계를 투입하는 것을 생성자 의존관계 주입 또는 줄여서 생성자 주입이라 한다.
• 클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존관계 주입을 통해 구현체를 주입받아 사용함으로써, 이런 이점을 얻을 수 있다.

 

전략 패턴(Strategy Pattern)
디자인 패턴 중에 가장 중요한 패턴 중 하나이다. 전략 패턴은 알고리즘을 클라이언트 코드의 변경 없이 쉽게 교체할 수 있다. 방금 설명한 코드가 바로 전략 패턴을 사용한 코드이다.

 

---

직접 구현한 리스트의 성능 비교

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 = 10000;
        System.out.println("==MyArrayList 조회==");
        getIndex(arrayList, loop, 0);
        getIndex(arrayList, loop, size / 2);
        getIndex(arrayList, 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 추가==");
        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);
        getIndex(linkedList, loop, size / 2);
        getIndex(linkedList, loop, size - 1);

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

    }

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

    }

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

    public 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, 계산 시간: 3227ms
평균 추가 - 크기: 50000, 계산 시간: 1718ms
뒤에 추가 - 크기: 50000, 계산 시간: 3ms

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

==MyArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 276ms
findValue: 49999, 반복: 10000, 계산 시간: 492ms

==MyLinkedList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 9ms
평균 추가 - 크기: 50000, 계산 시간: 1993ms
뒤에 추가 - 크기: 50000, 계산 시간: 3607ms

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

==MyLinkedList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 864ms
findValue: 49999, 반복: 10000, 계산 시간: 1787ms

 

 

직접 만든 배열 리스트와 연결 리스트 - 성능 비교표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) -3227 ms	O(1) - 9ms
평균 추가(삭제)	O(n) - 1718ms	O(n) - 1993ms
뒤에 추가(삭제)	O(1) - 3ms	O(n) - 3607ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 657ms
검색	O(n) - 평균 256ms	O(n) - 평균 884ms

 

추가, 삭제

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

앞에 추가(삭제)

• 배열 리스트: 추가나 삭제할 위치는 찾는데 O(1) , 데이터를 한 칸씩 이동 O(n) → O(1)
• 연결 리스트:  추가나 삭제할 위치는 찾는데 O(1), 노드를 변경하는데 O(1) → O(1)

평균 추가(삭제)

• 배열 리스트:  추가나 삭제할 위치를 찾는데 O(1), 인덱스 이후의 데이터를 한칸씩 이동 O(n/2) → O(1)
• 연결 리스트:  추가나 삭제할 위치를 찾는데 O(n/2), 노드를 변경하는데 O(1)  → O(1)

뒤에 추가(삭제)

• 배열 리스트:  추가나 삭제할 위치를 찾는데  O(1), 이동할 데이터 없음 → O(1)
• 연결 리스트:  추가나 삭제할 위치를 찾는데  O(n)  노드 변경하는데 O(1) →  O(n)

인덱스 조회

• 배열 리스트: 배열에 인덱스를 사용해서 값을 O(1)로 찾을 수 있음
• 연결 리스트:  노드를 인덱스 수만큼 이동해야 함 O(n)

검색

• 배열 리스트:  데이터를 찾을 때까지 배열을 순회  O(n)
• 연결 리스트:  데이터를 찾을 떄까지 노드 순회  O(n)

시간 복잡도와 실제 성능

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

 

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

 

배열 리스트 vs 연결 리스트  

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

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

 

---

자바 리스트

List 자료구조

 

Collection 인터페이스

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

 

List 인터페이스

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

 

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

 

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, Eelement)	지정된 위치의 요소를 변경하고, 이전 요소를 반환한다.
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 특징

• 배열을 사용해서 데이터를 관리한다.
• 기본 CAPACITY는 10이다. (DEFAULT_CAPACITY = 10)
  • CAPACITY를 넘어가면 배열을 50%로 증가하낟.
  • 10 → 15 → 22 → 33 → 49로 증가한다. (최적화는 자바 버전에 따라 달라질 수 있음)
• 메모리 고속 복사 연산을 사용한다
  • ArrayList의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한칸씩 뒤로 이동시켜야 한다.
  • 자바가 제공하는 ArrayList는 이 부분을 최적화 하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 System.arrayCopy()를 사용한다.

 

자바 LinkedList 특징

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

• 이중 연결 구조는 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있다.
  • 예) node.next를 호출하면 다음 노드로, node.prev를 호출하면 이전 노드로 이동한다
• 마지막 노드에 대한 참조를 제공한다. 따라서 데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공한다.
• 이전 노드로 이동할 수 있기 떄문에 마지막 노드부터 앞으로 즉, 역방향으로 조회할 수 있다.
  • 덕분에 인덱스 조회 성능을 최적화 할 수 있다

 

---

자바 리스트의 성능 비교

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); //찾는데 O(1), 데이터 추가(밀기)O(n)
        ArrayList<Integer> arrayList = new ArrayList<>(); //조회용 데이터
        addLast(arrayList, size); //찾는데 O(1), 데이터 추가(밀기)O(1)

        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); //찾는데 O(n), 데이터 추가O(1)
        LinkedList<Integer> linkedList = new LinkedList<>(); //조회용 데이터
        addLast(linkedList, size); //찾는데 O(n), 데이터 추가O(1)

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

    }

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

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

    }
}

 

실행 결과

==ArrayList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 209ms
평균 추가 - 크기: 50000, 계산 시간: 88ms
뒤에 추가 - 크기: 50000, 계산 시간: 3ms

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

==ArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 2ms
findValue: 25000, 반복: 10000, 계산 시간: 280ms
findValue: 49999, 반복: 10000, 계산 시간: 513ms

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

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

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

 

직접 만든 배열 리스트와 연결 리스트 - 성능 비교표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) -3227 ms	O(1) - 9ms
평균 추가(삭제)	O(n) - 1718ms	O(n) - 1993ms
뒤에 추가(삭제)	O(1) - 3ms	O(n) - 3607ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 657ms
검색	O(n) - 평균 256ms	O(n) - 평균 884ms

 

자바가 제공하는 배열 리스트와 연결 리스트 - 성능 비교 표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 209ms	O(1) - 5ms
평균 추가(삭제)	O(n) - 88ms	O(n) - 1749ms
뒤에 추가(삭제)	O(1) - 3ms	O(n) - 6ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 211ms
검색	O(n) - 평균 265ms	O(n) - 평균 900ms

 

 

추가, 삭제

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

앞에 추가(삭제)

• 배열 리스트: 추가나 삭제할 위치는 찾는데 O(1) , 데이터를 한 칸씩 이동 O(n) → O(1)
• 연결 리스트:  추가나 삭제할 위치는 찾는데 O(1), 노드를 변경하는데 O(1) → O(1)

평균 추가(삭제)

• 배열 리스트:  추가나 삭제할 위치를 찾는데 O(1), 인덱스 이후의 데이터를 한칸씩 이동 O(n/2) → O(1)
• 연결 리스트:  추가나 삭제할 위치를 찾는데 O(n/2), 노드를 변경하는데 O(1)  → O(1)

뒤에 추가(삭제)

• 배열 리스트:  추가나 삭제할 위치를 찾는데  O(1), 이동할 데이터 없음 → O(1)
• 연결 리스트:  추가나 삭제할 위치를 찾는데  O(1)  노드 변경하는데 O(1) →  O(1)
  • 참고로 자바가 제공하는 연결 리스트(LinkedList)는 마지막 위치를 가지고 있다.

인덱스 조회

• 배열 리스트: 배열에 인덱스를 사용해서 값을 O(1)로 찾을 수 있음
• 연결 리스트:  노드를 인덱스 수만큼 이동해야 함 O(n)

검색

• 배열 리스트:  데이터를 찾을 때까지 배열을 순회  O(n)
• 연결 리스트:  데이터를 찾을 떄까지 노드 순회  O(n)

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

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

 

시간 복잡도와 실제 성능

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

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

 

 

 

배열 리스트 vs 연결 리스트

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

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

 

 

 

 

출처 - 김영한의 실전 자바 중급 1편