Non-Primitive
Linear Data Structure vs. Non-Linear Data Structure
데이터 구조는 크게 Linear Data Structure와 Non-Linear Data Structure로 나눌 수 있다.
| 측면 | Linear Data Structure | Non-Linear Data Structure |
|---|---|---|
| 정의 | 데이터 요소가 순차적 또는 선형적으로 배열된 구조 | 데이터 요소가 순차적이거나 선형적으로 배열되지 않은 구조 |
| 구조 | 단일 레벨 구조 | 다중 레벨 구조 |
| 데이터 관계 | 요소 간 1:1 관계 | 요소 간 1:N 또는 N:N 관계 |
| 순회 | 단일 실행으로 모든 요소 순회 가능 | 단일 실행으로 모든 요소 순회 불가능 |
| 구현 복잡성 | 구현이 상대적으로 간단 | 구현이 상대적으로 복잡 |
| 메모리 사용 | 메모리 사용이 덜 효율적 | 메모리 사용이 더 효율적 |
| 시간 복잡도 | 입력 크기에 따라 증가 | 특정 작업에서 더 효율적 |
| 데이터 접근 | 순차적 접근 | 계층적 또는 네트워크 기반 접근 |
| 삽입/삭제 | 상대적으로 간단 | 더 복잡하지만 유연함 |
| 응용 분야 | 간단한 데이터 저장 및 처리 | 복잡한 관계 표현, AI, 이미지 처리 등 |
| 예시 | 배열, 연결 리스트, 스택, 큐 | 트리, 그래프, 해시 테이블, 힙 |
공통점:
- 둘 다 데이터를 구조화하고 관리하는 방법을 제공한다.
- 특정 작업에 대해 효율적인 알고리즘을 지원한다.
- 데이터의 삽입, 삭제, 검색 연산을 수행할 수 있다.
주요 차이점:
- 데이터 배열 방식 (순차적 vs 계층적/네트워크)
- 구현 복잡도 (간단 vs 복잡)
- 메모리 효율성 (덜 효율적 vs 더 효율적)
- 데이터 관계 표현 (1:1 vs 1:N 또는 N:N)
- 응용 분야 (간단한 데이터 처리 vs 복잡한 관계 표현)
선형 데이터 구조 (Linear Data Structure) 유형
| 구조 | 정의 | 특징 | 장점 | 단점 | 주요 연산 |
|---|---|---|---|---|---|
| Array | 연속된 메모리 위치에 동일한 유형의 요소를 저장하는 구조 | - 고정 크기 - 인덱스로 접근 | - 빠른 접근 시간 O(1) - 메모리 효율적 | - 크기 변경 어려움 - 삽입/삭제 비효율적 | 접근, 검색, 삽입, 삭제 |
| Linked List | 노드가 데이터와 다음 노드 참조를 포함하는 연결 구조 | - 동적 크기 - 비연속 메모리 | - 삽입/삭제 효율적 - 유연한 크기 | - 임의 접근 어려움 - 추가 메모리 필요 | 삽입, 삭제, 순회 |
| Stack | LIFO(Last-In-First-Out) 원칙을 따르는 구조 | - 한쪽 끝에서만 연산 - 후입선출 | - 간단한 구현 - 역추적에 유용 | - 제한된 데이터 접근 | push, pop, peek |
| Queue | FIFO(First-In-First-Out) 원칙을 따르는 구조 | - 양쪽 끝에서 연산 - 선입선출 | - 순서 보존 - 버퍼링에 유용 | - 중간 데이터 접근 어려움 | enqueue, dequeue |
| Deque | 양쪽 끝에서 삽입과 삭제가 가능한 구조 | - 양방향 연산 - 스택과 큐 기능 결합 | - 유연한 데이터 처리 - 다양한 알고리즘 지원 | - 구현 복잡성 | pushFront, pushBack, popFront, popBack |
비선형 데이터 구조 (Non-Linear Data Structure) 유형
| 구조 | 정의 | 특징 | 장점 | 단점 | 주요 연산 |
|---|---|---|---|---|---|
| Graph | 노드(정점)와 엣지(간선)로 구성된 비선형 데이터 구조 | - 계층적 또는 네트워크 관계 표현 - 방향성 있는/없는 그래프로 구분 | - 복잡한 관계 모델링 - 효율적인 경로 탐색 | - 구현 복잡성 - 메모리 사용량 큼 | 삽입, 삭제, 탐색, 순회 |
| Hash-based Structure | 키를 값에 매핑하는 데이터 구조 | - 해시 함수 사용 - 충돌 해결 메커니즘 필요 | - 빠른 검색, 삽입, 삭제 (평균 O(1)) - 효율적인 데이터 관리 | - 최악의 경우 성능 저하 - 순서 정보 손실 | 삽입, 검색, 삭제 |
| Tree | 계층적 구조를 가진 노드들의 집합 | - 루트 노드와 자식 노드로 구성 - 사이클 없음 | - 계층적 데이터 표현 - 효율적인 검색 | - 불균형 시 성능 저하 - 구현 복잡성 | 삽입, 삭제, 검색, 순회 |
| Heap | 완전 이진 트리 기반의 특수한 트리 구조 | - 최대 힙 또는 최소 힙 - 부모-자식 간 대소 관계 유지 | - 최대/최소값 빠른 접근 - 우선순위 큐 구현에 효과적 | - 임의 노드 접근 어려움 - 중간값 찾기 비효율적 | 삽입, 삭제, 힙 정렬 |
Hash-based data structure가 Non-linear data structure로 분류되는 근거
- 고유한 접근 방식: Hash-based 구조는 해시 함수를 사용하여 데이터를 저장하고 검색한다. 이는 다른 non-linear 구조와는 다른 독특한 접근 방식이다.
- 성능 특성: Hash-based 구조는 평균적으로 O(1)의 시간 복잡도로 삽입, 검색, 삭제 연산을 수행할 수 있어, 다른 non-linear 구조와 구별된다.
- 다양한 응용: Hash-based 구조는 associative arrays, 데이터베이스 인덱싱, 캐시, 집합 등 다양한 응용 분야에서 사용된다.
- 충돌 해결 메커니즘: Hash-based 구조는 충돌 해결을 위한 고유한 메커니즘(예: separate chaining, linear probing)을 가지고 있어, 다른 non-linear 구조와 구별된다.
- 공간-시간 트레이드오프: Hash-based 구조는 메모리 사용과 연산 속도 사이의 특별한 균형을 제공한다.
- 확률적 성능: Hash-based 구조의 성능은 해시 함수의 품질과 충돌 해결 방법에 따라 확률적으로 결정되며, 이는 다른 non-linear 구조와 다른 특성이다.