데이터베이스 자료 구조의 분류

 

데이터베이스 자료 구조의 분류는 크게 다음 두가지 형태로 나뉘어 진다.

 

1. 선형 구조

선형 리스트(Linear List, 배열), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), 데크(Deque)

 

2. 비선형 구조

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

 

 

연결 리스트(Linked List)

• 연결 리스트는 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
• 노드의 삽입, 삭제 작업이 용이하다.
• 기억 공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.
• 접근 속도가 느리다.
• 희소 행렬을 링크드 리스트로 표현하면 기억 장소가 절약된다.
• 트리를 표현하기에 적합하다.

 

 

1. 스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입 선출(Last-In, First-Out) 방식으로 자료를 처리한다.
• Top : 스택으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소, 스택 포인터라고도 한다.
• Bottom : 스택의 가장 밑 부분이다.

 

스택의 용도

• 부 프로그램 호출 시 복귀주소를 저장할 때
• 함수 호출의 순서 제어
• 인터럽트가 발생하여 복귀주소를 저장할 때
• 후위 표기법(Postfix Notation)으로 표현된 산술직을 연산할 때
• 0 주소 지정방식 명령어의 자료 저장소
• 재귀 프로그램의 순서를 제어한다.

 

 

2. 큐(Queue)

• 선형 리스트의 한 쪽에서는 삽입 작업이 이루어지고 다른 한 쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다.
• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입 선출(First-In, Last-Out) 방식으로 처리한다.
• 시작과 끝을 표시하는 두 개의 포인터를 갖는다.
  
  • 프론트(F, Front) 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 푕ㄴ터로, 삭제 작업을 할 때 사용한다.
  • 리어(R, Rear) 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로, 삽입 작업을 할 때 사용한다.

 

큐를 이용하는 경우

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

운영체제의 작업 스케줄링에 사용한다.

 

 

 

3. 데크(Deque)

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다.
• Double Ended Queue의 약자.
• 스택과 큐의 장점을 합쳐 구성되었다.
• 입력이 한 쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한이 있으며, 그리고 입력은 양쪽에서 일어나고 출력은 한 곳에서만 이루어지는 출력 제한이 있다.
  • 입력 제한 데크 : Scroll
  • 출력 제한 데크 : Shelf

 

 

4. 트리(Tree)

정점(노드-Node)과 선분(가지-Branch)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로 가족의 계보, 연산 수식, 회사 조직 구조도, 히프 등을 표현하기에 적합한 자료 구조이다.