Data structure, 자료구조
- Data의 표현 및 저장 방법
- 저장되어 있는 Data를 처리하는 과정을 Algorithm이라고 한다.
Stack
stack과 queue는 javascript 작동원리를 배울 때도 등장 한다. Javascript를 parsing하면서 실행 순서대로 callstack에 쌓아두고 parsing이 끝났을 때 쌓인 실행 순서 가장 마지막부터 실행하는데 이를 last in first out이라고 한다.
- 빈 배열 또는 객체가 존재한다.
- 순서대로 빈 배열 또는 객체에 Data를 하나씩 추가하는 method가 존재한다.
- 뒤에서 부터 순서대로 하나씩 Data를 제거함과 동시에 제거하는 Data를 반환하는 method가 존재한다.
Queue
Queue 또한 javascript 작동 원리에 대해 공부하다 마주치게 되는 자료 구조 이다. stack과는 다르게 first in first out의 형태를 가지고 있다.
자료가 쌓이는 형태는 stack과 동일하지만 순서는 가장 처음에 들어온 자료부터 가져오는 형태이다.
- 빈 배열 또는 객체가 존재한다.
- 순서대로 빈 배열 또는 객체에 Data를 하나씩 추가하는 method가 존재한다.
- 순서대로 하나씩 Data를 제거함과 동시에 제거하는 Data를 반환하는 method가 존재한다.
Linked List
자료구조 내 요소들을 node라고 한다. linked list는 각 요소들 끼리 연결점을 만들어 연결시켜 쌓아놓은 자료구조이다. playlist를 예로 들 수 있다. 현재 재생하고 있는 음악 또는 video는 이전과 다음 재생할 목록을 가지고 있고 마지막 재생목록은 다음 목록이 존재할 수도 아니면 다시 재생 목록의 처음으로 연결시켜 다시 처음부터 재생할 수 있다.
위의 내용을 풀어서 순서대로 작성해보자
- linked list는 node를 가지고 있다.
- node는 다음 node와 연결되어야 한다.
- linked list는 처음과 마지막 node를 알고 있어야 한다.
- 마지막 node는 추가될 수 있다.
- 마지막 node는 처음 node를 알고 있다.
Hash Table
hash table은 서로 hash로 연결되어 있는 자료구조이다. 회원가입을 하고 login을 하면서 서버에서 발급받는 token도 hash함수로 만들어진 key의 예라고 보았다. 이를 가지고 회원정보에 접근하거나 회원이 저장해놓은 글이나 자료들에 접근할 수 있다. hash table은 가능한 최소한의 크기를 유지하고 필요한 때에만 크기를 늘려야 한다.
hash는 hash function이라는 key값을 만들어주는 함수가 있는데 아래에서 직접 확인해 볼수 있다.
https://passwordsgenerator.net/sha256-hash-generator/
위 내용을 순서대로 풀어보자.
- hash table은 들어오는 정보를 가지고 일정한 길이의 암호, key를 만들어주는 hash function을 가지고 있다.
- hash function으로 받은 key 값은 hash table의 index값이 된다.
Graph
Vertex와 edge로 이루어져 있는 자료구조이다. Tree도 graph의 일종이지만 graph는 부모와 자식 node 개념이 없으며 edge가 없을 수도 있다.
Tree
하나의 최상위 root에서 2개의 child를 가지며 내려가는 구조이다. child에서 child를 다시 가질 수 있으며 child도 2개의 child를 가질 수 있다.
child에서 상위 node를 parent라 하고 node와 node사이의 접근 거리를 depth라고 한다. 같은 부모를 가지고 같은 depth에 위치한 node들을 sibling 관계에 있다고 한다.
BST, Binary search tree
BST는 root 또는 parent보다 작으면 왼쪽에, 크면 오른쪽에 정렬하는 자료구조이다. 이 또한 tree구조이기 때문에 각 Node는 2개의 child node를 가질 수 있고 앞 정렬 순서를 따라 간다.
BST를 탐색하는 방법으로 DFS, Depth-First-Search와 BFS, Breadth-First-Search가 존재한다. 
