> 자료구조(Data Structure)는 데이터를 **어떤 형태로 저장하고, 어떤 방식으로 접근할 것인가**를 다루는 컴퓨터 과학의 핵심 개념입니다. 
프로그램의 성능, 확장성, 유지보수성은 대부분 자료구조 선택에서 큰 영향을 받고있습니다. 
각 자료구조의 특징, 단점, 시간복잡도 등을 최대한 단순하게 적어서 읽는데 많은 시간을 안들이게 구성 했습니다. 
저도 적으면서 가물가물했던 내용들을 다시한번 기억하니 많은 도움이 되었습니다.

# 선형 자료구조

## 1. 배열 (Array)
- **특징**: 고정 크기, 연속된 메모리, O(1) 인덱스 접근
- **단점**: 크기 변경 불가, 삽입/삭제 비효율적
```java
int[] arr = new int[5];
arr[0] = 10; // O(1)
```

## 2. 동적 배열 (ArrayList)
- **특징**: 가변 크기, 내부적으로 배열 복사로 확장
- **시간복잡도**: 조회 O(1), 끝 추가 O(1) amortized, 중간 삽입/삭제 O(n)
```java
ArrayList list = new ArrayList<>();
list.add(10); // O(1) amortized
list.get(0); // O(1)
list.add(0, 5); // O(n) - 요소 이동 필요
list.remove(0); // O(n)
```

## 3. 연결 리스트 (LinkedList)
- **특징**: 노드 기반, 동적 크기, 포인터로 연결
- **시간복잡도**: 조회 O(n), 앞/뒤 삽입/삭제 O(1), 중간 삽입/삭제 O(n)
```java
class Node {
 int data;
 Node next;
 
 Node(int data) {
 this.data = data;
 this.next = null;
 }
}

class LinkedList {
 Node head;
 
 void addFirst(int data) { // O(1)
 Node newNode = new Node(data);
 newNode.next = head;
 head = newNode;
 }
 
 void delete(int data) { // O(n)
 if (head == null) return;
 
 if (head.data == data) {
 head = head.next;
 return;
 }
 
 Node current = head;
 while (current.next != null) {
 if (current.next.data == data) {
 current.next = current.next.next;
 return;
 }
 current = current.next;
 }
 }
}
```

## 4. 스택 (Stack)
- **특징**: LIFO (Last In First Out)
- **용도**: 함수 호출, DFS, 괄호 검증, 되돌리기
```java
Stack stack = new Stack<>();
stack.push(10); // O(1)
stack.push(20);
int top = stack.pop(); // 20, O(1)
int peek = stack.peek(); // 10, O(1)
```

## 5. 큐 (Queue)
- **특징**: FIFO (First In First Out)
- **용도**: BFS, 작업 스케줄링, 버퍼
```java
Queue queue = new LinkedList<>();
queue.offer(10); // O(1)
queue.offer(20);
int front = queue.poll(); // 10, O(1)
int peek = queue.peek(); // 20, O(1)
```

### 6. 덱 (Deque)
- **특징**: 양쪽 끝에서 삽입/삭제 가능
- **용도**: 슬라이딩 윈도우, 양방향 큐
```java
Deque deque = new ArrayDeque<>();
deque.addFirst(10); // O(1)
deque.addLast(20); // O(1)
deque.pollFirst(); // O(1)
deque.pollLast(); // O(1)
```

# 비선형 자료구조

## 1. 해시 테이블 (HashMap)
- **특징**: 키-값 쌍, 해시 함수 사용
- **시간복잡도**: 평균 O(1), 최악 O(n) - 해시 충돌 시
- **용도**: 빠른 검색, 중복 제거, 캐싱
```java
HashMap map = new HashMap<>();
map.put("apple", 100); // O(1) 평균
map.get("apple"); // O(1) 평균
map.containsKey("apple"); // O(1) 평균
map.remove("apple"); // O(1) 평균

// 충돌 처리: Chaining(LinkedList) 또는 Open Addressing
```

## 2. 해시 셋 (HashSet)
- **특징**: 중복 없는 집합, HashMap 기반
- **시간복잡도**: 추가/검색/삭제 O(1) 평균
```java
HashSet set = new HashSet<>();
set.add(10); // O(1)
set.contains(10); // O(1)
set.remove(10); // O(1)
```

