선요약
| 구분 | 장점 | 단점 |
|---|---|---|
| 배열 | - 빠른 접근 속도 - 메모리 사용 효율적 | - 크기 변경 불가 - API 기능 부재 |
| 컬렉션 | - 유연한 크기 조절 - 풍부한 API - 다양한 자료구조 구현체 존재 | - 오버헤드 존재 - 제네릭 사용 필요 - 타입 안전성 문제 발생 가능 |
| 상황 | 추천 자료구조 |
|---|---|
| 요소 수가 고정되어 있고 변경되지 않음 | 배열 |
| 삽입/삭제가 빈번함 | LinkedList, HashMap |
| 검색이 빈번하고 인덱스 기반 접근 필요 | ArrayList |
| 중복을 허용하지 않는 집합이 필요 | HashSet, TreeSet |
| 키-값 구조의 저장이 필요 | HashMap, TreeMap |
배열
같은 타입의 데이터를 연속적으로 저장할 수 있는 고정 크기 자료 구조
- 인덱스를 통한 빠른 접근이 가능
- 기본형(int[])과 참조형(String[]) 모두 지원
- 다차원 배열 지원
- 내부적으로 Heap 영역에 연속된 공간을 할당(CPU 캐시에 친화적)
int [] arr = new int [5];
int [] arr2 = {1,2,3,4,5};
System.out.println(Arrays.toString(arr2));
// 이거 하면 파이썬에서 한번에 출력하듯이 나옴
// 다차원 배열용은 Arrays.deeptoString(arr);
int [][] arr3 = new int[3][]; // 놀랍게도 이거 됨
arr3[0] = new int[1];
arr3[1] = new int[2];
arr3[2] = new int[3];
for(int [] t : arr3){
System.out.println(t.length);
}컬렉션
데이터를 효율적으로 저장, 탐색, 정렬, 삭제하기 위한 동적 자료구조들(java.util에 있다.)
- 요소의 추가/삭제가 동적
- 반복자(Iterator) 기반 순회 가능
- null 허용 여부 및 동기화 여부 등이 구현체 마다 다름
1. List
중복된 값이 가능하고, 인덱스로 참조 관리하는 자료구조이다.
add(), get(), set(), remove(), indexOf(), lastIndexOf(), contains() // 공통메서드🔸 ArrayList
- 내부적으로 배열이 사용되지만, 자동 리사이징을 수행
(add()시 용량이 초과되면 내부적으로 grow()를 사용해 크기를 1.5배 확장한다) - 동시에 여러 스레드가 접근할 수 있다.
🔸 LinkedList
- 각 요소에 포인터를 포함해 비연속적으로 저장된다.
- 그래서 중간 인덱스를 삭제해도 해당 인덱스 번호는 비게 된다.
(ArrayList와 비교해 인덱스를 당기는 연산이 사라져 비교적 빠름)
| 연산 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 접근 | O(1) | O(n) |
| 삽입/삭제 (중간) | O(n) (밀어내기 발생) | O(1) (노드 연결만) |
| 메모리 사용 | 적음 (데이터만 저장) | 많음 (데이터 + 링크) |
| 캐시 적중률 | 높음 (연속된 메모리) | 낮음 (불연속 메모리) |
🔸 Vector
- ArrayList와 동일하나
모든 메서드에 synchronized처리(thread-safe)
2. Set
중복을 허용하지 않고 저장 순서를 미보장한다.(null도 하나만)
🔸 HashSet
- 내부적으로 HashMap<K, Object> 구조로 관리
hashCode()와equals()를 모두 Override 해야 중복 판단이 정확
(equals(): 기본적으로 주소값을 비교(==), Override로 내용을 비교하게 설정)
(hashCode(): 객체를 Hash기반에서 사용할 때, 내부 버킷을 결정할 때 사용, 같은 객체는 항상 같은 hashCode()를 반환해야 함.)- Lombok 사용 시
@EqualsAndHashCode로 자동 생성 가능
class Person {
String name;
public Person(String name) { this.name = name; }
}
Set<Person> set = new HashSet<>();
set.add(new Person("Alice"));
set.add(new Person("Alice")); // 다른 객체로 인식됨
System.out.println(set.size()); // 결과: 2
// 둘 다 주소가 다르고 hashCode도 다르고 equals도 false: 중복 아닌걸로 처리class Person {
String name;
public Person(String name) { this.name = name; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person p = (Person) o;
return this.name.equals(p.name);
}
@Override
public int hashCode() {
return name.hashCode(); // String의 hashCode 사용
}
}
Set<Person> set = new HashSet<>();
set.add(new Person("Alice"));
set.add(new Person("Alice"));
System.out.println(set.size()); // 결과: 1
🔸 TreeSet
- Red-Black Tree 기반 이진탐색트리(BST)
Comparable과Comparator로 정렬 기준 지정 가능
TreeSet<Integer> ts = new TreeSet<>();- 정수형 TreeSet을 생성한다. 값이 자동으로 오름차순 정렬된다.
ts.headSet(10); // 10보다 작은 값- 10 미만의 값들만 포함한 뷰(view)를 반환한다.
- 즉, ts에서 10보다 작은 값들만을 가진 부분 집합이다. (10은 포함되지 않음)
ts.tailSet(10); // 10보다 큰 값- 10 이상의 값을 포함하는 뷰(view)이다.
- 즉, ts에서 10부터 시작하여 그 이상의 값을 포함하는 부분 집합이다. (10은 포함됨)
ts.subSet(5, 15); // 5~14 사이 값- 5 이상, 15 미만의 값들로 이루어진 부분 집합이다.
- 즉, 5 <= 값 < 15 조건을 만족하는 원소들만 반환한다.
기본 정렬 (Comparable)
TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(3);
set.add(10);
System.out.println(set); // [3, 5, 10] - 오름차순 자동 정렬사용자 정의 정렬 (Comparator 전달)
TreeSet<String> names = new TreeSet<>(Comparator.reverseOrder());
names.add("Alice");
names.add("Bob");
names.add("Charlie");
System.out.println(names); // [Charlie, Bob, Alice]사용자 객체 정렬 (Comparable 구현)
class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) { this.name = name; this.age = age; }
@Override
public int compareTo(Person o) {
return Integer.compare(this.age, o.age);
}
}
TreeSet<Person> people = new TreeSet<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 20));
3. Stack, Queue, Deque, PriorityQueue
🔸 Stack (LIFO, 후입선출)
- java.util.Stack은 오래된 구조이며, 동기화 비용이 있어 요즘은 ArrayDeque 권장
- 메서드:
push(),pop(),peek()
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop()); // "B"🔸 Queue (FIFO, 선입선출)
- 일반적으로 LinkedList, ArrayDeque, PriorityQueue 등을 사용
- 메서드:
offer(e)– 요소 추가poll()– 꺼내고 제거 (비어있으면 null)peek()– 꺼내지 않고 조회
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
System.out.println(queue.poll()); // "A"🔸 Deque (Double Ended Queue, 양방향 큐)
- Stack + Queue 혼합형: 양쪽에서 삽입과 삭제 가능
- 장점: 빈번한 삽입/삭제에 적합 (LinkedList보다 빠름), 큐/스택 전부 구현 가능
- 메서드:
addFirst(e),addLast(e)removeFirst(),removeLast()peekFirst(),peekLast()
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A");
deque.addLast("B");
System.out.println(deque.removeLast()); // "B"🔸 PriorityQueue (우선순위 큐)
- 요소를 삽입하면 자동으로 우선순위에 따라 정렬되어 꺼낼 수 있는 큐
- 내부적으로 Min-Heap (최소 힙) 구조 사용
- 기본 정렬 기준은 Comparable.compareTo() 오름차순
- 커스텀 정렬은 Comparator 전달로 가능
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1 (가장 작은 값부터)
✅ 커스텀 정렬 (내림차순)
java
복사
편집
PriorityQueue<Integer> descPq = new PriorityQueue<>(Comparator.reverseOrder());
descPq.offer(5);
descPq.offer(1);
descPq.offer(3);
System.out.println(descPq.poll()); // 54. Map
Key - Value 매핑 구조로 이루어져 있으면 key는 유일한 값이다.
🔸 HashMap
hashCode()→ 버킷 인덱스 결정- 충돌 시
LinkedList
(Java 8 이후 TreeNode(Red-Black Tree) 로 전환 (성능 최적화)) - key 탐색, 삽입, 삭제: 평균 O(1), 최악 O(n) → TreeNode로 완화
🔸 HashTable
- 모든 메서드가 synchronized → 성능 이슈
- Legacy 클래스 → ConcurrentHashMap 권장
🔸 LinkedHashMap
- 들어온 순서를 가지고 있다.
new LinkedHashMap<>(capacity, loadFactor, accessOrder);→ accessOrder = true 설정 시, 접근 순서 기준으로 순서 갱신
🔸 TreeMap
- NavigableMap 인터페이스 구현
- 내부는 Red-Black Tree
- 정렬 기준: natural order or Comparator
🔸 ConcurrentHashMap
- 세그먼트 기반 락에서 Java 8 이후에는 CAS("내가 예상한 값일 때만 바꾼다"는 조건부 갱신 연산) + Synchronized 방식 도입
- 동기화를 보장하는 부분 락 구조
컴퓨터를 좋아합니다