선형 자료구조 : 배열, 스택, 큐, 맵, 연결 리스트
비선형 자료구조 : 그래프, 트리 (힙, 이진트리)
| 포인트 | 선형구조 | 비선형구조 |
|---|---|---|
| 데이터 저장 | 순차적(Linear), 순회 가능하도록 저장 | 계층적(Level)으로 저장 |
| 수준(Lv) | 단일 Level | 복수 Level |
| 구현 복잡도 | 쉬움 | 어려움 |
| 순회 | 단일 동작으로 가능 | 복수 동작 필요 |
| 메모리 활용 | 공간 효율성 낮음 | 공간 효율성 매우 높음 |
| 시간 복잡도 | 저장공간과 비례하여 증가 | 저장공간이 늘어나면 비례하는 수준보다 적게 증가 |
선형 자료구조
배열 (Array)
번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조
일반적으로 같은 종류의 데이터들이 순차적으로 저장
인덱스(Index) : 기본주소로부터 값이 저장되어 있는 상대적인 위치
기본주소 : 배열의 첫번째 요소의 메모리 주소- 검색시간 : O(1)
문자열 (String)
일련의 연속된 문자(character)들의 집합
스택 (Stack)
한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 자료구조
LIFO: Last In First Out
삽입:
push
삭제:pop검색 시간 = O(n)
[ 활용 예시 ]
- 웹 브라우저 방문기록
- 실행취소 (Undo, Ctrl + Z)
큐 (Queue)
양 쪽에서 데이터의 입출력이 가능한 자료구조
FIFO = First In First Out
삽입:
enqueue
삭제:dequeue
읽기:peek
맨앞:front
맨뒤:rear검색 시간 = O(n)
[ 활용 예시 ]
- 대기열
- 그래프의 너비우선탐색 (BFS)
- 선형 큐
막대 모양으로 된 큐
크기가 제한되어 있고 빈 공간을 사용하려면 모든 데이터를 꺼내거나 데이터를 한 칸씩 옮겨야 함
- 문제점:
배열로 큐를 선언할 경우, 삭제와 생성을 반복하여 마지막 배열에 도달했을 때 데이터 공간이 남아있음에도 오버플로우가 발생
- 환형 큐 (원형 큐)
선형 큐의 문제점을 보완, 1차원 배열이지만 논리적으로 배열의 처음과 끝이 연결되어 있다고 생각
front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식
- 우선순위 큐 (Priority Queue)
먼저 들어온 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나감
힙 방식이 최악의 경우에도 O(log n)을 보장하므로 일반적으로 힙을 통해 구현
[ 활용 예시 ]
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제의 작업 스케쥴링
힙 (Heap)
우선순위 큐를 위해 고안된 완전이진트리(Complete Binary Tree) 형태의 비선형 자료구조
- 여러 값 중 최대값 혹은 최소값을 찾아내는 연산이 빠름
- 부모 노드와 서브 트리간 대소관계가 성립 (반정렬 상태)
- 이진탐색트리와 달리 중복값을 허용
- 검색시간 : O(log n)
- 최대 힙
부모 노드의 키값이 자식 노드보다 크거나 같은 완전이진트리
- key(부모노드) >= key(자식노드)
- 최소 힙
부모 노드의 키값이 자식 노드보다 작거나 같은 완전이진트리
- key(부모노드) <= key(자식노드)
연결 리스트 (Linked List)
노드(Node)로 구성된, 선형 자료구조
인접한 메모리 공간에 저장되는 배열과 다르게 연결 리스트는 실제 메모리 공간에서 아무 규칙없이 저장
- 노드의 구성
데이터 변수: 실제 값을 저장
포인터 변수: 다음 노드의 주소를 저장
배열과 차이점
데이터의 추가/삽입 및 삭제가 용이
일반적으로 탐색 속도가 떨어짐 ( 노드를 하나하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없음 )
= 탐색 / 정렬 이 많을 때 : 배열
= 추가 / 삭제 가 많을 때 : 연결 리스트
- 장점
- 단순한 구조로 이루어져 구현이 편하고 CRUD가 용이함
- 배열은 크기를 미리 선언하는 정적 할당이지만, 연결 리스트는 - 필요시에만 노드를 생성하는 동적 할당이므로 메모리 사용이 효율적
- 현재 노드가 가진 포인터 정보를 이용해 추가적인 연산없이 다음 노드를 가져올 수 있음
- 단점
- 노드에 데이터 뿐만 아니라 포인터도 저장해야 하므로 추가 메모리가 필요
- Random Access 가 불가능 ( 특정 주소의 노드를 찾기 위해선 많은 연산이 필요 )
맨앞:
Haed
- Head 노드는 항상 존재하며 데이터 변수에는 아무것도 저장하지 않음
맨뒤:Tail검색 시간 : O(n)
[ 활용 예시 ]
- 지하철 노선도
- 다시 실행 (Redo, Ctrl + Y) 및 실행취소 (Undo, Ctrl + Z) 명령어 로직
- 영화, 음악 등의 플레이 리스트
해시 테이블 (Hash Table)
(Key, Value)로 데이터를 저장하는 자료구조 ( 선형, 비선형 모두 속하지 않음 )
각각의 key 에 해시함수를 적용, 고유한 index를 생성하고 index에 종속되는 버킷(슬롯)에 값을 저장
- 장점
- 빠른 CRUD 가능
- 단점
- 해시 충돌이 발생할 경우 처리 속도가 느려짐
- 해시 함수의 로직이 복잡할수록 처리 속도가 느려짐
- 데이터가 순차적으로 저장되지 않아 빈 공간이 발생하기 때문에, 메모리 효율이 떨어지고 데이터 순서가 보장되지 않음.
평균 O(1)의 시간복잡도를 가지고 있지만
해시 충돌시, Chaining에 연결된 리스트들까지 검색하므로 O(n)
[ 활용 예시 ]
- Python의 Dictionary 자료형
- Mongo DB
- 캐시 메모리
비선형 자료구조
| 포인트 | 그래프 | 트리 |
|---|---|---|
| 정의 | 객체 혹은 노드(Node) 연결하는 간선(Edge)으로 모인 구조 | 그래프의 한 종류 방향성이 없으며 순환하지 않음 |
| 방향성 | 무방향 혹은 유방향 | 무방향 |
| 순환성 | 순환, 비순환 모두 가능 자기 자신을 연결하는 간선 가능(Self-Loop) | 순환 불가능 Self-Loop 불가능 |
| 루트 | 루트가 없어도 됨 | 하나의 루트 존재 |
| 모델 | 네트워크 모델 | 계층 모델 |
| 순회 | BFS, DFS | 전위(Pre), 중위(In), 후위(Post) |
| 간선 수 | 그래프에 따라 다름, 없을 수도 있음 | N 개의 노드에 대한 간선 (N-1)개 존재 |
그래프 (Graph)
객체들이 쌍으로 연관되어 집합을 이루는 자료구조
트리(Tree)도 그래프 구조의 일종
그래프 탐색: 깊이 우선 탐색(DFS), 너비 우선 탐색 (BFS)
[ 활용 예시 ]
- 네트워크 연결
- 경로 찾기
- 순서 확인
- 연결성 확인
트리 (Tree)
노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조
트리 안에 다른 하위 트리가 계속 존재할 수 있는 재귀적 자료구조
- 특징
하나의 루트 노드와 0개 이상의 하위 트리
순환(Loop)가 없는, 연결된 무방향 그래프
노드 간 부모-자식 관계를 갖는 계층형 자료구조, 모든 자식 노드는 하나의 부모 노드만 가짐
노드가 n개인 트리는 항상 (n-1)개의 간선을 가짐
- [ 활용 예시 ]
- 계층적 데이터 저장 ( 파일, 폴더 구조 등)
- 효율적인 검색 속도 보장
- 힙(Heap = 우선순위 큐)
- 데이터베이스 인덱싱 ( B-Tree, B+Tree, AVL-Tree, ... )
- Trie (사전을 저장하는 데 사용되는 특별한 종류의 트리 )
출처 : 사진 클릭 시 이동
