[컬렉션 프레임워크] List

1. 리스트란 무엇인가?

 ☑︎ 리스트의 특징

  - 순서 보장: 데이터가 들어간 순서를 유지

  - 중복 허용: 같은 값을 여러 번 저장 가능

  - 배열과 비슷하지만 크기가 자동으로 조절됨

---

2. 직접 구현한 리스트

 ☑︎ 자바에서 제공하는 ArrayList, LinkedList를 흉내내어 기본적인 리스트 구조를 직접 구현해보자.

 

✰ 공통 인터페이스 : MyList

  - 이 인터페이스 덕분에, 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);
}

---

3. MyArrayList - 배열 기반 리스트

   ☑︎ 내부 배열 사용

   ☑︎ 배열 크기가 초과하면 grow() 메서드로 2배 확장

   ☑︎ 삽입이나 삭제 시 배열 요소를 밀거나 당겨야 해서 시간이 오래 걸림

@Override
public void add(int index, E e) {
    if (size == elementData.length) grow();
    shiftRightFrom(index);
    elementData[index] = e;
    size++;
}

 

작업	시간
앞에 추가	O(n)
뒤에 추가	O(1)
조회	O(1)

 

---

4. MyLinkedList - 연결 리스트 기반

   ☑︎ 노드(Node)를 이용하여 데이터를 연결

   ☑︎ 배열처럼 한 번에 접근 불가 -> 노드를 순회해야 한다.

   ☑︎ But, 삽입/삭제는 빠르다 (참조만 변경하면 됨!)

 

@Override
public void add(int index, E e) {
    Node<E> newNode = new Node<>(e);
    if (index == 0) {
        newNode.next = first;
        first = newNode;
    } else {
        Node<E> prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
    }
    size++;
}

작업	시간
앞에 추가	O(1)
중간 추가	O(n)
조회	O(n)

---

5. 다형성 & 의존관계 주입

   ☑︎ 리스트 전략을 바꾸기 위해 MyList 인터페이스를 활용한 의존관계 주입을 적용할 수 있다

 

public class BatchProcessor {
    private final MyArrayList<Integer> list = new MyArrayList<>();
}

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

✅ MyArrayList, MyLinkedList 중 어떤 구현체를 사용할지는 생성자 주입으로 런타임에 결정할 수 있게 되었다!

---

6. 성능 비교 : 직접 테스트 해보기

 ☑︎ 앞에 추가

 - MyArrayList: O(n) → 모든 요소를 한 칸씩 밀어야 함

 - MyLinkedList: O(1) → 참조만 바꾸면 됨

 

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

 ☑︎ 중간 추가

 - 둘 다 평균적으로는 O(n)

 - 하지만 MyArrayList는 내부적으로 메모리 복사를 더 효율적으로 처리

 

 ☑︎ 뒤에 추가

- MyArrayList: O(1) (단, 가끔 grow)

 - MyLinkedList: O(n) (마지막 노드 탐색 필요)

---

7. 자바 컬렉션 프레임워크의 List

 ☑︎ 자바는 기본적으로 List 구현체를 제공한다.

 ☑︎ 실무에서는 대부분 ArrayList를 기본으로 사용한다

 ☑︎ 앞쪽에서 자주 추가/삭제하는 경우에는 LinkedList도 고려해볼만 한다.

기능	ArrayList	LinkedList
앞에 추가	O(n)	O(1)
뒤에 추가	O(1)	O(1)
조회	O(1)	O(n)
검색	O(n)	O(n)

 

---

8. 정리

☑︎ List는 순서를 보장하고 중복을 허용하는 자료구조이다.

☑︎ ArrayList는 배열 기반, LinkedList는 노드 기반

☑︎ 인터페이스 기반 설계를 하면 다양한 구현체로 쉽게 전략을 바꿀 수 있다.

☑︎ 실제 성능은 단순한 시간 복잡도뿐 아니라 CPU 캐시, 메모리 구조 등도 영향을 미친다.

☑︎ 자바의 ArrayList는 메모리 고속 복사 등 최적화가 잘 되어 있어 실무에서는 더 많이 쓰인다.

 

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 6. 컬렉션 프레임워크 List