[JAVA] 자료구조

선요약

구분	장점	단점
배열	- 빠른 접근 속도 - 메모리 사용 효율적	- 크기 변경 불가 - 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 허용 여부 및 동기화 여부 등이 구현체 마다 다름

 

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)

 

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 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));

 

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 (가장 작은 값부터)


PriorityQueue<Integer> descPq = new PriorityQueue<>(Comparator.reverseOrder());
descPq.offer(5);
descPq.offer(1);
descPq.offer(3);
System.out.println(descPq.poll()); // 5

 

Map

Map은 키(key)와 값(value)의 쌍으로 데이터를 저장하는 Java의 인터페이스

하나의 키에 하나의 값만 대응되며, 키는 중복될 수 없고 값은 중복될 수 있는 자료구조

🔸 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 방식 도입
• 동기화를 보장하는 부분 락 구조

 

주 사용 메서드

1. put(K key, V value)

키와 값을 삽입하거나, 이미 존재하면 값을 덮어씀

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);

---

2. get(Object key)

해당 키에 대한 값을 반환 (없으면 null)

System.out.println(map.get("apple")); // 3
System.out.println(map.get("grape")); // null

 

---

3. containsKey(Object key)

키가 존재하는지 확인

if (map.containsKey("banana")) {
    System.out.println("바나나 있음");
}

---

4. containsValue(Object value)

해당 값이 존재하는지 확인

if (map.containsKey("banana")) {
    System.out.println("바나나 있음");
}

---

5. remove(Object key)

특정 키 제거

map.remove("apple"); // "apple" 삭제

---

6. keySet()

모든 키를 Set으로 반환

for (String key : map.keySet()) {
    System.out.println("key: " + key);
}

---

7. values()

모든 값을 Collection으로 반환

for (Integer value : map.values()) {
    System.out.println("value: " + value);
}

---

8. entrySet()

키-값 쌍을 Map.Entry로 반환 (반복문에 자주 사용)

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " => " + entry.getValue());
}

---

9. getOrDefault(K key, V defaultValue)

키가 없으면 기본값 반환

int count = map.getOrDefault("grape", 0); // 없으면 0 반환

---

10. replace(K key, V newValue)

키가 존재할 때만 값을 교체

map.replace("banana", 10); // banana → 10

---

11. putIfAbsent(K key, V value)

키가 없을 때만 값을 삽입
즉, 이미 키가 있으면 아무것도 하지 않고 기존 값을 유지

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);

// 키 "apple"이 이미 있으므로 변경되지 않음
map.putIfAbsent("apple", 10);

// 키 "banana"는 없으므로 새로 추가됨
map.putIfAbsent("banana", 5);

System.out.println(map); // 출력: {apple=3, banana=5}