1. Array
- 동일한 타입의 데이터만 저장 가능
- 고정된 크기
- 0부터 시작하는 인덱스로 데이터에 접근 가능 → 모든 요소에 빠르게 접근 가능, 원하는 데이터에 무작위로 접근(RandomAccess) 가능
- 다차원으로 생성 가능
- but, 데이터 추가/삭제는 각 원소를 shift해야 하므로 오래 걸림(시간복잡도: O(n))
- Stack 구현 시 주로 사용
1-1. Array List
- 가변되는 크기
- 데이터 추가/삭제 시 메모리를 재할당 하므로 속도가 Array보다 느림
2. Linked List
- head → 데이터 + 포인터 → 데이터 + 포인터
- 다음 노드의 주소를 가지고 있는 포인터를 가지고 있음
- 배열은 크기가 고정되어 있어 메모리의 낭비가 있으나, Linked List는 메모리의 낭비가 적음
- 데이터 추가/삭제는 빠름(시간복잡도: O(1))
- but, 순차 접근만이 가능
- Queue 구현 시 주로 사용
3. Stack
- 동일한 타입의 데이터만 저장 가능
- LIFO(Last In, First Out)
- 중간에 값을 끼워넣을 수 없음(전부 빼고 다시 넣어야 함)
- 실행 취소나 메모리의 지역변수 및 매개변수 저장되는데에 주로 사용
- 인덱스만 줄이면 되니까(LIFO) Array List로 주로 구현
4. Queue
- 동일한 타입의 데이터만 저장 가능(?)
- FIFO(First In, First Out)
- OS의 프로세스 관리, 캐시, 너비 우선 탐색에 주로 사용
- 객체만 줄이면 되니까(FIFO) Linked List로 주로 구현
5. Tree
- 노드가 계층적으로 이어진 비선형 자료 구조
- 사이클이 생기지 않는 그래프의 특수한형태
- 디렉터리 구조에 주로 사용
5-1. BST(Binary Search Tree)
- 이진트리: 자식 노드가 최대 2개
- 이진 탐색 트리(BST): 이진 탐색(효율적 탐색) + 연결 리스트(데이터 추가/삭제 유용)
- 왼쪽 트리의 모든 값은 부모보다 작아야 하고, 오른쪽 트리의 모든 값은 부모보다 커야 함(Q. 같은 값은?)
- 시간복잡도: O(h = 높이) → 트리가 한 쪽으로 치우쳐진 worst case는 O(n)
5-2. RBT(Red-Black Tree)
- BST에서 데이터 추가/삭제의 문제점 해결을 위해 등장
- 자식이 없을 경우 포인터는 NIL
- 모든 노드를 Red or Black으로 칠하는데 연결된 노드끼리는 색이 겹치지 않음(즉, 자식과 부모는 항상 색이 다름)
6. Heap
- 완전 이진 트리: 자식 노드는 반드시 0 or 2개를 가져야하며, 왼쪽부터 채워짐(Array로 구현 가능)
- 최대 힙: 부모 노드가 자식 노드보다 크거나 같음
- 최소 힙: 부모 노드가 자식 노드보다 작거나 같음
- 최댓값 or 최솟값 찾을 때 주로 사용
- 우선순위큐(시간복잡도: O(log n))에 주로 사용
7. Hash Table
- 해시함수를 통해 인덱스와 키로 저장
- Null은 허용 x
- 데이터 크기에 상관없이 삽입 및 검색에 효율적이며 빠름(시간복잡도: O(1) ~ O(n))
- 데이터 베이스 인덱스 구현이나 사용자 로그인 인증에 주로 사용
7-1. Hash Map
- 병렬 처리를 하지 않을 때(동기화 고려 x) thread-safe하지 않음(?)
- Null 허용
8. Graph
- 정점과 간선으로 이루어진 자료구조(간선은 없을 수도)
- 웹 페이지 및 링크를 나타나는 데 주로 사용
+) Ref
https://jin-network.tistory.com/127
https://mangkyu.tistory.com/89
https://dev-coco.tistory.com/159
