Data Structure 02:

Linked List

• 노드가 데이터와 포인터를 가지고 일렬로 연결된 형태의 자료 구조.
• 포인터는 다음 데이터의 주소를 가지고 있다.
• 데이터의 주소를 일일이 찾아다녀야 하기 때문에 배열보다 느릴 수 있다.
• 배열은 배열의 길이를 늘리거나 줄일 수 없는 반면, 링크드리스트는 연결된 데이터의 주소를 추가/삭제 해서 데이터를 늘리거나 줄일 수 있다. 따라서 길이가 정해지지 않은 데이터를 핸들링 할 때 적합함.

Graph

• 노드들이 다양한 연결관계를 갖고 있는 자유로운 형식의 자료구조. 네트워크 모델 이라고도 한다.
• 그래프에는 노드와 엣지가 있으며 에지의 방향이 있으면 Directes graph, 없으면 Undirected graph라고 한다.
• 검색방법에는 깊이우선검색Depth First Search, 넓이우선검색 Breadth First Search 두 가지 방식이 있음.
• 그래프를 자료구조에 저장하는 방법에는 두 가지가 있다.
  - 이차원배열(Matrix) 에 담는 방법 : 서로 연결되면1, 연결이 없으면 0.
  - Linked List에 담는 방법: 인접한 노드들을 링크드리스트에 담음. 

 

Tree

• 그래프의 한 종류로 방향성을 가진 비순환 그래프에 해당하는 계층이 있는 데이터 구조다. 
• 트리는 항상 root 부터 시작해서 아래로 가지치기를 하는데 트리 맨 끝에 자식이 없는 노드는 leaf라고 함.
• 하나의 노드에는 하나 이상의 차일드 노드가 붙을 수 있다.
• 노드에 최대 2개까지의 차일드가 붙는 트리를 Binary tree 라고 하는데 가장 많이 쓰이는 트리 구조다.

 

Binary Search Tree

• 바이너리 트리이면서 왼쪽 노드와 그 이하 차일드 노드가 현재 노드의 값보다 작고, 오른쪽 노드와 그 이하 차일드 노드의 값이 현재보다 크게 배열된 구조이다.
• 어떤 값을 찾을 때 root에서 부터 두 갈래 길을 선택해서 가다보면 그 값을 찾을 수 있다. 찾으려는 값과 비교해서 작으면 왼쪼그 크면 오른쪽 으로 내려가며 탐색할 수 있다.

 

Hash Table

• 해시 함수를 이용해서 데이터를 저장하는 자료구조.
  검색하고자 하는 키값을 => 해시 함수를 돌려서 => 나온 해시 코드를 => 배열의 인덱스로 환산해 데이터에 할당/접근 함.
• 해시함수: 특정한 규칙을 이용해서 키값을 이용해서 특정 코드를 반환함.
• 활용예: 블록체인 공공장부를 검색할때도 해시함수를 이용함. 해시코드만 비교해서 빠르게 확인.
• 장점: 검색 속도가 매우 빠르다. 해시코드 자체가 배열방의 인덱스로 사용하기 때문에 검색을 하지 않고 배열에 다이렉트로 접근하기 때문. 
• 입력받은 키를 가지고 얼마나 잘 분배하는지 여부가 좋은 알고리즘인지를 결정함.
• 해시테이블 충돌(Collision): 키값은 문자열이고 해시코드는 정수기 때문에 다른 값을 입력해도 인덱스가 같은 경우가 발생할 수 있음. 해결 방법은 두 가지.
  - 연결리스트 Linked List : 배열방 안에 링크드리스트를 만들고 데이터가 할당될 때마다 리트스를 추가한다.
  - 선형탐사 Linear probing : 충돌이 발생한 지점의 다음 인덱스부터 찾아서 빈 인덱스가 있으면 그곳에 데이터를 저장.