데이터 구조의 종류와 장단점
아래 표는 보편적으로 사용되는 데이터 구조의 종류와 각 구조가 지닌 장단점을 소개한다.
| 데이터 구조 | 장점 | 단점 |
|---|---|---|
| 배열 | 인덱스 값을 미리 알고 있는 경우, 접근이 빠르며 삽입이 빠르다. | 크기가 고정되고, 삭제 및 검색은 느리다. |
| 정렬된 배열 | 정렬되지 않은 배열에 비해 검색 속도가 더 빠르다. | 크기가 고정되고, 삭제 및 검색은 느리다. |
| 큐 | 먼저 입력된 데이터가 먼저 출력되는 선입 선출 (FIFO) 접근 방식이 제공된다. | 다른 요소에 대한 접근 속도가 느리다. |
| 스택 | 나중에 입력된 데이터가 먼저 출력되는 (LIFO) 접근 방식이 제공된다. | 다른 요소에 대한 접근 속도는 느리다. |
| 리스트 | 데이터 삽입 및 삭제 속도가 빠르다. | 검색 속도는 느리다. |
| 해시 테이블 | 키값을 미리 알고 있는 경우, 해당 데이터에 접근이 빠르며, 새로운 요소 삽입이 빠르다. | 키값을 모르는 경우 접근 및 삭제 속도가 느리며 메모리 효율성이 떨어진다. |
| 힙 | 삽입 및 삭제가 빠르며 최대 혹은 최소 항목에 대한 접근 속도가 빠르다. | 다른 요소에 대한 접근 속도는 느리다. |
| 트라이 | 데이터 접근 속도가 매우 빠르며, 서로 다른 키값에 대한 충돌 가능성이 없고, 삽입과 삭제 또한 빠르다. 문자열 딕셔너리의 정렬, 프리픽스 검색 등에 유용하다. | 특정 상황에서 해시 테이블 보다 속도가 느릴 수 있다. |
| 이진 트리 | (균형 잡힌 트리 구조인 경우) 삽입, 삭제, 검색 속도가 매우 빠르다. | 삭제 알고리즘 작성이 복잡해질 수 있고, 트리 구조가 삽입 순서에 영향을 받으며, 성능이 저하될 수 있다. |
| 레드블랙 트리 | 삽입, 삭제, 검색이 매우 빠르며, 트리는 항상 균형 상태를 유지한다. | 한계 상황에서 데이터 구조를 운영하므로 구현이 까다롭다. |
| R 트리 | 공간적 데이터를 나타낼 때 좋으며, 2차원 이상의 구조를 지원한다. | 역사적으로 성능이 검증되지 못했다. |
| 그래프 | 실제 세계의 상황을 반영한 모델을 구현한다. | 일부 알고리즘은 느리고 복잡하다. |
알고리즘 개요
대부분의 데이터 구조에서 다음과 같은 내용을 필수적으로 파약해야한다.
- 새로운 데이터 아이템 삽입방법
- 데이터 아이템 삭제방법
- 특정 데이터 아이템 검색방법
- 모든 데이터 아이템 순회방법
- 데이터 아이템 정렬방법