Collection (interface)
└── List (interface)
├── ArrayList (class)
├── LinkedList (class)
└── Vector (class)🛒 List 인터페이스
List<Integer> list;특징
- 저장 순서가 유지되는 컬렉션을 구현하는 데 사용한다.
- 같은 요소의 중복 저장을 허용한다.
- 배열과 마찬가지로 index로 요소에 접근한다.
- 리스트와 배열의 가장 큰 차이는 리스트는 자료형 크기가 고정이 아닌 가변형이다.
- 요소 사이에 빈 공간을 허용하지 않아 삽입/삭제할 때마다 배열 이동이 일어난다.
method
| method | 설명 |
|---|---|
void add(int index, Object element), boolean addAll(int index, Collection c) | index에 element 또는 컬렉션에 포함된 객체들을 추가한다. |
Object remove(int index) | index에 있는 객체를 삭제하고 삭제된 객체를 반환한다. |
Object get(int index) | index에 있는 객체를 반환한다. |
Object set(int index, Object element) | index에 있는 element를 저장한다. |
int indexOf(Object o) | index를 반환한다.(순방향) |
int lastIndexOf(Object o) | index를 반환한다.(역방향) |
List subList(int fromIndex, int toIndex) | 지정된 범위(from~to)에 있는 객체를 반환한다. |
ListIterator listIterator(), ListIterator listIterator(int index) | List의 객체에 접근할 수 있는 ListIterator를 반환한다. |
void sort(Comparator) | 지정된 비교자로 List를 정렬한다. |
🛒 ArrayList 클래스
List<Integer> arrayList = new ArrayList<>();특징
- 배열을 이용하여 만든 리스트이다.
- 데이터의 저장 순서가 유지되고 중복을 허용한다.
- 데이터량에 따라 공간이 자동으로 늘어나거나 줄어든다.
- 단방향 포인터 구조로 자료에 대한 순차적인 접근에 있어 조회가 빠르다.
- 삽입/삭제가 느리다는 단점이 있다. 순차적으로 추가/삭제하는 경우에는 가장 빠르다.
Array vs ArrayList
Array | ArrayList | |
|---|---|---|
| 크기 | 고정(생성 시 크기 결정) | 가변(자동으로 크기 조정됨) |
| 타입 | 기본 타입 가능 | 참조 타입만 가능 |
| 메모리 구조 | 연속된 메모리 공간 | 내부적으로 배열 사용하지만 유연 |
| 성능 | 빠름 | 크기 조정, 박싱/언박싱 오버헤드 존재 |
| 메소드 지원 | 없음 | 다양한 메소드 제공 |
| null 허용 | 원시 타입이면 안 됨 | 가능 |
| generic | 불가 | 가능 |
| 적합 | 고정된 데이터 처리 | 크기가 변동될 수 있는 일반적 리스트 처리에 적합 |
code
List<String> arrayList = new ArrayList<>();정렬
오름차순
Collections.sort(arrayList);내림차순
Collections.sort(arrayList, Collections.reverseOrder());
arrayList.sort((a, b) -> b.compareTo(a));리스트→배열
String[] arr = arrayList.toArray(String[]::new);배열→리스트
List<String> arrayList2 = new ArrayList<>(List.of(arr));중복 제거
arrayList = arrayList.stream().distinct().toList();빈리스트 반환
List<String> empty = Collections.emptyList();반복처리
arrayList.forEach(System.out::println);조건 필터링
arrayList = arrayList.stream()
.filter(str -> str.charAt(0) > 'P')
.toList();합계, 평균 등 집계
List<Integer> arrayList3 = List.of(10, 20, 30);
int sum = arrayList3.stream().mapToInt(Integer::intValue).sum();2차원 리스트 초기화
List<List<Integer>> matrix = new ArrayList<>();
for (int i = 0; i < 10; i++) {
matrix.add(new ArrayList<>());
}🛒 LinkedList 클래스
LinkedList<String> linkedList = new LinkedList<>();특징
- 노드(객체)를 연결하여 리스트처럼 만든 컬렉션이다.
- 데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다.
- 하지만 임의의 요소에 대한 접근 성능은 좋지 않다.
- 자바에서는 Doubly LinkedList로 이루어져 있다.
- 스택, 큐, 트리 등의 자료구조의 근간이 된다.
ArrayList vs LinkedList
ArrayList | LinkedList | |
|---|---|---|
| 내부 구조 | 동적 배열 | 이중 연결 리스트 |
| 접근 속도 | O(1) | O(n) |
| 삽입/삭제(중간) | O(n) | O(1) |
| 삽입/삭제(끝) | O(n) | O(1) |
| 메모리 사용 | 상대적으로 적음 | 노드당 추가 포인터 공간 필요 |
| 스레드 안정성 | X | X |
| 적합 | 읽기 중심, 인덱스 접근 | 삽입/삭제 중심 |
자료구조
Queue
BFS 알고리즘에서 많이 사용된다.
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int head = queue.poll();Deque
양방향 탐색, 슬라이딩 윈도우 알고리즘에서 많이 사용된다.
Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(1);
deque.offerLast(2);
deque.pollFirst();
deque.peekLast();Stack
DFS 알고리즘에서 자주 사용된다.
Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");
String top = stack.pop();code
LinkedList<String> linkedList = new LinkedList<>();정렬
오름차순
linkedList.sort(Comparator.naturalOrder());내림차순
linkedList.sort(Comparator.reverseOrder());
linkedList.sort((a, b) -> b.compareTo(a));리스트→배열
String[] arr = linkedList.toArray(String[]::new);배열→리스트
LinkedList<String> linkedList2 = new LinkedList<>(List.of(arr));중복 제거
linkedList = linkedList.stream().distinct().
collect(Collectors.toCollection(LinkedList::new));반복처리
linkedList.forEach(System.out::println);조건 필터링
linkedList = linkedList.stream()
.filter(s -> s.startsWith("W"))
.collect(Collectors.toCollection(LinkedList::new));🛒 Vector 클래스
ArrayList의 구형 버전이다.
🛒 인터페이스의 다형성
처음에 문제를 ArrayList로 선언하여 풀던 중에 인덱스로의 접근이 아닌 중간 삽입/삭제가 많을 때는 LinkedList로 바꿔 풀어야 할 때 인터페이스의 다형성을 이용하여 바꿀 수 있다. 이 둘은 List 인터페이스의 거의 동일한 메소드 등을 갖고 있기 때문에 다형성을 이용해 중간에 구현체만 바꿔도 그대로 동작한다.
List<String> list = new ArrayList<>();
list = new LinkedList<>();import java.util.*;
public class ListExample {
public static void main(String[] args) {
// 초기에는 ArrayList로 시작
List<String> list = new ArrayList<>();
list.add("사과");
list.add("바나나");
list.add("체리");
System.out.println("초기 리스트: " + list);
// 인덱스로 접근
System.out.println("2번째 과일: " + list.get(1));
// 구현체를 LinkedList로 변경
list = new LinkedList<>(list); // 기존 요소 유지하면서 교체
// 중간에 삽입
list.add(1, "딸기");
System.out.println("중간 삽입 후: " + list);
// 반복 처리
System.out.println("과일 목록:");
list.forEach(System.out::println);
}
}