[자료구조] 자료구조의 선형, 비선형 분류에 따른 각 종류와 자료구조별 특징 간단 정리

프로그래밍을 하다보면 각 특징에 맞게 효율적으로 데이터를 담는 자료구조가 존재한다.

이 포스팅은 다양한 자료구조의 종류와 각 특징의 간단 정리를 하는 글이다.

---

- 자료구조의 분류

자료구조는 크게 두 분류로 나뉘어진다. 바로 선형구조와 비선형 구조이다.

 ■ 선형구조 : 선형 리스트(배열), 연결 리스트, 스택, 큐, 데크

 ■ 비선형구조 : 트리, 그래프

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

비선형구조란? 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태를 의미한다.

그림으로 보면 더 이해하기가 쉬울 것이다.

선형구조는 아래와 같이 1부터 4까지 순차적으로 원소를 나열시키는 형태이며,

비선형구조는 아래와 같이 하나의 자료인 Root가 있고 그 아래에 여러개의 원소를 나열시킨 형태이다.

---

- 배열

배열은 인덱스를 가지고 있으며, 순차적으로 데이터가 삽입 삭제될 수 있는 형태의 자료구조이다. 

또한 데이터를 순차적으로 삽입 삭제할때 가장 효과적이다.

장점	단점
인덱스를 사용하기 때문에 검색이 빠르다.	중간에 삽입 삭제가 어렵다.

- 연결 리스트

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

연결을 위한 포인터 부분이 필요하기 때문에 순차 리스트, 배열에 비해 기억공간 이용 효율이 좋지는 않다.

또한 연결 리스트 중 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들지만, 노드의 연결이 끊어지지만 않는다면 중간에 삽입 삭제가 용이하다.

장점	단점
중간 삽입 삭제가 빠르고 용이하다.	검색 속도, 접근 속도가 느리다.

- 스택(Stack)

스택은 리스트의 한 쪽 끝으로만 자료를 삽입, 삭제 작업이 이루어 진다.

스택의 특징은 가장 마지막으로 들어온 데이터부터 빠져나가는 후입선출(LIFO) 형식이며,

- 스택의 가장 마지막 삽입 위치를 가리키는 TOP/SP(StackPointer)

- 스택의 가장 밑 바닥을 나타내는 Bottom

- 스택의 자료 입력 명령어인 PUSH

- 스택의 자료 출력 명령어인 POP이 있다.

스택의 쓰임새를 알려면 프로그램이 운영체제로부터 할당받는 메모리공간을 알 필요가 있다.

- 코드(code) 영역 - 데이터(DATA) 영역 - 스택(Stack) 영역 - 힙(Heap) 영역.

여기서 스택은 '스택 메모리'라 불리며 지역 변수와 매개변수를 담고 있으며 컴파일 타임에 크기가 결정된다.

스택의 용도는 대략 7가지 정도가 있다.

부 프로그램 호출 시 복귀주소를 저장할 때	함수 호출의 순서 제어
인터럽트가 발생하여 복귀주소를 저장할 때	후위 표기법으로 표현된 산술식을 연산할 때
0 주소지정방식 명령어의 자료 저장소	재귀 프로그램의 순서 제어  * 재귀 프로그램이란, 한 루틴이 자기를 다시 호출하여 실행하는 프로그램을 일컫는다.
컴파일러를 이용한 언어 변역 시

- 큐(Queue)

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

가장 먼저 삽입된 자료가 가장 먼저 출력되는 선입선출(FIFO) 방식으로 처리한다.

- 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터로 삭제 작업이 이루어지는 Front 포인터

- 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로 삽입 작업이 이루어지는 Rear 포인터

Queue는 순서를 기다리는 대기 행렬 처리에 사용되거나 운영체제의 작업 스케쥴링에 사용된다.

- 데크(Deque, Double Ended Queue)

데크는 Stack과 Queue의 장점을 빼서 따로 구성된 자료구조로, 삽입 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.

- 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과, (입력 제한 데크 : Scroll)

- 입력은 양쪽에서 일어나고 출력은 한쪽에서만 이루어지는 출력 제한이 있다. (출력 제한 데크 : Shelf)

- 트리(Tree) 

트리틑 정점(Node)과 선분(Branch)을 이용하여 사이클로 이루어 지지 않도록 구성된 그래프의 특수한 형태이다.

트리는 계층 모델로 노드가 N개인 트리는 항상 N-1개의 가지를 갖는다.

또한 루트에서 어떤 노드로 가는 경로는 유일하다. 트리의 순회는 Pre-Order, In-Order, Post-Order로 이루어진다.

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

- 가지(Branch, Edge) : 노드와 노드를 연결하는 간선

- Root Node : 트리의 맨 위에 있는 노드이다. 위 예시에는 1 이다

- 차수, Degree : 각 노드에서 뻗어나온 가지의 수이다. 위 예시에는 1의 차수 = 2 / 2의 차수 =  2 / 4의 차수 = 1이다

