Collection & Map - 1. List
- 이번 시리즈에서는 Java의 Collection과 Map에 대해 소개합니다.
- 프레임워크의 기반이 되는 자료구조에 대한 개념은 따로 시리즈로 작성할 것이고, 본 시리즈에서는 Java에서 제공하는 자료구조들과 그에 따른 메서드들을 정리할 것입니다.
0. Java의 Collection Framework와 Map Interface
- Java에서는 데이터 구조와 알고리즘을 지원하는 강력한 표준 라이브러리를 제공하며, 이 중 Collection Framework와 Map은 데이터 관리와 처리의 핵심적인 역할을 합니다.
- 위 이미지는 주로 쓰이는 Collection Framework와 Map Interface의 상속 및 구현 관계를 제가 직접 그려본 것입니다.
- 회색으로 표시된
Vector, Stack, Hashtable은 Java 초창기에 만들어져서 하위 버전 호환을 위해 남겨진 Legacy Class들입니다.
- 구조적인 문제들이 있어서 현재는 더이상 업데이트되지 않고 거의 쓰이지 않기 때문에 본 시리즈에서도 따로 정리하진 않을 예정입니다.
- Collection Framework
- List 구현체 :
ArrayList, LinkedList
- Queue 구현체 :
PriorityQueue, ArrayDeque, LinkedList
- Deque 구현체 :
ArrayDeque, LinkedList
- Set 구현체 :
HashSet, LinkedHashSet, TreeSet
- Map Interface 구현체 :
HashMap, LinkedHashMap, TreeMap
1. List Interface - 개요
- 이번 포스팅에서는 Collection Framework의 하위 인터페이스인
List 인터페이스와 List 구현체 클래스인 ArrayList, LinkedList에 대해서 다룰 것입니다.
1.1 List 인터페이스의 개념
List는 순서가 있는 데이터를 저장할 수 있는 Collection의 하위 인터페이스로, 요소의 인덱스를 기반으로 접근하고 관리할 수 있는 특징을 가집니다.
- 배열과 유사하지만,
List는 크기가 동적으로 조절되며, 다양한 데이터 조작 메서드를 제공합니다.
List 인터페이스는 중복된 요소의 저장을 허용하며, 순서를 유지하면서 데이터를 관리합니다.
List 인터페이스는 다음과 같은 주요 기능을 제공합니다:
- 순서 유지: 삽입된 순서대로 요소를 저장하고, 필요에 따라 정렬된 순서를 유지합니다.
- 중복 허용: 동일한 요소를 여러 번 저장할 수 있습니다.
- 인덱스를 통한 접근: 배열처럼 인덱스를 통해 요소에 접근하거나, 요소를 삽입 및 삭제할 수 있습니다.
1.2 List의 주요 구현체: ArrayList와 LinkedList
List 인터페이스는 여러 구현체가 있으며, 그중 가장 많이 사용되는 것은 ArrayList와 LinkedList입니다.
- 각 구현체는
List의 기능을 구현하되, 내부적인 구조와 사용 목적에 차이가 있습니다.
ArrayList와 LinkedList는 모두 List 인터페이스를 구현하므로, 다형성에 의한 동일한 메서드를 사용하여 리스트를 처리할 수 있지만, 성능 및 메모리 효율성 측면에서 차이가 있습니다.
ArrayList
- 배열을 기반으로 하는 동적 리스트로, 요소에 대한 빠른 인덱스 접근이 가능하며, 데이터 삽입과 삭제는 상대적으로 느립니다.
- 이론적으로 데이터 삽입과 삭제가 느리다는 것일뿐, 실제로는
LinkedList보다 평균적으로 훨씬 빠릅니다.
- 다만, 요소 추가시 배열이 어느정도 차면 배열 크기를 증가시키기 때문에, 대규모 데이터를 처리할때는 성능에 영향을 줄 수 있습니다.
ArrayList는 요소의 빈번한 접근이 필요한 경우 유리하며, 읽기 중심의 작업에서 성능이 좋습니다.
LinkedList
- 이중(양방향) 연결 리스트를 기반으로 하는 리스트로, 삽입과 삭제가 빠르지만, 인덱스 기반 접근은 상대적으로 느립니다.
LinkedList는 대규모 리스트의 앞쪽 혹은 뒤쪽에서 빈번한 삽입/삭제 작업이 필요할 때 유리합니다.
Queue와 Deque 인터페이스도 구현하기 때문에, Queue나 Deque 자료 구조에서도 활용 가능합니다. (다만 이때는 ArrayDeque가 더 성능이 좋습니다.)- 중간 쪽 데이터 삽입은 이론상으론
LinkedList가 빠르지만 실제로는 ArrayList가 더 빠릅니다. (이유는 뒤에서 다시 다룰 예정입니다.)
2. List Interface - 주요 메서드
- 주요 메서드는 상당히 많기 때문에 상위 클래스 및 인터페이스에서 부터 하위 인터페이스 순서로 메서드를 정리하고자 합니다.
2.1 Object & Iterable Interface 메서드
Object 메서드
Object는 모든 클래스의 최상위 클래스이기 때문에, List 구현체들에도 상속된 메서드들이 있고 오버라이딩도 되어 있습니다.
| 메서드 | 설명 | 반환값 |
|---|
| equals(Object obj) | 두 객체가 동일한지 비교 | boolean |
| hashCode() | 객체의 해시 코드를 반환 | int |
| toString() | 객체의 문자열 표현 반환 | String |
Iterable 메서드
Iterable은 모든 컬렉션이 구현해야 하는 인터페이스로, 반복자를 생성하는 메서드가 포함됩니다.
| 메서드 | 설명 | 반환값 |
|---|
| iterator() | 컬렉션의 요소를 순차적으로 탐색할 수 있는 Iterator 반환 | Iterator<T> |
forEach(Consumer<? super T> action) | 각 요소에 대해 주어진 동작을 수행 | void |
| spliterator() | 요소의 분할 가능한 반복자를 반환 | Spliterator<T> |
2.2 Collection Interface 메서드
Collection 인터페이스는 List, Set, Queue 등 모든 컬렉션의 공통 메서드를 정의합니다.
| 메서드 | 설명 | 반환값 |
|---|
| add(T e) | 요소 추가 | boolean |
addAll(Collection<? extends T> c) | 주어진 컬렉션의 모든 요소를 추가 | boolean |
| remove(Object o) | 지정된 요소 삭제 | boolean |
removeAll(Collection<?> c) | 주어진 컬렉션에 있는 모든 요소를 삭제 | boolean |
retainAll(Collection<?> c) | 주어진 컬렉션에 있는 요소들만 유지 | boolean |
| size() | 컬렉션의 크기 반환 | int |
| isEmpty() | 컬렉션이 비어있는지 여부 확인 | boolean |
| contains(Object o) | 지정된 요소가 있는지 확인 | boolean |
| clear() | 컬렉션의 모든 요소 삭제 | void |
| toArray() | 컬렉션의 요소를 배열로 반환 | Object[] or T[] |
2.3 List Interface 메서드
List 인터페이스는 Collection 인터페이스에 추가적으로 리스트 고유의 기능을 제공합니다.
| 메서드 | 설명 | 반환값 |
|---|
| add(int index, T element) | 지정된 인덱스에 요소 추가 | void |
addAll(int index, Collection<? extends T> c) | 지정된 인덱스에 요소 추가 | void |
| remove(int index) | 지정된 인덱스의 요소 삭제 | T |
| get(int index) | 지정된 인덱스의 요소 반환 | T |
| set(int index, T element) | 지정된 인덱스에 요소 변경 | T |
| indexOf(Object o) | 지정된 요소의 첫 번째 인덱스 반환 | int |
| lastIndexOf(Object o) | 지정된 요소의 마지막 인덱스 반환 | int |
| listIterator() | 리스트 반복자를 반환 | ListIterator<T> |
| subList(int fromIndex, int toIndex) | 지정된 범위의 부분 리스트 반환 | List<T> |
3-1. List 구현체 - ArrayList
3-1.1. ArrayList란?
ArrayList는 List 인터페이스를 구현한 대표적인 동적 배열입니다.
- 내부적으로 배열을 사용해 데이터를 저장하며, 배열의 크기가 거의 차면(약 75%) 크기를 자동으로 확장(1.5배)하여 데이터를 추가로 저장할 수 있는 동적 리스트입니다.
ArrayList는 빠른 인덱스 접근이 필요할 때 유리하며, 데이터 추가 및 삭제는 상대적으로 느리지만, 실제 성능에 있어서는 매우 효율적입니다.
ArrayList 주요 특징
- 배열 기반: 내부적으로 배열을 사용하기 때문에, 요소를 인덱스 기반으로 빠르게 접근할 수 있습니다. (
O(1) 시간 복잡도)
- 동적 크기 조절: 배열의 크기가 부족할 경우,
ArrayList는 자동으로 더 큰 배열을 할당하고 기존 데이터를 복사합니다.
- 삽입/삭제 성능: 중간에 요소를 삽입하거나 삭제하는 작업은 모든 후속 요소를 한칸씩 이동해야 하므로,
LinkedList에 비해 이론적으로는 느립니다.
- 그러나 실제 환경에서는 충분히 빠르고, 대부분의 경우
ArrayList가 더 나은 성능을 보일 때가 많습니다.
- 이는 내부적으로
System.arraycopy를 통해 고속 복사를 수행하여 훨씬 빠르게 동작하도록 최적화 되어 있기 때문입니다.
3-1.2. ArrayList 사용 예시
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
List<String> fruits = new ArrayList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
fruits.add(1, "Blueberry");
System.out.println(fruits.get(2));
fruits.set(2, "Blackberry");
fruits.remove("Apple");
fruits.remove(1);
System.out.println("현재 리스트: " + fruits);
System.out.println("리스트 크기: " + fruits.size());
}
}
의존성 주입 (Dependency Injection)과 함께 사용하기
- 위 코드에서 보듯이,
ArrayList를 생성할 때 의존성 주입(DI) 개념을 적용할 수 있습니다.
List<String> fruits = new ArrayList<>();와 같은 방식으로, List 인터페이스를 참조 타입으로 사용하고, 구체적인 구현체는 ArrayList로 생성합니다.- 이 방식은 나중에
ArrayList 대신 LinkedList와 같은 다른 List 구현체로 교체하는 것이 용이하며, 코드의 유연성을 높일 수 있습니다.
- 의존성 주입 (Dependency Injection) 이란 ?
- 의존성 주입은 객체 간의 의존성을 명시적으로 주입하는 방식으로, 코드의 결합도를 낮추고 테스트 가능성을 높이는 중요한 설계 원칙입니다.
List<T> 인터페이스에 구체적인 구현체를 주입하는 방식으로 코드를 작성하는 것이 DI 원칙을 따르는 방법입니다.
List<String> fruits = new ArrayList<>();
- 의존성 주입(DI)는 Spring Framework와 같은 프레임워크에서도 핵심적으로 사용되고, IoC (Inversion of Control) 컨테이너, 등의 개념을 다룰 때 함께 설명하면 좋은 주제가 될 수 있어서 나중에 이에 대해서는 따로 다루어보겠습니다.
- 일단은
List<String> fruits = new ArrayList<>();와 같은 방식으로 유연하게 쓰면 되는구나 하고 넘어가시면 됩니다.
3-2. List 구현체 - LinkedList
3-2.1. LinkedList란?
LinkedList는 이중 연결 리스트(Doubly Linked List)를 기반으로 구현된 List 인터페이스의 구현체입니다.
- 양방향으로 연결된 노드들로 이루어져 있으며, 각 노드는 데이터와 이전/다음 노드의 참조를 가집니다.
- 대규모 데이터에서 요소의 삽입과 삭제가 빈번하게 발생할 때 유리하며, 특히 리스트의 양 끝에 요소를 추가하거나 삭제하는 작업에 강점을 가집니다.
LinkedList 주요 특징
- 연결 리스트 구조: 배열처럼 연속된 메모리 공간을 사용하지 않으며, 노드들 간의 연결로 이루어져 있습니다.
- 빠른 삽입/삭제: 리스트의 중간이나 양 끝에서 요소를 추가하거나 제거할 때 빠른 성능을 보여줍니다. (
O(1) 시간 복잡도)
- 특히, 리스트의 앞쪽이나 뒤쪽에서 추가 및 삭제 작업을 할 때 매우 유리합니다.
- 이중 연결 리스트 구조 덕분에 노드들이 양방향으로 연결되어 있어, 삽입 또는 삭제할 때 인접한 노드들만 수정하면 됩니다.
- 따라서 리스트의 중간이나 양 끝에서 삽입/삭제 작업을 할 때 매우 빠르게 처리할 수 있습니다.
- 느린 인덱스 접근: 배열처럼 인덱스를 사용해 바로 접근할 수 없고, 앞에서부터 하나씩 순차적으로 탐색해야 합니다. (
O(n) 시간 복잡도)
- 다양한 인터페이스 구현:
List, Deque, Queue 인터페이스를 모두 구현하고 있어, 스택, 큐, 양방향 큐(Deque) 등 다양한 자료 구조로 활용할 수 있습니다.
3-2.2. LinkedList 사용 예시
import java.util.LinkedList;
import java.util.List;
public class LinkedListExample {
public static void main(String[] args) {
List<String> animals = new LinkedList<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
((LinkedList<String>) animals).addFirst("Cow");
((LinkedList<String>) animals).addLast("Sheep");
animals.add(2, "Chicken");
System.out.println("첫 번째 요소: " + ((LinkedList<String>) animals).getFirst());
System.out.println("마지막 요소: " + ((LinkedList<String>) animals).getLast());
animals.remove("Dog");
((LinkedList<String>) animals).removeFirst();
((LinkedList<String>) animals).removeLast();
System.out.println("현재 리스트: " + animals);
System.out.println("리스트 크기: " + animals.size());
}
}
- 위 예제에서
List 인터페이스의 메서드가 아닌 메서드들(.addFirst(), getLast(), removeFirst(), 등)의 경우 일시적 형변환 (LinkedList<String>)을 통해 해당 기능들을 사용하실 수 있습니다.
3-2.3. LinkedList의 활용
- 큐(Queue)와 스택(Stack)으로 활용
LinkedList는 Deque와 Queue 인터페이스를 구현하고 있어, 큐 또는 스택 자료 구조로 사용할 수 있습니다. (Deque와 Queue는 다음 포스팅에서 다룰 예정입니다.)- 큐로 사용시:
addLast()와 removeFirst() 메서드를 통해 FIFO(First In, First Out) 방식으로 사용.
- 스택으로 사용시:
addFirst()와 removeFirst() 메서드를 통해 LIFO(Last In, First Out) 방식으로 사용.
import java.util.LinkedList;
import java.util.Deque;
public class LinkedListQueueExample {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addLast("A");
deque.addLast("B");
deque.addLast("C");
System.out.println(deque.removeFirst());
System.out.println(deque.removeFirst());
System.out.println(deque.removeFirst());
}
}
4. List 구현체 - 비교 및 사용 팁
4-1. LinkedList와 ArrayList 비교
| 비교 항목 | ArrayList | LinkedList |
|---|
| 내부 구조 | 배열 기반 | 이중 연결 리스트 기반 |
| 데이터 추가/삭제 | 중간 삽입/삭제 시 느림 | 양 끝 삽입/삭제 빠름 |
| 데이터 접근 | 인덱스 기반 접근 빠름 (O(1)) | 순차 접근 (O(n)) |
| 메모리 | 고정된 메모리 할당 (배열 크기만큼) | 각 노드가 추가 메모리 사용 |
4-2. List 구현체 주의점 및 사용 팁
- 빠른 삽입/삭제: 앞뒤 양쪽에서 대규모로 삽입이나 삭제가 자주 발생할 때는
LinkedList가 적합합니다.
- 대규모가 아닌 일반적인 경우엔
ArrayList를 사용하는 것이 더 나을 수 있습니다.
- 인덱스 기반 접근이 빈번할 경우: 빠른 인덱스 접근이 필요한 경우에는
ArrayList를 사용하는 것이 더 적합합니다.
Deque로 활용: 양방향 큐 자료 구조를 사용해야 할 경우 LinkedList를 활용하는 것이 효율적입니다.
실제 개발 시 사용 팁
- 일반적으로 대규모 데이터를 다룰 때는
ArrayList가 메모리와 성능 면에서 더 나은 선택일 수 있습니다.
- 특히 데이터 조회가 빈번한 애플리케이션에서는
ArrayList가 유리합니다.
- 반면에, 데이터가 자주 삽입되고 삭제되는 상황에서는
LinkedList가 더 적합합니다.
- 다만, 일반적인 환경에서는
ArrayList가 더 나은 성능을 보이는 경우가 많으니, 성능 테스트 결과에 따라 최종 선택하는 것이 좋습니다.
마무리
- 이번 포스팅에서는
List 인터페이스와 그 주요 구현체인 ArrayList와 LinkedList에 대해 알아보았습니다.
- 각 구현체는 내부 구조와 동작 방식에 따라 성능 차이가 있으며, 사용 목적과 상황에 맞는 선택이 중요합니다.
ArrayList: 요소의 빈번한 접근이 필요할 때, 읽기 중심의 작업에 적합.LinkedList: 요소의 빈번한 삽입/삭제가 필요한 경우, 큐나 스택으로 사용할 때 유리.
- 일반적으로는 요소의 빈번한 삽입/삭제가 필요해도
ArrayList가 대부분 더 나은 성능을 보이는 경우가 많음
- 다음 포스팅에서는
Queue와 Deque 구현체에 대해 알아보겠습니다.