## 3. 트리 (Tree)

### 3.1. 이진 트리
```java
class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 
 TreeNode(int val) {
 this.val = val;
 }
}
```

### 3.2. 이진 탐색 트리 (BST)
- **특징**: 왼쪽 < 부모 < 오른쪽
- **시간복잡도**: 평균 O(log n), 최악 O(n) - 편향 트리
```java
class BST {
 TreeNode root;
 
 TreeNode insert(TreeNode node, int val) { // O(log n) 평균
 if (node == null) return new TreeNode(val);
 
 if (val < node.val)
 node.left = insert(node.left, val);
 else if (val > node.val)
 node.right = insert(node.right, val);
 
 return node;
 }
 
 boolean search(TreeNode node, int val) { // O(log n) 평균
 if (node == null) return false;
 if (node.val == val) return true;
 
 return val < node.val 
 ? search(node.left, val) 
 : search(node.right, val);
 }
}
```

### 3.3. TreeMap/TreeSet (Red-Black Tree)
- **특징**: 자가 균형 이진 탐색 트리
- **시간복잡도**: 모든 연산 O(log n) 보장
- **용도**: 정렬된 상태 유지 필요 시
```java
TreeMap treeMap = new TreeMap<>();
treeMap.put(3, "three"); // O(log n)
treeMap.put(1, "one");
treeMap.put(2, "two");
// 자동 정렬: {1=one, 2=two, 3=three}

TreeSet treeSet = new TreeSet<>();
treeSet.add(5); // O(log n)
treeSet.first(); // 최소값 O(log n)
treeSet.last(); // 최대값 O(log n)
```

## 4. 힙 (Heap)
- **특징**: 완전 이진 트리, 최대/최소값 빠른 접근
- **시간복잡도**: 삽입/삭제 O(log n), 최대/최소 조회 O(1)
- **용도**: 우선순위 큐, 힙 정렬, Top K 문제
```java
// 최소 힙
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(5); // O(log n)
minHeap.offer(3);
minHeap.offer(7);
minHeap.poll(); // 3, O(log n)

// 최대 힙
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(3);
maxHeap.poll(); // 5
```

## 5. 그래프 (Graph)

### 5.1. 인접 리스트
```java
// 효율적: 간선이 적을 때 (희소 그래프)
HashMap> graph = new HashMap<>();

void addEdge(int u, int v) {
 graph.putIfAbsent(u, new ArrayList<>());
 graph.get(u).add(v);
 // 무방향 그래프면 양쪽 추가
 graph.putIfAbsent(v, new ArrayList<>());
 graph.get(v).add(u);
}
```

### 5.2. 인접 행렬
```java
// 간선이 많을 때 (밀집 그래프), O(1) 간선 존재 확인
int[][] graph = new int[n][n];
graph[u][v] = 1; // 간선 존재
```

# 시간복잡도 비교

| 자료구조 | 접근 | 검색 | 삽입 | 삭제 |
|---------|------|------|------|------|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1)* | O(1)* |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| HashMap | - | O(1) | O(1) | O(1) |
| TreeMap | - | O(log n) | O(log n) | O(log n) |
| Heap | O(n) | O(n) | O(log n) | O(log n) |
| BST | O(log n) | O(log n) | O(log n) | O(log n) |

*위치를 알고 있을 때

# 선택 기준

- **빠른 인덱스 접근**: 배열, ArrayList
- **빈번한 삽입/삭제**: LinkedList
- **LIFO**: Stack
- **FIFO**: Queue
- **빠른 검색**: HashMap, HashSet
- **정렬 + 검색**: TreeMap, TreeSet
- **최대/최소 우선**: PriorityQueue (Heap)
- **관계 표현**: 그래프

# 마무리
실전에선 대부분 ArrayList, HashMap, PriorityQueue로 해결이 가능한 것들이 많습니다. 
혹시 작성한 내용중에 오타나 내용에 이상이 있으면 댓글로 말씀해주시면 감사하겠습니다 .

자료구조

이 주제의 기록

개발자가 반드시 알아야 할 자료구조 기본 정리