자료구조란, 여러 데이터들의 묶음을 어떻게 저장하고 사용할 것인지 정의한 것이다. 여기서 데이터(data)란, 문자, 숫자, 소리 등 실생활을 구성하고 있는 것들을 말한다
자료구조는 형태에 따라 선형 구조, 비선형 구조로 나눌 수 있다.
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
console.log(stack); // [1, 2, 3, 4, 5]
stack.pop();
stack.pop();
console.log(stack); // [1, 2, 3]
// const array = new Array() 미리 정의된 Array 객체를 사용합니다.
const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
queue.push(5);
console.log(queue); // [1, 2, 3, 4, 5]
queue.shift();
queue.shift();
console.log(queue); // [3, 4, 5]
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
여기서 점은 정점(vertex)로, 선은 간선(edge)로 표현한다.
알아둬야 할 개념
그래프는, 두 가지의 표현 방식이 있다.
인접행렬은, 정점들간의 인접함을 표시해 주는 행렬으로 2차원 배열의 모습을 가진다.
한 개의 표와 같은 모습을 하기 때문에 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다. 주로 가장 빠른 경로를 찾고자 할 때 사용된다.
출처 : Code States
인접 리스트는 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식이다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트에는 자신과 인접한 다른 정점들이 담겨 있다.
인접 행렬은 모든 경우의 수를 저장하기 때문에 메모리를 많이 차지한다. 따라서 메모리를 효율적으로 사용하고 싶다면 인접 리스트를 사용한다.
출처 : Code States
:그래프를 탐색하는 방법
- 인접 리스트 : O(n+e)
- 인접 행렬 : O(n^2)
- 인접 리스트 : O(n+e)
- 인접 행렬 : O(n^2)
데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조
- 루트(Root) : 최상위 노드
- 부모 노드(Parent Node) : 상위 노드
- 자식 노드(Child Node) : 하위 노드
- 리프 노드(Leaf Node): 자식 노드가 없는 최하위 노드
- 형제 노드(Sibling Node) : 같은 레벨에 나란히 있는 노드
트리에서는 높이와 깊이를 잴 수 있는데, 루트에서 자신에게 걸리는 거리를 레벨(Level)이라고 부르고, 루트는 Level 1로 설정한다. 루트로부터 가장 안쪽에 있는 노드까지의 레벨을 트리의 높이라고 하고, 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이라고 표현한다.
실사용 예: 컴퓨터의 디렉토리 구조, 가계부, 조직도 등
- 완전 이진 트리(Full binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 적어도 마지막 레벨 노드의 왼쪽이 채워져 있는 트리
- 정 이진 트리(Complete Binary Tree) : 모든 노드의 자식이 없거나 두 개인 트리.
- 포화 이진 트리(Perfect Binary Tree) : 완전 이진 트리이면서, 정 이진 트리인 트리