1. 배열(Array)
✔ 개념
- 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조.
- 인덱스를 사용하여 빠르게 접근할 수 있음.
✔ 장점
- O(1) 시간 복잡도로 인덱스를 이용한 데이터 접근 가능.
- 메모리에서 연속된 공간을 사용하여 캐시 효율이 좋음.
✔ 단점
- 크기가 고정되어 있어 확장이나 삽입/삭제가 비효율적(평균 O(n)).
- 중간에 데이터를 삽입하거나 삭제할 때 연속적인 데이터 이동이 필요함.
✔ 활용
- 고정된 크기의 데이터 저장 (ex: 배열 기반 리스트, 2D 행렬, 이미지 데이터 등).
- 빠른 데이터 접근이 필요한 경우.
2. 연결 리스트(Linked List)
✔ 개념
- 노드(Node)들이 포인터로 연결된 구조로, 각 노드는 데이터와 다음 노드의 주소를 가짐.
✔ 장점
- 동적 크기 조절이 가능하여 메모리 활용이 유연함.
- 중간 삽입/삭제가 배열보다 효율적 (O(1) 또는 O(n)).
✔ 단점
- 인덱스 접근이 불가능하여 특정 요소를 찾으려면 O(n) 시간이 걸림.
- 추가적인 포인터 저장 공간이 필요하여 메모리 사용량이 증가함.
✔ 활용
- 메모리를 효율적으로 사용해야 하는 경우.
- 자주 삽입/삭제가 발생하는 경우 (ex: LRU 캐시, 해시 테이블의 체이닝).
3. 스택(Stack)
✔ 개념
- 후입선출(LIFO, Last In First Out) 방식의 자료구조.
- push(삽입), pop(삭제), top(조회) 연산을 가짐.
✔ 장점
- O(1) 시간 복잡도로 빠른 삽입/삭제 가능.
✔ 단점
- 중간 요소 접근이 어렵고 특정 요소를 찾으려면 O(n) 시간이 걸림.
✔ 활용
- 재귀 호출 처리 (콜 스택)
- 괄호 검사 및 수식 계산
- 뒤로가기 기능 (Undo, Redo)
4. 큐(Queue) & 덱(Deque)
✔ 개념
- 큐(Queue): 선입선출(FIFO, First In First Out) 방식의 자료구조.
- 덱(Deque): 양쪽에서 삽입/삭제가 가능한 확장된 큐.
✔ 장점
- O(1) 시간 복잡도로 삽입/삭제 가능 (연결 리스트 또는 원형 배열 사용 시).
- 멀티 태스킹, 작업 스케줄링 등에서 유용함.
✔ 활용
- 프로세스 스케줄링 (ex: 운영체제의 작업 큐).
- 너비 우선 탐색(BFS)
- 캐시 구현 (LRU 캐시, Deque 활용)
5. 해시 테이블(Hash Table)
✔ 개념
- 키(key)를 해시 함수(hash function)를 이용해 해시 값으로 변환한 후, 해당 위치에 값을 저장하는 자료구조.
✔ 장점
- 평균 O(1) 시간 복잡도로 빠른 삽입, 삭제, 검색 가능.
✔ 단점
- 해시 충돌(Collision) 발생 가능 → 체이닝(Chaining) 또는 개방 주소법(Open Addressing)으로 해결 필요.
- 메모리 사용량이 많을 수 있음.
✔ 활용
- 딕셔너리(Dictionary), 맵(Map) 자료구조
- 중복 검사, 데이터 카운팅 (ex: 빈도수 계산)
- 캐싱 (ex: 웹 브라우저 캐시, DNS 캐시)
6. 트리(Tree) & 그래프(Graph)
✔ 트리(Tree)
- 계층적 구조를 가지며, 각 노드는 부모-자식 관계를 가짐.
- 이진 탐색 트리(BST), AVL 트리, 레드-블랙 트리 등이 있음.
✔ 활용
- 데이터베이스의 인덱스 (B-트리, B+트리)
- 탐색 최적화 (ex: BST, Trie)
✔ 그래프(Graph)
- 노드(Node)와 간선(Edge)로 구성된 자료구조.
- BFS, DFS 탐색 알고리즘이 사용됨.
✔ 활용
- 소셜 네트워크, 길 찾기 알고리즘 (Dijkstra, A* 알고리즘)
- 최단 경로 문제
7. 힙(Heap)
✔ 개념
- 우선순위 큐를 구현하는 데 사용되는 완전 이진 트리 기반 자료구조.
- 최대 힙(Max Heap), 최소 힙(Min Heap) 존재.
✔ 장점
- O(log n) 시간 복잡도로 효율적인 삽입 및 삭제 가능.
✔ 활용
- 우선순위 큐 (ex: 작업 스케줄링, 네트워크 패킷 처리)
- 최대값/최소값 탐색
- 다익스트라 최단 경로 알고리즘
마무리
- 빠른 접근이 필요하면 → 배열, 해시 테이블
- 빈번한 삽입/삭제가 필요하면 → 연결 리스트, 큐, 스택
- 탐색 최적화가 필요하면 → 트리, 그래프, 힙
- 우선순위 처리가 필요하면 → 힙
