[DataStructure] 1. 자료구조 기본 - Array, Linked List, Stack, Queue, Tree

1. 자료구조 기본 - 기본적인 자료구조 종류

선형 자료 구조

Array vs Linked List

가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access가 가능하다는 장점이 있는 것이다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤<Big-O(1)>, 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 cost가 발생한다<Big-O(n)>. Array 자료구조에서 삭제 기능에 대한 time complexity의 worst case는 Big-O(n)이 된다. 삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

이 부분에 대한 문제점을 해결하기 위한 자료구조가 linked list이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 고쳐주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것이다. 하지만 linked list 역시 한 가지 문제가 있다. 바로 Searching 과정에 있어서 첫번째 원소부터 하나하나 다 확인해봐야 한다는 것이다. 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다. 결국 linked list 자료구조는 searching에도  O(n)의 time complexity를 갖고, 삽입, 삭제에 대해서도  O(n)의 time complexity를 갖는다. 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List는 Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.

Stack vs Queue

Stack 자료구조는 Last In First Out ( LIFO ) 나중에 들어간 놈이 먼저 나온다. Stack의 특징이다. 차곡차곡 쌓이는 구조로 먼저 stack에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.

 Queue 자료구조는 First In First Out ( FIFO ) 먼저 들어간 놈이 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다. 

비선형 자료구조

Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierachical Relationship)을 표현하는 자료구조이다. 이 트리라는 자료구조는 표현에 집중한다. 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보자.

트리를 구성하고 있는 구성요소들

Node (노드) :: 트리를 구성하고 있는 각각의 요소를 의미한다.

Edge (간선) :: 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.

Root Node (루트 노드) :: 트리 구조에서 최상위에 있는 노드를 의미한다.

Terminal Node ( = leaf Node, 단말 노드) :: 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.

Internal Node (내부노드, 비단말 노드) :: 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

- Binary Tree (이진 트리)

Definition)

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다. 재귀적인 정의라 맞는듯 하면서도 이해가 쉽지 않을 듯하다. 한 가지 덧붙이자면 공집합도 이진 트리로 포함시켜야 한다. 그래야 재귀적으로 조건을 확인해갔을 때, leaf node에 다 달았을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 ‘Level(레벨)’이라고 한다. 레벨의 값은 0부터 시작하고 따라서 루트 노트의 레벨은 0이다. 그리고 트리의 최고 레벨을 가리켜 ‘height(높이)’라고 한다.

- - Full Binary Tree (포화 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.

- - Complete Binary Tree (완전 이진 트리)

위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.

end