[자료구조] 자료구조 기본 이해하기

ArrayList

기본 개념

• 동적 배열(Dynamic Array) 기반의 리스트
• 내부적으로 Object[] elementData 배열을 사용함
• 배열이 꽉 차면 1.5배로 자동 확장
• 인덱스 기반 접근이 빠르지만, 중간 삽입/삭제는 느림
• 첫 add()시 10크기 배열 생성됨.

List<String> list = new ArrayList<>();
list.add("A"); // elementData[0] = "A"
list.add("B"); // elementData[1] = "B"
list.get(0);   // O(1)로 접근
list.remove(1); // 뒤의 원소를 전부 한 칸씩 앞으로 이동 → O(n)

• 데이터가 순차적으로 추가/조회될 때 유리
• Stack, Queue를 직접 구현할 때 내부 자료구조로 활용 가능

LinkedList

public class Node {
 Object item;
 Node next;
}

노드 클래스는 내부에 저장할 데이터인 item 과, 다음으로 연결할 노드의 참조인 next 를 가진다.

기본 개념

• 노드(Node) 들이 포인터로 서로 연결된 구조
• 각 노드는 데이터(data) + 다음 노드(next) + 이전 노드(prev) 정보를 가짐
• 양방향 연결 리스트 (Doubly Linked List) 형태로 구현되어 있음

⇒ 중간 삽입·삭제는 빠르지만, 인덱스로 접근할 때는 느림

LinkedList<String> list = new LinkedList<>();

list.add("A");          // A
list.add("B");          // A <-> B
list.addFirst("START"); // START <-> A <-> B
list.addLast("END");    // START <-> A <-> B <-> END

list.remove("A");       // START <-> B <-> END
list.get(1);            // 인덱스 접근은 O(n)

 

→ 김영한 자바 중급.

사용 예시

• 중간 삽입/삭제가 잦은 경우
• 큐(Queue), 덱(Deque) 구조 구현 시 자주 사용

Deque<String> deque = new LinkedList<>();

// 뒤쪽 추가
deque.addLast("A");
deque.addLast("B");

// 앞쪽 추가
deque.addFirst("C"); // [C, A, B]

// 양쪽 제거
System.out.println(deque.removeFirst()); // C
System.out.println(deque.removeLast());  // B
System.out.println(deque); // [A]

Stack (LIFO 구조)

기본 개념

• LIFO (Last In, First Out) 구조
• → 마지막에 들어온 데이터가 가장 먼저 나가는 구조
• "접시를 쌓는 것" 과 같은 개념
• → 가장 위(top)에 있는 접시를 먼저 꺼냄

연산 설명 시간복잡도

push(E e)	맨 위에 데이터 추가	O(1)
pop()	맨 위의 데이터 제거 후 반환	O(1)
peek()	맨 위의 데이터 확인 (제거 X)	O(1)
empty()	스택이 비어있는지 확인	O(1)

import java.util.Stack;

public class Example {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println(stack.peek()); // C
        System.out.println(stack.pop());  // C
        System.out.println(stack.pop());  // B
        System.out.println(stack);        // [A]
    }
}

내부 구현

• Stack 클래스는 Vector를 상속해서 만들어졌음
• 즉, 내부적으로 배열 기반 구조.
• 다만 Vector는 모든 메서드가 synchronized(동기화) 되어 있어서
• → 단일 스레드 환경에서는 불필요하게 느림.

public class Stack<E> extends Vector<E> {
    public E push(E item) { ... }
    public synchronized E pop() { ... }
}

연산 설명 반환값 시간복잡도

offer(e)	큐의 뒤에 요소 추가	true / false	O(1)
poll()	큐의 앞에서 요소 제거	제거된 값 or null	O(1)
peek()	큐의 앞의 요소 조회 (제거 X)	값 or null	O(1)

import java.util.Queue;
import java.util.LinkedList;

public class Example {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println(queue.peek()); // A
        System.out.println(queue.poll()); // A
        System.out.println(queue.poll()); // B
        System.out.println(queue);        // [C]
    }
}

