5.2 선형 자료 구조
2026-06-09
스터디를 함께 진행했음
연결 리스트
데이터를 감싼 노드를 포인터로 연결한 자료구조.
- 싱글 연결 리스트
- 이중 연결 리스트
- 원형 이중 연결 리스트
| 삽입 | 삭제 | 탐색 |
|---|---|---|
| O(1) | O(1) | O(n) |
배열
같은 타입의 변수들이 같은 크기로 인접한 메모리 공간에 모여 있는 자료구조.
| 삽입 | 삭제 | 탐색 |
|---|---|---|
| O(n) | O(n) | O(1) |
랜덤 접근 : 임의의 인덱스에 해당하는 데이터에 바로 접근할 수 있음 (예: 배열)
순차적 접근 : 데이터에 접근할 때 저장된 순서대로 검색해야 함 (예: 연결 리스트)
스택
LIFO(Last In First Out) 성질을 가진 자료구조. 가장 마지막에 삽입된 것이 가장 먼저 나온다.
재귀적인 함수나 알고리즘에 활용되고, 브라우저 방문 기록에도 스택이 활용됨.
| 삽입 | 삭제 | 탐색 |
|---|---|---|
| O(1) | O(1) | O(n) |
큐
FIFO(First In First out) 성질을 가진 자료구조. 먼저 삽입된 것이 가장 먼저 나온다.
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, BFS, …. 등에 활용됨
| 삽입 | 삭제 | 탐색 |
|---|---|---|
| O(1) | O(1) | O(n) |