데이터구조: Linked List, Graph, Tree, Binary Search Tree, Hash Table

1. 연결 리스트(Linked List)

'Linked List' 란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 형태의 자료구조

• 연결 리스트(Linked List)는 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당함
• 연결 리스트는 노드의 중간점에서도 자료의 추가/삭제가 가능하다는 장점이 있음
• 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있음

연결 리스트 데이터 삽입

[1, 3, 5]의 리스트에 [2]를 삽입해서 [1, 2, 3, 5] 리스트를 만드는 경우

• 1을 2와 연결하고 2를 3과 연결

연결 리스트 데이터 삭제

[1, 3, 5]의 리스트에 [3]을 삭제해서 [1, 5] 리스트를 만드는 경우

• 1과 5를 연결하면 3은 가비지 컬렉터에 의해 정리됨

2. 그래프(Graph)

'Graph' 란 노드들이 다양한 연결관계를 갖고 있는 자유로는 형식의 자료구조. 네트워크 모델이라고도 함

• 그래프에는 트리와 마찬가지로 노드와 엣지가 있으며, 각각 버텍스와 아크라고 부름
• 다른 버텍스로부터 아크가 오는 개수를 In-dergee, 반대가 Out-degree라고 함
  • 버텍스는 하나 이상의 In/Out-degree를 가질 수 있음
• 그래프에는 방향성이 있는가에 따라 방향 그래프와 무방향 그래프로 나뉨

• 그래프 표현에는 이차원배월과 연결리스트를 이용하는 방식이 있음
  1. 이차원배열: 공간은 많이 차지하지만 간단
  2. 연결리스트: 공간은 적게 차지하지만 복합

3. 트리(Tree)

'Tree' 란 그래프의 한 종류로 방향성이 있는 비순환 그래프의 한 종류

• 트리구조는 말 그대로 나무처럼 생긴 형태의 자료구조이며 root, leaf, 내부 노드로 구성됨
• 트리는 항상 root부터 시작해서 아래로 가지치기를 함
• 제일 마지막 노드를 leaf라고 부르면 root도 leaf도 아닌 노드들을 내부 노드라고 함
• 트리는 root와 하위 노드의 관계를 부모와 자식 관계로 표현할 수 있고 각 하위 노드는 또 다른 하위 노드를 가질 수 있음
  

4. 이진 탐색 트리(Binary Search Tree)

'Binary Search Tree' 란 한 개의 부모 노드가 최대 2개의 자식 노드를 갖는 트리를 말함

• 이진 탐색 트리는 한 개의 부모 노드가 최대 2개의 자식 노드를 갖는 형태임
• 찾을려는 value를 입력하여 value와 root를 비교하여 작으면 왼쪽, 크면 오른쪽으로 root를 바꿈
• 변경된 root를 기준으로 다시 지속적으로 비교하여 이동하고 더 이상 비교할 자식 노드가 없을 때 해당 위치에 데이터를 입력함

5. 해시 테이블(Hash Table)

'Hash Table' 이란 해시함수를 이용하여 데이터를 저장하는 자료구조

• 해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 해시 코드를 인덱스(index)에 저장함
• 해시 테이블은 매우 빠른 데이터 검색을 위해 사용됨

5.1. 해시 테이블 충돌(Collison)

• 해시 테이블 충돌이란 서로 다른 값을 해시 함수를 통과 시켜서 나온 해시 코드(인덱스의 주소)가 같은 경우를 말함
• 충돌을 해결하는 대표적인 방법은 다음 두 가지임

1. 연결 리스트(Linked List)

   • 같은 주소가 나왔을 때 해당 주소에 이미 데이터가 있다면 그 데이터에 연결 리스트로 연결

2. 선형탐사(Linear probing)

   • 충돌이 발생한 지점의 다음 인덱스부터 찾아서 빈 인덱스가 있으면 그 곳에 데이터를 저장

참고자료
1. https://codeburst.io/objects-and-hash-tables-in-javascript-a472ad1940d9
2. https://ko.wikipedia.org/w/index.php?search=%EA%B7%B8%EB%9E%98%ED%94%84+%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0&title=%ED%8A%B9%EC%88%98:%EA%B2%80%EC%83%89&go=%EB%B3%B4%EA%B8%B0&ns0=1
3. https://medium.com/@songjaeyoung92/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-javascript-hash-table-%EC%9D%B4%EB%9E%80-5f5345623dab