[Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해

[Java] 시간복잡도와 빅 오(Big-O) 표기의 이해

 

Collection이란?

Collection 인터페이스는 여러 개의 객체를 저장하는 구조를 추상화한 최상위 인터페이스입니다. 

즉, 객체들을 모아 관리하기 위한 공통 규격을 표준화한 인터페이스이며,
자바에서 자료구조를 사용할 때 대부분의 구조는 Collection을 기반으로 설계되어 있습니다.

Collection 인터페이스는 List, Set, Queue와 같은 다양한 하위 인터페이스의 공통 부모입니다.

이들은 모두 Collection이 정의 한 기본 기능을 공유하면서, 각각의 특징에 맞는 동작을 추가로 구현합니다.

 

Collection이 필요한 이유

만약  ArrayList, LinkedList, HashSet 등이 각자 완전히 다른 메서드를 가지고 있다면 매번 새로 배워야 합니다.

하지만, Collection이라는 공통 인터페이스가 있기 때문에 add(), remove(), 등 여러 공통 기능을 모든 자료구조가 동일한 방식으로 제공 합니다. 

 

이 덕분에 개발자는 자료구조가 달라지더라도, 기본적인 사용 방식은 동일하게 유지할 수 있습니다.

 

Collection 특징

특징	설명
객체만 저장	기본형(int, double등) 직접 저장 불가(Wrapper 클래스 사용 필요)
제네릭 지원	타입 안정성 보장
순회 가능	Iterable을 상속 하기 때문에 for-each문 사용 가능
표준 인터페이스	다양한 자료구조에 공통 규격 제공

 

Collection의 가장 큰 장점은 다형성을 활용할 수 있다는 점입니다.

Collection<String> col = new ArrayList<>();
col.add("A");
col.add("B");

 

위의 코드도 다음과 같이 쉽게 변경할 수 있습니다.

Collection<String> col = new LinkedList<>();

여기서 변경되는 것은 구현체뿐이며, 코드의 사용 방식은 그대로 유지됩니다. 즉, 구현체 교체가 자유롭고 코드 수정이 최소화되며 유지보수가 쉬워집니다. 이것이 바로 인터페이스 기반 설계의 핵심 장점입니다.

---

List 인터페이스란?

프로그래밍에서 데이터를 다룰 때 가장 많이 사용하는 구조 중 하나가 List 인터페이스입니다. List는 입력 순서를 유지하고, 중복을 허용하며 인덱스로 접근할 수 있는 자료 구조입니다. 또한 크기를 동적으로 변할 수 있어 배열보다 유연한 자료 구조 입니다.

*자료 구조 중에는 중복을 허용하지 않는 자료 구조도 있습니다.(예 : Set)

List가 필요한 이유

그렇다면 저희는 배열도 있는데 왜 굳이 List를 사용해야 할까요? 배열의 가장 큰 단점은 정적으로 크기가 고정돼 있다는 점입니다.

int[] arr = new int[3];

 

처음에 3칸으로 크기를 정하면, 더 늘릴 수 없지만 List는 필요시 자동으로 크기가 늘어납니다.

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40); // 자동 확장

즉 배열은 크기가 정해진 상자이지만, List는 필요하면 크기가 늘어나는 상자이기에 배열보다 유연한 자료구조라고 합니다.

하지만 List는 인터페이스이기 때문에, 직접 객체를 생성할 수 없습니다.

 

따라서 구현 클래스가 필요하며, 대표적인 두 가지 구현 클래스를 알아보겠습니다.

---

ArrayList

ArrayList는 동적 배열(Dynamic Array) 기반입니다. 내부적으로는 배열을 사용하며, 데이터는 연속된 메모리 공간에 저장됩니다.

이러한 구조 덕분에 인덱스를 이용한 빠른 접근이 가능하며, 데이터의 조회 속도가 매우 빠릅니다. 하지만 데이터의 중간에 삽입/삭제 시 성능 저하 문제가 발생할 수 있습니다.

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);

System.out.println(list.get(1)); // 20

 

배열의 조회 공식 : 시작주소 + (index * 데이터 크기)

위의 공식에 따라 중간 계산 없이 바로 접근이 가능하기에, 조회 시간 복잡도는 O(1)입니다.

 

그렇다면 데이터 추가할 때는 어떨까요?

앞서 설명했듯이 ArrayList는 내부적으로 배열을 사용합니다.

따라서 ArrayList의 성능을 이해하려면, 먼저 일반 배열의 데이터 추가 방식을 이해해야 합니다.

 

따라서 일반 배열의 데이터 추가 방식에 대해서 먼저 알아보겠습니다.

 

 

일반 배열의 데이터 추가

일반 배열은 크기가 고정되어 있고, 중간에 데이터를 삽입하려면 기본 데이터를 이동시켜야 합니다.

