[데이터베이스]자료 구조의 분류-hoyhi-tistory

선형 구조

• 선형 리스트(Lienear , 배열)
• 연결 리스트(Linked List)
• 스택(Stack)
• 큐(Queue)
• 덱(Deque)

비선형 구조

• 트리(Tree)
• 그래프(Graph)

 

선형 리스트(Lienear List)

 

 

연결리스트(Linked List)

- 연결 리스트는 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조

- 노드의 삽입, 삭제 작업이 용이

- 기억 공간이 연속적으로 놓여 있지 않아도 저장 가능

- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않음

- 접근 속도가 느림

- 희소 행렬을 연결 리스트로 표현하면 기억 장소가 절약

- 트리를 표현하기에 적합

 

 

스택(Stack)

- 리스트의 한쪽 끝으로만 자료의 삽입,삭제가 가능한 자료 구조

- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 LIFO(Last In First Out, 후입선출) 방식으로 자료 처리

- TOP : Stack으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소(=스택 포인터)

- BOTTOM : Stack의 가장 밑바닥

​

Stack의 용도

- 부 프로그램 호출 시 복귀주소를 저장할 때

- 함수 호출의 순서 제어

- 인터럽트가 발생하여 복귀주소를 저장할 때

- 후위 표기법(Postfix Notation)으로 표현된 산술식을 연산할 때

- 0 주소지정방식 명령어의 자료 저장소

- 재귀 프로그램의 순서 제어

- 컴파일러를 이용한 언어 번역 시

 

 

큐(Queue)

- 선형 리스트의 한 쪽에서는 삽입 작업이 이루어지고 다른 한 쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조

- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO) 방식으로 처리

- 시작과 끝을 표시하는 2개의 포인터

1) 프론트 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가르키는 포인터로, 삭제 작업을 할 때 사용

2) 리어 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로, 삽입 작업을 할 때 사용

​

큐 사용 예

- 창구 업무처럼 서비스 순서를 기다리는 등의 대기 행렬 처리에 사용

- 운영체제의 작업 스케줄링

 

 

 

덱(Deque)

- 삽입과 삭제가 리스트의 양 끝에서 모두 발생 가능한 자료 구조

- Double Ended Queue의 약자

- Stack 과 Queue의 장점만을 따서 구성

- 입력이 한 쪽에서만 일어하고 출력은 양 쪽에서 일어날 수 있는 입력 제한과 --> Scroll

  입력은 양 쪽에서 일어나고 출력은 한 쪽에서만 일어날 수 있는 출력 제한이 있음 --> Shelf

 

 

 

트리(Tree)

- 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태

- 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

-> A, B, C, D, E, F, G, H, I, J, K, L, M

​

- 근 노드(Root Node) : 트리의 맨 위에 있는 노드

-> A

​

- 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수

-> A=3, B=2, C=1, D=3, E=2

​

- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

-> 3

​

- 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드

-> F, G, I, J, K, L, M

​

- 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드

-> A, B, C, D, E, H

​

- 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들

-> D의 자식 노드 : H, I, J

​

- 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들

-> D의 부모 노드 : A

​

- 형제 노드 : 동일한 부모를 갖는 노드들

-> D의 형제 노드 : B, C

​

- Level : 근 노드의 Level을 1로 가정 후 어떤 Level이 L이면 자식 노드는 L+1

-> D의 레벨 : 2

​

- 깊이(Depth) : 어떤 트리에서 노드가 가질 수 있는 최대의 레벨

-> 3

 

 

 

그래프(Graph)

좌 : 무방향 그래프 / 우 : 방향 그래프

 

무방향 그래프
- 두 접점을 연결하는 간선에 영향이 없는 그래프
- 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현
=> (Vi, Vj) = (Vj, Vi)


방향 그래프
- 다이그래프 ( digraph )라고도 하는데, 간선에 방향이 있는 그래프
- 방향 그래프에서 정점 Vi에서 정점 Vj를 연결하는 간선, 즉 Vi→Vj를 <Vi, Vj>로 표현하고 화살표로 표현

- Vi를 꼬리(Tail) Vj를 머리(head)
=> <Vi, Vj> ≠ <Vj, Vi>