Queue (큐)

기본 개념

• FIFO (First In, First Out) 구조
• → 먼저 들어온 데이터가 먼저 나가는 구조(선입선출)

ArrayDeque (배열 기반 양방향 큐)

기본 개념

• Deque(양방향 큐) 인터페이스의 가장 대표적인 구현체
• 내부적으로 배열(circular array, 원형 배열) 을 사용
• 앞·뒤 양쪽에서 삽입과 삭제가 모두 O(1)
• Stack 과 Queue 를 모두 대체 가능

큐 사용시

Deque<String> queue = new ArrayDeque<>();

queue.offer("A"); // addLast("A")
queue.offer("B"); // addLast("B")
queue.offer("C"); // addLast("C")

System.out.println(queue.peek()); // A (맨 앞)
System.out.println(queue.poll()); // A 제거
System.out.println(queue.poll()); // B 제거
System.out.println(queue);        // [C]

스택 사용시

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(stack.pop()); // C
System.out.println(stack.pop()); // B
System.out.println(stack);       // [A]

[ A ][ B ][ C ][ - ][ - ][ - ][ - ][ - ]
front = 0
rear  = 3

poll() → A 삭제
front = 1

offer(D) →
[ - ][ B ][ C ][ D ][ - ][ - ][ - ][ - ]
front = 1
rear  = 4

항목 설명

빠름	배열 기반이라 인덱스 계산만으로 접근
메모리 효율	노드 객체 없음 (LinkedList보다 가벼움)
유연성	Queue와 Stack 둘 다 가능
null 금지	null은 내부적으로 빈 칸 표시용
자동 확장	꽉 차면 2배로 resize

PriorityQueue (우선순위 큐)

내부 구조

• 내부적으로 힙(Heap) 자료구조로 구현됨 (기본은 최소 힙)
• 삽입/삭제 시 자동으로 힙 성질 유지

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 5

Set (집합) — 개념

기본 개념

• 중복을 허용하지 않는 자료구조
• 순서(인덱스) 개념이 없음
• 내부적으로 Hash 기반, Tree 기반, Linked 기반으로 구현됨

기본구조

public interface Set<E> extends Collection<E> {
    boolean add(E e);
    boolean remove(Object o);
    boolean contains(Object o);
    int size();
    Iterator<E> iterator();
}
순서가 없고, 인덱스로 접근하지 않음 (get(i) 불가)

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("A");
System.out.println(set); // [A, B]
중복되는 A 무시

HashSet

기본 개념

• 가장 많이 사용하는 Set
• 내부적으로 HashMap을 사용
• 중복 판단은 hashCode()와 equals() 기반

Set<String> set = new HashSet<>();
set.add("A");
set.add("C");
set.add("B");
set.add("A");

System.out.println(set); // [A, B, C] (순서는 랜덤)

내부 동작

map.put("A", PRESENT);
map.put("B", PRESENT);
map.put("A", PRESENT); // 이미 존재하므로 무시

LinkedHashSet

기본 개념

• HashSet + 연결 리스트
• 삽입한 순서 그대로 유지
• 내부적으로 LinkedHashMap 사용

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("C");
set.add("B");
System.out.println(set); // [A, C, B]
순서유지는 되나 중복은 안됨.

LinkedHashMap의 Entry 구조

[prev] ←→ [key, value, next] ←→ [next]
해시 테이블 + 이중 연결 리스트
탐색은 해시로, 순회는 연결 리스트 순서대로

TreeSet

핵심 개념

• 데이터가 자동으로 정렬된 상태로 저장되는 Set
• 내부적으로 TreeMap (Red-Black Tree) 사용

Set<Integer> set = new TreeSet<>();
set.add(30);
set.add(10);
set.add(20);
System.out.println(set); // [10, 20, 30]

내부 동작

