자바 컬렉션 프레임워크

자바 컬렉션 프레임워크는 List, Set, Map 세 가지 주요 인터페이스를 중심으로 다양한 구현체를 제공합니다
각 구현체는 내부 데이터 구조에 따라 시간 복잡도, 메모리 특성, 그리고 특정 연산에서의 성능이 달라집니다

List 계열: 순서 있는 요소, 중복 허용

ArrayList:

동적 배열 기반의 리스트로, 원소를 순차적으로 저장하며 필요에 따라 배열 크기를 동적으로 확장합니다

성능

조회(get)의 시간복잡도가 O(1)로 빠르며, 맨 뒤에 추가(add)되는 것도 O(1)로 빠릅니다
이는 배열의 연속적인 메모리 할당 덕분에 메모리 지역성이 우수하여 캐시 효율이 높기 때문입니다

하지만 "중간 요소를 삽입/삭제하거나 그 위치에서 이후의 요소들을 한 칸씩 밀거나 당겨야 하기 때문에 O(n) 시간이 걸립니다
그중 맨 앞의 삭제는 가장 느린 O(n) 비용이 발생합니다

메모리

배열로 원소를 연속 저장하므로 메모리 지역성(locality)이 좋아 반복 접근이 빠릅니다
다만 사용 중이지 않은 만큼에 대해서는 공간을 차지한다는 단점이 있습니다

사용해야하는 상황

인덱스를 통한 빠른 접근과 순차적 처리가 필요한 경우에 가장 적합합니다
요소 추가/삭제가 주로 리스트 끝에서 발생하는 경우 효율적입니다.

사용하지 말아야 하는상황

맨 앞이나 중간에 빈번한 삽입/삭제가 발생하면 성능 저하가 크기 때문에 빈번한 추가/삭제가 있는 경우 피하는 것이 좋습니다
또한 멀티스레드 환경에서는 Thread-Safe하지 않아 Collections.synchronizedList 등으로 감싸는 방법을 선택해야 합니다

LinkedList

이중 연결 리스트 기반으로, 각 요소(Node)가 이전/다음 노드의 참조를 가집니다
List 외에 Deque(양쪽 끝 삽입/삭제) 및 Queue 인터페이스도 구현할 수 있습니다

성능

조회(get)의 시간복잡도는 O(n)으로 상대적으로 느립니다.
그 이유는 원소를 찾을 때까지 순차적으로 각 노드를 탐색하기 떄문입니다
반면 맨 앞/뒤에 추가(addFirst/Last)는 노드 연결만 변경하면 되기 때문에 O(1)의 시간복잡도를 가집니다

중간 삽입/삭제도 해당 위치 노드 참조를 알고 있으면 노드 연결 변경만으로 O(1)에 가능하지만,
일반적으로는 탐색 후 작업하기 때문에 평균 O(n)의 시간복잡도를 가집니다

메모리

각 요소를 담는 노드 객체가 별도로 존재하고,
노드마다 데이터 외에 두 개의 포인터(이전/다음 노드 참조)를 저장하므로 메모리 오버헤드가 높습니다
또한 메모리 비연속성으로 캐시 지역성이 떨어져 성능도 저하될 수 있습니다

사용해야하는 상황

리스트의 처음이나 끝에서 빈번한 삽입/삭제가 일어나는 경우 성능상 이점이 있으므로 사용하기 좋습니다

사용하지 말아야 하는상황

조회가 느리고(O(n)), 메모리 사용량이 많습니다
심지어 순차 반복조차 ArrayList보다 느린 경우가 많습니다

Vector

ArrayList와 유사한 동적 배열 기반이지만,
모든 메소드가 synchronized로 동기화되어 Thread-Safe합니다

성능

단일 스레드 상황에서 ArrayList보다 약간 느립니다. 이유는 동기화 오버헤드 때문입니다
멀티스레드 환경에서 Thread-Safe하다는 장점을 제공합니다

참고

• 자바 성능 튜닝 이야기 - 4챕터