Array vs Linked List
Array
가장 기본적인 자료구조인 Array는 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 해당 원소(element)에 접근할 수 있다. Array 자료구조는 배열의 원소 중 어느 원소를 삭제했다고 했을 때 빈 공간이 생겨 배열의 연속적인 특징이 깨지게 된다. 삭제와 삽입 시 1씩 shift 해줘야해서 시간과 비용이 발생한다.
Linked List
Array 자료구조의 문제점을 해결하기 위한 자료구조가 linked list다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 빨리 해결할 수 있다. 하지만 linked list는 Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다. Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.
참고 : https://opentutorials.org/module/1335/8857
참고 : https://freestrokes.tistory.com/84
Stack and Queue
Stack
선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.
- 선형 자료구조 : 하나의 자료 뒤에 하나의 자료가 존재하는 것으로 배열과 리스트가 있다.
Queue
선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 놈이 먼저 나온다. Stack 과는 반대로 작동된다. 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 Priority queue등을 사용할 수 있다.
heap
참고 : https://suyeon96.tistory.com/31
참고 : https://all-young.tistory.com/17
Tree
트리는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 비선형 자료구조이다. 그래서 계층적 구조를 표현할 수 있다.
트리를 구성하고 있는 구성요소들(용어)
- Node (노드) : 트리를 구성하고 있는 각각의 요소
- Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드
- Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
Binary Tree (이진 트리)
루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.
- Perfect Binary Tree (포화 이진 트리)
- Complete Binary Tree (완전 이진 트리)
- Full Binary Tree (정 이진 트리)
BST (Binary Search Tree)
이진 탐색 트리에는 데이터를 저장하는 규칙이 있다.
1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이럴 경우 성능에 영향을 미치게 되며 시간과 복잡도가 높아진다. 트리의 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 한다.
