Advanced Data Structure

1. Linked List (연결 리스트)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

배열과 비교 했을 때, 데이터를 삽입/삭제 할 경우 데이터의 재구성에 용이하다. 반면 특정 위치의 데이터를 검색하기 위해서는 연결리스트를 처음부터 끝까지 순회해야 하므로 비효율적이다.

 

*종류

1) 단일 연결 리스트

각 노드에 데이터 공간과 한개의 포인터 공간이 있고, 포인터는 다음 노드를 가리킨다.

 

2) 이중 연결 리스트

단일 연결리스트와 비슷하지만, 포인터 공간이 두 개가 있고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

 

3) 원형 연결 리스트

일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

 

2. Graph

그래프란 연결되어있는 객체 간의 관계를 표현할 수 있는 자료구조로써, 하나이상의 정점(노드)와 두 정점간의 관계인 간선(링크)로 구성된다.

* 종류

1) 무방향 그래프

간선을 통해서 양 방향으로 갈 수 있는 자료구조, 방향성이 없다.

 

2) 방향 그래프

간선에 방향성이 존재하는 그래프, 연결되어있더라도 가진 방향대로만 갈 수 있다.

 

3. Tree

하나의 0개이상의 자식노드를 가진 루트노드를 가지고, 그 자식노드 또한 0개이상의 자식노드를 갖고 있는 형태로 반복적으로 이루어진 계층적인 자료구조, 노드들과 노드들을 연결하는 링크들로 구성된다.

 

*용어

- 루트 노드(root node) : 부모가 없는 노드, 트리 자료구조는 하나의 루트 노드만을 가진다.

- 단말 노드 : 자식이 없는 노드

- 형제 노드 : 같은 부모를 가지는 노드

- 노드의 크기 : 자신을 포함한 모든 자손 노드의 개수

- 노드의 깊이 : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선(링크)의 수

- 노드의 레벨 : 트리의 특정 깊이를 가지는 노드의 집합

- 노드의 차수 : 각 노드가 지닌 간선(링크)의 수

- 트리의 차수 : 트리 내의 노드의 차수중 가장 큰 값

 

4.  Binary Search Tree

* 정의

1) 각 노드가 최대 두개의 자식을 갖는 탐색 트리이다.

2) 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다.

(여기서 key값은 각 개체에 대한 저장 단위를 의미한다.)

 

*탐색 방법

원하는 값이 k라고 하면,

1. 트리가 비어있다면 k는 트리에 있을 수 없다.

2. 만약 루트노드의 값이 k라면 이 값을 리턴

3. k값이 루트노드보다 작으면 왼쪽 서브트리로, k값이 루트보다 크면 오른쪽 서브트리로 넘어가서 탐색한다.

4. 3번과정을 계속해서 반복하며 원하는 값 k를 찾는다.

 

5. Hast Table

내부적으로 배열을 사용하여 데이터를 저장하며,  특정한 값을 검색하는데 데이터 고유의 인덱스로 접근하게 때문에 빠른 검색 속도를 갖는다.