[정보처리기사] 데이터베이스-선형 비선형

자료구조란 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문입니다. 즉, 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미합니다.

 

자료구조는 정렬을 하거나 검색을 할 때, 인덱스 처리를 하거나 파일편성을 할 때 이용됩니다. 이번 포스팅에서는 선형구조화 비선형구조에 대하여 알아보도록 하겠습니다.

 

 

자료구조는 선형구조와 비선형구조로 구분됩니다. 먼저 선형구조에 대하여 설명한 후 비선형구조에 대하여 설명하도록 하겠습니다.

 

선형구조란 자료를 구성하는 원소들은 순차적으로 나열시킨 형태를 의미합니다. 어떤 연산들을 수행할 수 있느냐에 따라 다시 세부적으로 분류 할 수 있습니다.

 

리스트에 대하여 먼저 설명하도록 하겠습니다. 리스트는 다시 선형리스트와 연결리스트로 구분됩니다.

선형리스트란 배열과 같이 연속되는 기억 장소에 저장되는 리스트입니다. 특징으로는 구조가 간단하다는 것, 기억장소 이용 효율이 높다는 것, 삽입/삭제에 어려움이 있다는 것, 연결리스트와 비교하여 검색이 빠르다는 것 등이 있습니다.

 

연결리스트란 노드의 포인터 부분으로 서로 연결시킨 리스트입니다. 특징으로는 기억장소 이용 효율이 낮다는 것, 삽입/삭제가 용이하다는 것, 순차 리스트에 비교하여 검색이 느리다는 것, 포인터를 위한 추가 공간이 필요하다는 것 등이 있습니다.

 

선형구조 중 스택에 대하여 설명하도록 하겠습니다. 스택이란 삽입/삭제가 한 방향에서 이루어지는 데이터 구조입니다. LIFO(Last In First Out)라 불리며 인터럽트의 처리나 수식의 계산, 서브루틴의 복귀번지 저장, 부프로그램 호출 등에 사용됩니다.

Top Point라는 개념을 사용하는데 Top Pointer는 가장 최근에 삽입된자료 또는 가장 먼저 삭제될 자료를 가리키는 스택 포인터를 의미합니다. 삽입시 Top의 값이 증가하며 삭제시 Top의 값이 감소합니다.

 

이번에는 선형구조 중 큐에 대하여 설명하도록 하겠습니다. 큐란 리스트의 한 방향에서 삽입작업이, 반대편 방향에서는 제거 작업이 이루어지는 데이터 구조입니다. FIFO(First In First Out)라 불리며 운영체제의 작업 스케줄링, 키보드 버퍼 이용, 스플 등에 사용됩니다.

 

Head와 Tail이라는 개념을 사용하는데 Tail -> Head로 작업이 이루어지는 특징을 갖습니다.

 

이번에는 선형구조 중 데크에 대하여 설명하도록 하겠습니다. 데크란 삽입과 삭제가 리스트의 양쪽 끝에서 발생할 수 있는 자료구조입니다.

 

큐와의 차이점은 단방향이 아닌 양방향이라는 것입니다.

 

 

이번에는 비선형구조에 대하여 설명하도록 하겠습니다. 비선형구조에는 트리와 그래프가 있습니다.  

 

트리란 노드와 간선으로 구성되어져 있고, 사이클이 없는 구조를 의미합니다. 용어에는 노드(Node), 근노드(Root Node), 노드의 차수(Degree), 트리의 차수, 단말노드(Leaf), 노드의 깊이(Level) 등의 용어가 있습니다.

트리의 종류에는 이진트리(차수가 2이하로 구성된 트리: 최대 노드의 수는 2의 n승 -1)와스레드 이진트리(기억 공간의 낭비 원인이 되는 널 링크 부분을 트리 순회시 이용되도록 구성), B-트리(인덱스 파일에서 인덱스를 구성하는 방법 중의 하나) 등이 있습니다. 이진트리의 순회방법에 대해서만 간략하게 설명하고 넘어가도록 하겠습니다. 순회방법이란 트리를 구성하는 노드들을 찾아가는 방법으로 Root를 찾는 순서가 어떻게 되느냐에 따라 전위순회(Root->왼->오), 중위순회(왼->Root->오), 후위순회(왼->오->Root)로 나뉘어집니다. 위의 그림에서는 전위순회(A,B,D,E,C,F,G), 중위순회(D,B,E,A,F,C,G), 후위순회(D,E,B,F,G,C,A)로 구성되게 됩니다. 

 

그래프에 대하여 설명하도록 하겠습니다. 그래프란 노드와 간선으로 구성되어져 있으며 사이클이 존재하는 비선형구조 자료구조입니다.

표시하는 방법은 그림이나 표로 합니다. 표의 경우에는 예를 들자면 1행2열에서 A에서 B로 향하는 것이 있기 때문에 1로 표시합니다.