[TIL] 12/30: Advanced Data Structure

(ref: https://www.geeksforgeeks.org/introduction-to-data-structures-10-most-commonly-used-data-structures/ )

1. Linked List: 선형 구조, 비연속적, 포인터 사용해 각 데이터 연결

 

•Node(노드)

   - Data(데이터)

   - Pointer(포인터): 다음 노드의 주소값이 담긴 변수

•Pointer(포인터): 다음 노드가 어디에 위치하는지 알려주는 표지판

 

 

	Array	Linked List
장점	데이터 탐색, 정렬 편리	데이터 추가, 삽입, 삭제가 용이 (포인터로 연결)
탐색속도	빠르다 (index로 접근)	(비교적) 느리다

 

Property

* Head : 첫 번째 노드 판별

Methods

1. Add(element): 맨 끝에 element 추가

 

2. Remove(element): element를 제거

 

3. insertAt(element, index): 주어진 index에 element 추가

 

4. 탐색

 

https://opentutorials.org/module/1335/8821

---

2. Graph: 비선형 구조, node(또는 vertice)와 edge로 이루어진 

* Reference

(ref: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html)

(ref: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/)

(ref: https://medium.com/@senaiayalew/graph-data-structures-6038a4b21fd6)

(ref: https://ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/describing-graphs)

 

* In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.

 

•Node(노드) 또는 Vertice

•Edge: 두 개의 노드를 연결하는 선이나 호(arc)

 

인접행렬: 노드를 2차원 배열로 만든 것 --> 공간을 많이 차지

연결리스트: 노드의 개수 + 간선의 개수 만큼 공간을 차지

 

Property

 

Methods

1. addVertex(v) – It adds the vertex v as key to adjList and initialize its values with an array.

2. addEdge(src, dest) – It adds an edge between the src and dest.

https://ko.khanacademy.org/computing/computer-science/algorithms

알고리즘 | 컴퓨터과학 | 컴퓨팅 | 칸아카데미

---

3. Tree : 계층형 구조

 

* Binary Tree(이진트리): 각각의 노드가 최대 2개의 자식 노드(좌우)를 가지는 자료구조

1. 데이터

2. 왼쪽 자식노드의 포인터

3. 오른쪽 자식노드의 포인터

---

4. Binary Search Tree(이진탐색트리): 계층형 구조

* 규칙

• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들

• 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들

• 좌우 하위 트리는 각각이 다시 이진 탐색 트리

 

* BST 삭제

장점: 탐색 속도가 빠르다

 

편향 트리를 최대한 피해야 한다

 

https://velog.io/@shaqok/Data-Structure-Linked-List-Graph-Tree-Binary-Search-Tree-Hash-Table

---

5. Hash Table

- Hash Function(해시함수): 주어진 키(key)를 통해 요소에 더 빨리 접근, 복호화가 불가능함

ex)  hash function H(x) maps the value x at the index x%10 in an Array.

For example, if the list of values is [11, 12, 13, 14, 15] it will be stored at positions {1, 2, 3, 4, 5} in the array or Hash table respectively.

- Hash Table: 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조

연관배열 구조
(associative array)

   : 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

 

- 키(key)는 해시 함수를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소(Bucket, Slot)에 저장

* 해시 알고리즘의 핵심은 충돌이 나지 않는 것 (속도 때문에 어느정도 충돌은 감안해야 함)

-- 충돌나는 걸 커버할 수 있는 충돌 알고리즘을 같이 구현

 

 

해쉬 함수가 만들어주는
인덱스는 유한한데
입력값은
무한데라서
충돌이 일어나고
충돌이 안일어날려면 인덱스가 많아져야하는데 많아지면 무거워서 느려진다


 

- Limited Array: 자바스크립트의 동적배열을 동적배열이 아닌 것으로 만들어 주는 것--> 사이즈를 제한한다

- getIndexBelowMaxforkey

https://www.reddit.com/r/programming/comments/86s6am/an_intuitive_visualization_of_hash_tables/

An intuitive visualization of hash tables

 

* Reference

(ref: https://hackernoon.com/the-little-guide-of-linked-list-in-javascript-9daf89b63b54)

(ref: https://boycoding.tistory.com/33)

 (ref: https://dororongju.tistory.com/107)

(ref: https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o)

(ref: https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o)