1. Linked List
연결리스트의 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 공간(Next)으로 구성되어 있으며, 이런 노드들이 한 줄로 연결되어 있는 방식의 자료 구조이다.
첫 노드를 가리키는 시작점을 Head라고 부르며, 아무것도 가리키는 것이 없는 마지막 노드인 Tail이 있다.
연결리스트는 다음 데이터의 정보만 가지고 한 방향으로만 연결되는 단일연결리스트(Singly-Linked List)와 이전 데이터의 정보도 가지고 있는 이중연결리스트(Doubly-Linked List)로 나누어볼 수 있다.
- Method
> Insert : 리스트의 시작에 노드를 추가한다
> Search : 주어진 키의 값에 해당하는 데이터를 찾는다
> Delete : 리스트의 첫번째 노드 또는 주어진 키에 해당하는 값을 삭제한다
> Display : 주어진 키의 값에 해당하는 데이터를 보여준다
2. Hash Table
- Property
> Key : Hash Function의 input
> Hash Function : key를 index에 매칭되도록 변환해주는 함수
> Index : hash function의 결과물이 매칭됨
> Value : 저장소에 최종적으로 저장되는 값
- Method
> Search : key를 Hash Function으로 변환하여 매칭되는 index의 value을 찾는다
> Insert : key를 Hash Function으로 변환하여 매칭되는 index의 value로 저장한다
> Delete : key를 Hash Function으로 변환하여 매칭되는 index의 value로 삭제한다
3. Graph
그래프는 vertex(node)와 그들을 연결하는 edge(arc)로 이루어진 비선형 자료 구조이다.
- Property
> Vertex/Node : 그래프를 이루고 있는 각 데이터
> Edge : 노드와 노드를 잇는 선
> Distance : 두 노드를 잇는 edge의 갯수
> Eccentricity : 두 노드의 distance 중 가장 긴 distance
> Radius : 두 노드의 distance 중 가장 짧은 distance
> Adjacency : 두 노드가 edge로 바로 연결되어 있다면 두 노드는 인접하다고 할 수 있다
> Degree : 해당 노드에 연결된 edge의 갯수
> Loop : 하나의 edge가 같은 노드에 부속해 있는 경우
> Isolated : 한 노드에 부속해있는 edge가 전혀 없는 경우
- 비방향성 그래프(Undirected graph) & 방향이 있는 방향성 그래프(Directed graph)
: 엣지의 방향성 여부에 따라 나뉨
- 가중치 그래프(Weighted Graph) : 엣지에 가중치가 할당된 그래프
그래프의 구현방식
1. Adjacency Matrix : 두 노드가 인접하고 있는지를 매트릭스로 나타냄
2. Adjacency List : 두 노드가 인접하고 있는지를 링크드 리스트로 나타냄
- Method
> add Vertex: adds the vertex x, if it is not there
> remove vertex: removes the vertex x, if it is there;
> add edge: adds the edge from the vertex x to the vertex y, if it is not there
> remove edge: removes the edge from the vertex x to the vertex y, if it is there
> adjacent: tests whether there is an edge from the vertex x to the vertex y
#DFS(깊이우선탐색)
#BFS(너비우선탐색)
4. Tree
트리는 node와 edge로 이루어진 자료구조이다.
트리는 모두 그래프에 속하지만, 모든 그래프가 트리 구조를 가지지는 않는다.
- Property
> Root : 부모가 없는 노드, 가장 꼭대기에 있는 노드
> Leaf : 자식 노드가 없는 노드
> Edge : 노드와 노드를 잇는 선
> Height : 부모와 자식 노드 사이의 edge 갯수
> Siblings : 같은 부모를 가지는 노드
> Path : Path refers to the sequence of nodes along the edges of a tree
> Parent : Any node except the root node has one edge upward to a node called parent
> Child : The node below a given node connected by its edge downward is called its child node
- Method
> Insert : Inserts an element in a tree/create a tree
> Search : Searches an element in a tree
> Delete : Deletes an element in a tree/create a tree
4-1. Binary Search Tree
트리 구조 중에서 각각의 노드가 최대 2개의 자식노드를 가지는 구조를 이진 트리라고 하며,
그 중 노드의 왼쪽 서브트리에는 그 노드의 값(key)보다 작은 값을 가지는 데이터만 있고, 오른쪽 서브트리에는 그 노드의 값보다 큰 값을 가지는 데이터만 있는 구조를 이진탐색트리라고 한다.
(서브트리(subtree) : subtree represents the descendants of a node)
이진탐색트리는 값의 크기에 따라 데이터를 정리해 놓았으므로 값을 찾기가 쉽다는 장점을 가지고 있다.
- 순회(Traversal)
> 선위순회(Preorder Traversal) : V→L→R
8 - 3 - 1 - 6 - 4 - 7 - 10 - 14 - 13
> 중위순회(Inorder Traversal) : L→V→R (오름차순으로 정리됨)
1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14
> 후위순회(Postorder Traversal) : L→R→V
1 - 4 - 7 - 6 - 3 - 13 - 14 - 10 - 8
'TIL (Today I Learned)' 카테고리의 다른 글
| REACT-NATIVE Android 환경설정 (0) | 2020.06.04 |
|---|---|
| TIL <6> 객체의 상속 (0) | 2020.03.25 |
