Today I Learn...
1. Linked List
연결 리스트는 일련의 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.
다음과 같은 특징이 있다.
- 연속되는 항목들이 포인터로 연결된다.
- 마지막 항목은 Null을 가리킨다.
- 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다. (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.
- 메모리 공안을 낭비하지 않는다.(하지만 포인터를 위한 추가의 메모리를 필요로 한다.)
- 배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.
즉, 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다.
Linked List 의 Property
- 첫번째 노드임을 판별하기 위해 Head 라는 노드가 첫번째 노드를 향하고 있습니다.
2. Graph
Graph 의 Property
- Vertex: Graph 에서는 노드라 불렀었던 저 1번을 “Vertex”(꼭지점)이라고 부릅니다.
- Edge: 포인터였던 화살표는 “Edge”(모서리)라 불립니다.
- In-degree: 자신에게 (들어)오는 Edge 들의 개수입니다.
- Out-degree: 반대로 자신이 향하는 Edge 들의 개수입니다.
(위의 그림처럼 화살표가 아닌 서로 연결된 Graph를 Undirected Graph라 하는데 이 때 총 degree 를 셉니다.)
3. Tree
Tree 의 Property
- Root node - A가 뿌리를 내리는 첫번째 노드가 됩니다.
- Child node - A가 뿌리를 내리면서 B-I 는 모두 누군가의 Child node가 됩니다.
- Parent node - A처럼 뿌리를 내리는 B-D는 모두 누군가의 Parent node가 됩니다.
- Sub-tree - B-D처럼 뿌리를 내린 부분은 조그만 sub-tree라고 할 수도 있습니다.
- Leaf node - H, I처럼 마지막 level에 존재하는 node가 leaf node가 됩니다. 나무의 끝에 있는 것이 나뭇잎인걸 생각하면 이해에 도움이 됩니다.
4. Binary Search Tree
Binary Search Tree 의 Property
- 각 노드는 데이터와 left 와 right 으로 향하는 포인터를 가지고 있습니다. 이 노드의 데이터 값보다 작은 노드를 추가하려면 left 를 연결, 크다면 right를 연결해줍니다.
5. Hash Table
Hast Table의 Property
- Hash function: key-value를 정렬/저장하기 위해 특정한 인덱스를 리턴하는 함수.
- Bucket: hasing된 value가 저장되는 곳.
- key: 요소의 key값, hash value를 검색할 때 사용할 수 있다.
- value: key값을 이용해 Bucket 안에 저장된 value를 탐색할 수 있다.
To-Do
참고문서
박레고의 개발 블로그