- 트리의 차수 : 노드들의 차수 중에서 가장 많은 수를 의미한다. 위 예시에는 2이다.

- 단말 노드(Terminal Node = Leaf Node) : 자식이 하나도 없는 노드이다. 이 단말 노드의 차수는 0이다. 
위 예시에는 5, 6, 7, 8이 단말노드이다.

- 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드이다. 위 예시에는 1, 2, 3, 4가 비단말 노드이다.

- 자식노드(Children Node) : 어떤 노드에 연결된 다음 레벨의 노드들을 의미한다. 만약 위 예시에서 2의 자식 노드는 4와 5가 된다.

- 부모노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드이다. 위 예시에서 8의 부모 노드는 4가 된다.

- 형제노드(Sibling) : 동일한 부모를 갖는 노드들을 의미한다. 위 예시에서 7의 형제노드는 7이 된다.

- Level : 루트 노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식 노드는 L+1이다.

- 깊이(Depth, Height) : 어떤 트리에서 노드가 가질 수 있는 최대의 레벨을 의미한다. 위 예시에서 깊이는 4이다.

트리의 종류에는 일반 트리, 이진 트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 균형 트리 등으로 되어 있다.

이진 트리(Binary Tree)	각 노드가 최대 두 개의 자식을 갖는 트리이다. 모든 트리가 이진 트리는 아니다. 이진 트리의 순회는 중위 순회(left -> 현재 -> right), 전위 순회(현재 -> left -> right), 후위 순회(left -> right -> 현재)가 있다. 이진 탐색 트리는, 모든 노드가 모든 왼쪽 자식들 <= n <= 모든 오른쪽 자식들의 특정 순서를 따르는 이진 트리이다.
완전 이진트리(Complete BT)	마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다.
균형 이진트리(Full Binary Tree)	모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
포화 이진트리(Perfect Binary Tree)	균형 이진트리이면서 완전 이진트리로, 모든 단말노드는 같은 높이에 있어야 하며, 모든 내부 노드가 두 개의 자식노드를 갖는다.
균형 트리(B-Tree)	레드블랙트리, AVL트리가 이 일종이며, 시간 복잡도 O(logN)에 삽입, 찾기 등을 무리없이 가능한 균형 잡힌 트리이다.

트리의 쓰임새는 다양한데, 정렬에서 Heap정렬 등에 쓰이는 최소 힙(부모노드 <= 자식노드, 오른차순)과 최대 힙(부모노드 >= 자식노드, 내림차순)또한 완전 트리구조로 되어 있다.

- 그래프(Graph)

그래프는 단순히 노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.

우리가 평소에 보는 지하철 노선도가 그래프 형태로 되어 있다.

그래프는 노드와 다르게 루트 노드 개념과 부모-자식 관계의 개념이 없다. 2개 이상의 경로가 가능하며, 순회는 DFS와 BFS로 이루어진다.

간선의 유무는 그래프에 따라 다르며 간선에 따라 Weight 가중치를 매길 수 있다.

- 정점(Vertex, Node) : 데이터의 위치를 나타내는 개념이다.

- 간선(Edge, Branch) : 노드를 연결하는 선이다.

- 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점이다.

- 노드의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수이다. 

- 진입 차수(in-Degree) : 방향 그래프에서 외부에서 오는 간선의 수이다.

- 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수이다.

- 경로의 길이 : 경로를 구성하는데 사용된 간선의 수이다.

- 단순 경로 : 경로 중에서 반복되는 정점이 없는 경우를 의미한다.

그래프의 종류는 크게 무방향 그래프와 방향 그래프, 가중치 그래프, 연결그래프와 비연결그래프, 순환 그래프와 비순환 그래프, 완전 그래프 등으로 구성되어 있다.

이를 구분하기 위해서는 오일러 경로(Eulerian Tour)의 개념을 알고 있어야 한다.

오일러 경로란, 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점(Vertex)으로 되돌아오는 경로를 의미한다. 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

가중치 그래프(=Network)	간선에 비용이나 가중치가 할당된 그래프이다.
무방향 그래프	무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다. 정점 A와 정점 B를 연결하는 간선은 (A, B) 혹은 (B, A)와 같이 정점의 쌍으로 표현한다.
방향 그래프	간선에 방향성이 존재하는 그래프이다. A->B로만 갈 수 있는 간선은 <A, B>로 표시한다. 무방향 그래프와 다르게 <B, A>로 나타낼 수 없다. 즉, <A, B> <B, A>는 다른 의미다.
비연결 그래프	무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다.
연결 그래프	무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우이며 트리가 이에 해당된다.
비순환 그래프	사이클이 없는 그래프이다.
순환 그래프	단순 경로의 시작 정점과 종료 정점이 동일한 그래프이다.
완전 그래프	그래프에 속해 있는 모든 정점이 서로 연결 되어 있는 그래프이다. (무방향 완전 그래프의 정점 수(n)일 때 간선의 수를 구하는 공식 = n * (n - 1) / 2)