Array vs Linked List
Array
- 논리적 저장 순서와 물리적 저장 순서 일치 > 인덱스로 해당 원소에 접근 가능
- 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 한 가지의 작업을 추가적으로 해줘야 하기 때문에 다수의 시간 소요
- 원소 삭제 시, 배열의 연속적인 특징이 깨지게 되어 빈 공간생성 > 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하여 시간 복잡도 = O(n)
- 삽입, 삭제 기능에 대한 시간복잡도는 O(n)
Linked List
- Array의 시간복잡도 문제를 해결하기 위한 자료구조
- 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있어 해당 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 에 해결
- 원하는 위치에 삽입 또는 정렬을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 모두 확인 필요 < 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문
- search 시 O(n)의 time complexity를, 삽입, 삭제 시에도 O(n)의 time complexity 필요
- Tree 구조의 근간이 되는 자료구조이며, Tree 구조에서 사용 시 유용
Stack vs Queue
Stack
- 선형 자료구조 일종
- Last In First Out : 나중에 삽입된 원소가 가장 먼자 배출
Queue
- 선형 자료구조 일종
- First In First Out : 먼저 삽입된 원소가 가장 먼저 배출
Tree
비선형 자료구조로, 계층적 관계 (Hierarchical Relationship)를 표현하는 자료구를이다.
- Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미
- Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
- Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미
- Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미
- Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함
Binary Tree (이진 트리)
- 루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 분할 (서브 트리 모두 이진 트리)
- 각 층별로 숫자를 매겨 이를 트리의 Level(레벨)이라 정의. (레벨의 값은 0 부터 시작. 루트 노드의 레벨은 0)
BST (Binary Search Tree)
- 이진 탐색 트리
- 데이터를 저장하는 규칙 보유
- 이진 탐색 트리의 노드에 저장되는 키는 유일
- 부모의 키가 왼쪽 자식 노드의 키보다 크다.
- 부모의 키가 오른쪽 자식 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리
- O(log n)의 시간 복잡도 (O(h)) < 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수 두 배씩 증가
- Skewed Tree(편향트리) 될 가능성 다수 (시간 복잡도 O(n))
Binary Heap
- Tree의 형식 중 배열 기반 Complete Binary Tree
- 0 번째 제외 1번 index부터 루트 노드 시작 (노드 고유 값과 배열 index를 일치시켜 혼동 제어)
- Max Heap : 노드의 값이 해당 children의 값보다 크거나 같은 complete binary tree. 배열을 사용하여 효율적으로 관리
- Min Heap : 노드의 값이 해당 children의 값보다 작은 complete binary tree.
Hash Table
hash
내부적으로 배열을 사용하여 데이터를 저장하여 빠른 검색 속도 보유 (고유 index로 접근)
