코딩 테스트를 위한 Java (2-2) - 동적 배열

이 글에서는 Java에서 제공하는 동적 배열(List 계열)에 대해 살펴봅니다.

정적 배열은 빠르고 단순하지만, 크기가 고정되어 있어 유연성이 떨어집니다.

반면 동적 배열은 크기를 자동으로 조절하며 데이터를 관리할 수 있는 자료구조입니다.

코딩 테스트에서는 문제의 크기가 가변적인 경우가 많기 때문에, 동적 배열을 적절히 활용하는 것이 중요합니다.

이번 장에서는 다음 내용을 다룹니다.

• ArrayList의 내부 동작 원리
• LinkedList의 구조와 특징
• 동적 배열의 시간 복잡도

---

1. 동적 배열(Dynamic Array)

동적 배열은 요소의 개수에 따라 자동으로 크기를 조정할 수 있는 배열 기반 자료구조입니다.

Java에서는 대표적으로 다음과 같은 동적 배열이 존재합니다.

• ArrayList: 배열 기반 동적 배열
• LinkedList: 연결 리스트 기반 구조

둘 다 같은 인터페이스(List)를 구현하므로 메서드는 동일하지만 내부 동작은 다릅니다.

---

2. ArrayList

ArrayList는 내부적으로 Object 배열을 기반으로 동작합니다.

겉보기에는 리스트이지만, 실제로는 배열과 크기 관리 로직으로 구현된 자료구조입니다.

transient Object[] elementData; // non-private to simplify nested class access

또한, ArrayList는 제네릭 기반이므로, 원시 타입을 직접 저장할 수 없습니다.

List<int> list = new ArrayList<>();     // 불가능
List<Integer> list = new ArrayList<>(); // 가능

다만 배열은 객체이므로 다음과 같은 사용은 가능합니다.

List<int[]> list = new ArrayList<>();

 

빠른 접근/수정, 추가

ArrayList는 내부적으로 배열을 사용하므로 인덱스를 통한 접근을 지원합니다.

list.get(0) // O(1), 0번 인덱스 요소 접근

또한 배열의 끝에 요소를 추가하는 연산은 평균적으로 매우 빠릅니다.

list.add(132) // amortized O(1), 요소(값) 132 추가

 

요소의 수정과 삭제는 다음과 같습니다.

list.set(0, 111); // O(N), 0번 인덱스의 요소를 111로 수정
list.remove(0); // O(N), 0번 인덱스 요소 삭제

 

resize

대부분의 Java의 동적 컬렉션은 배열 기반이며, 기존의 공간이 가득찰 경우 더 큰 배열을 생성하고, 기존 데이터를 복사하는 방식으로 가용 공간을 확장합니다.

하지만 resize는 자주 발생하지 않기 때문에 전체적으로 요소 추가는 $O(1)$의 시간 복잡도를 가집니다.

 

시간 복잡도

ArrayList는 $O(1)$의 빠른 조회(get)와 요소 추가(add)를 지원합니다.

연산 시간 복잡도

조회 (get)	O(1)
마지막 삽입	O(1) (amortized)
중간 삽입	O(N)
삭제	O(N)

반면, 중간 위치의 요소 삽입이나 삭제는 $O(N)$의 시간이 소요됩니다.

---

3. LinkedList

LinkedList는 이중 연결 리스트(Doubly Linked List) 구조입니다.

각 노드는 다음과 같이 이전/다음 노드를 참조합니다.

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

 

 

 

순차 접근

LinkedList는 인덱스를 통한 임의 접근이 불가능합니다.

따라서 특정 노드를 조회하기 위해서는 Head부터 순차적으로 탐색해야 하며, 시간 복잡도는 $O(N)$입니다.

LinkedList의 요소 순차 접근

빠른 중간 삽입/삭제

반면 중간 삽입/삭제의 경우 노드 간 연결만 변경하면 되므로, 특정 위치를 알고 있을 경우 삽입 연산은 $O(1)$의 시간 복잡도를 가집니다.

LinkedList의 요소 중간 삽입/삭제

---

4. ArrayList vs LinkedList

ArrayList와 LinkedList의 주요 연산 성능 비교는 다음과 같습니다.

항목 ArrayList LinkedList

내부 구조	ArrayList	LinkedList
조회	O(1)	O(N)
삽입/삭제	O(N)	O(1)
메모리	적음	큼
캐시 효율	좋음	나쁨

 

하지만 실제 코딩 테스트에서는 특정 위치의 삽입/삭제보다는 조회 연산이 더 빈번해 ArrayList가 자주 사용됩니다.