• 삽입 시 이진 트리 형태로 저장
• 각 노드는 "왼쪽 < 부모 < 오른쪽" 형태 유지
• Red-Black Tree이므로 삽입/삭제 시 자동 균형 조정

        20
       /  \\
     10    30
항상 정렬된 순서로 탐색 가능

한 눈에 정리 표(feat.GPT)

항목 HashSet LinkedHashSet TreeSet

내부 구조	HashMap	LinkedHashMap	TreeMap (Red-Black Tree)
순서	없음	삽입 순서 유지	자동 정렬
중복	❌	❌	❌
null 허용	✅ 1개	✅ 1개	❌
시간복잡도	O(1)	O(1)	O(log n)
메모리 사용	적음	중간	많음
Comparator	X	X	✅ 지원
대표 용도	빠른 중복 제거	순서 + 중복 제거	정렬 + 중복 제거

Map

기본 개념

• Key–Value 쌍(Key, Value pair) 으로 데이터를 저장하는 자료구조
• Key는 중복 불가, Value는 중복 허용

메서드 설명

put(K key, V value)	데이터 추가
get(Object key)	key로 value 조회
remove(Object key)	key 삭제
containsKey(Object key)	key 존재 여부 확인
keySet()	key만 모아 Set으로 반환
values()	value만 Collection으로 반환
entrySet()	key-value 쌍을 Set으로 반환

HashMap

HashTable 구조 기반, key 중복 불가, 순서 없음.

Map<String, Integer> map = new HashMap<>();
map.put("A", 100);
map.put("B", 200);
map.put("C", 300);
map.put("A", 999); // 덮어쓰기
System.out.println(map); // {A=999, B=200, C=300}

내부 동작 (해시 기반)

1. key의 hashCode() 호출
2. 해시값을 버킷(bucket) 인덱스로 변환
3. 해당 버킷에 노드(Node) 저장
4. 충돌 시 → 체이닝(Linked List or Tree) 으로 연결

LinkedHashMap

HashMap + 연결 리스트 구조

⇒ 즉, 삽입 순서 유지 + O(1) 속도

Map<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("C", 3);
map.put("B", 2);
System.out.println(map); // {A=1, C=3, B=2}

HashMap은 순서 랜덤, LinkedHashMap은 삽입 순서 그대로 출력.

내부 구조

• Entry(Node)에 before, after 포인터 존재
• 순회 시 연결 리스트 순서로 이동
• HashMap보다 약간 느리지만 순서 보장됨

TreeMap

핵심 개념

• Key가 자동 정렬되는 Map
• 내부적으로 Red-Black Tree 사용
• Key의 자연 순서(Comparable) 혹은 Comparator 기준 정렬

Map<Integer, String> map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");
System.out.println(map); // {1=A, 2=B, 3=C}

Map<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
System.out.println(map); // {C=3, B=2, A=1}

EnumMap

핵심 개념

• Enum 타입 전용 Map, 내부적으로 배열 기반
• 가장 빠른 Map 중 하나
• HashMap보다 훨씬 메모리 효율적

enum Day { MON, TUE, WED }

Map<Day, String> map = new EnumMap<>(Day.class);
map.put(Day.MON, "월요일");
map.put(Day.TUE, "화요일");
System.out.println(map); // {MON=월요일, TUE=화요일}

추가

Map.Entry

• Map은 Key와 Value의 쌍으로 구성 → 그 한 쌍을 Entry 라고 통칭

entrySet() 메서드

개념

• Map 안에 들어있는 모든 Entry(Key-Value 쌍) 를 Set 형태로 반환

Set<Map.Entry<K, V>> entrySet()
즉, HashMap의 내부 구조를 한 번에 꺼내오는 역할.

예시 코드

Map<String, Integer> map = new HashMap<>();
map.put("A", 10);
map.put("B", 20);
map.put("C", 30);

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

A → 10
B → 20
C → 30

entrySet() 내부 구조 이해

HashMap의 각 버킷에는 Node<K,V> 객체가 저장

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

entrySet()은 이 Node 객체들을 Set 형태로 감싼 것!