2019-12-30

bathingape·2019년 12월 30일
0

TIL(2019)

목록 보기
41/41

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


참고문서

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

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

  3. https://boycoding.tistory.com/33

profile
웹 개발을 위해 공부한 내용을 기록하고 있습니다.

0개의 댓글