일반적인 배열은 오른쪽에 있는 데이터가 좌측의 데이터를 먼저 복사해 오고, 오른쪽으로 한 칸씩 밀어서 계속 복사합니다.

반복문을 이용한 내부 동작은 다음과 같습니다.

 

1. 마지막 요소부터 오른쪽으로 이동

2. 각 요소를 한 칸씩 뒤로 복사

3. 지정 위치에 새로운 값 삽입

 

위의 과정으로 첫 번째, 중앙 위치에 데이터를 추가하는 것은 모든 요소를 한 칸씩 뒤로 미뤄야 하기에 시간복잡도는 O(n)입니다.

배열 첫 번째 위치 추가 - O(n)

 

배열 중앙 위치 추가  - O(n)

 

배열 마지막 위치 추가  - O(1)

마지막 위치에 추가하는 것은 기존 데이터 이동이 없고, 배열의 길이를 이용해 마지막 인덱스에 바로 접근이 가능하고 즉시 저장할 수 있으며 시간 복잡도는 O(1)입니다.

 

---

ArrayList 데이터 추가 - 배열 고속 복사

ArrayList의 기본 초기 용량은 10으로, 배열이 가득 차면 기존 용량의 약 1.5배로 증가합니다.

이 과정에서는 아래와 같이 동작합니다.

 

1. 더 큰 배열을 새로 생성

2. 기존 데이터를 새 배열로 복사

3. 참조를 새 배열로 변경

 

앞에서 일반 배열은 데이터를 한 칸씩 밀어내며 이동한다고 설명했지만, ArrayList는 그렇게 비효율적으로 동작하지 않습니다.

내부적으로는 다음과 같은 메서드를 사용합니다.

System.arraycopy()

 

이 메서드는 자바 반복문으로 하나씩 복사하는 방식이 아니라, 배열의 특정 구간을 메모리 블록 단위로 한 번에 복사합니다. 즉, 데이터를 하나씩 이동시키는 것이 아니라 연속된 메모리 영역을 통째로 복사합니다.

 

System.arraycop()는 시스템 레벨에서 내부적으로 최적화된 방식으로 복사를 수행하기에 동일한 O(n)이라도 일반 반복문 복사보다 훨씬 빠르게 수행됩니다.

 

즉 ArrayList는 배열 기반이므로 데이터 이동 비용이 존재합니다.
하지만 실제 구현은 배열 고속 복사를 통해 매우 빠르게 처리되므로 평균적으로 add()의 시간 복잡도는 O(1)과 가깝게 동작합니다.

---

LinkedList

LinkedList는 이중 연결 리스트 기반의 자료 구조입니다. ArrayList가 배열을 기반으로 했다면, LinkedList는 노드(Node) 단위로 데이터를 연결하여 저장하며 연속된 메모리 공간을 사용하지 않고 첫 번째 노드와 마지막 노드 둘 다 참조합니다.

구조는 아래 코드와 같습니다.

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

 

각 노드는 서로 (이중) 연결되어 있으며, 배열처럼  연속된 메모리 공간을 사용하지 않습니다. 배열은 데이터가 실제 메모리 상에서 바로 옆 주소에 순차적으로 저장되지만, LinkedList는 각 노드가 메모리의 서로 다른 위치에 저장됩니다.

 

즉, 물리적으로는 떨어져 있지만 각 노드가 다음 노드의 참조 값을 가지고 있어서 연결되는 구조입니다.

 

LinkedList  데이터 추가

LinkedList는 배열과 달리 미리 공간을 확보할 필요가 없습니다. 데이터를 추가할 때마다 새로운 노드를 생성하여 연결하므로, 배열처럼 리사이징(Resizing) 개념이 존재하지 않습니다. 즉 저장 공간이 부족해 전체를 복사하는 과정이 없습니다.

 

연결 리스트의 데이터 추가 연산 속도는 앞 노드의 next, 뒤 노드의 preve 이 두 참조만 변경하면 되므로 삽입과 삭제는 O(1)입니다. 하지만 배열처럼 인덱스로 바로 접근할 수 없어 Node 0 -> Node 1 -> Node 2 순차적으로 이동해야 하므로 탐색은 O(n)입니다.

 

LinkedList는 중간 삽입/삭제가 빈번할 때 유리하며 리사이징 비용이 없는 장점이 있습니다.
이론적으로는 중간/삽입 연산에서 ArrayList보다 빠를 수 있지만 대부분의 경우 ArrayList의 연산 속도가 더 빠릅니다.

왜냐하면 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용 등 다양한 요소에 의해 영향을 받는데, 연결 리스트는 각 요소가 별도의 객체로 존재하고, 다음 요소의 참조를 저장하기 때문에 메모리 사용량이 증가하고 메모리 접근 속도가 상대적으로 느려져 CPU 캐시 효율이 떨어질 수 있기 때문입니다.