자료구조의 개요 및 종류

나쁜 프로그래머는 코드를 걱정한다. 좋은 프로그래머는 자료구조와 그 관계에 대해 걱정한다.

‘Bad programmers worry about the code. Good programmers worry about data structures and their relationships.’

리눅스의 아버지, 리누스 토발즈(Linus Tovarlds)가 자료구조에 대해 한 말이다. 평생 Data 관리라면 엑셀시트 셀을 추가해 왔던 나인데…. 좋은 프로그래머 근처에라도 가고싶으면 자료구조에 대해 먼저 알아봐야겠다.

개요

Data Structure(자료구조)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 저장을 의미한다. (출처: 위키피디아)

자료와 그 자료를 활용하는 특성에 따라 적절한 Data Structure를 선택해서 사용하게 되는데, 크게 세 가지 종류가 있다.

1. Array-like : ex) Stack, Queue
2. node와 reference로 이루어 진 : ex) Linked List, Trees, Graph
3. data를 저장하고, 위치를 찾는데 hash function에 의존하는 : ex) Hash Table

종류 및 특징

Stack

Stack의 특성을 한 마디로 정리하면, 한쪽 끝에서만 자료를 넣거나 빼는 (Last In, First Out(LIFO) 구조이다. 자료를 넣는 것을 Push라고 하며, 빼는 것을 Pop이라고 하는데, 제일 최근에 Push한 자료부터 Pop할 수 있는 구조라는 것이다. JavaScript의 Call Stack이 그 예라고 할 수 있다. 실생활에서 Stack의 예라면… 이중주차 정도가 될 것 같다. 뒤에 세운 차가 빠지기 전까진 뺄 수 없는..

Queue

Stack과 반대로, Queue는 먼저 넣은 Data가 먼저 나오는 First In, First Out(FIFO) 구조이다. 자료를 넣는 것을 Enqueue, 빼는 것을 Dequeue라고 하며, 자료의 맨 앞, 즉 Dequeue할 수 있는 위치를 Front라고 하며, Enqueue할 수 있는 위치를 Rear라고 한다.

Linked List

Linked List는 앞서살펴본 Stack/Queue와는 다르게, data가 연속된 메모리에 저장되어 있지 않고, node(노드/데이터)와 그것의 reference(링크/연결)로 이루어져 있다. 각 노드는 Data와 next node에 대한 reference로 이루어져 있다. List의 시작을 Head라고 하며, next가 null인 노드가 Tail이 된다. 아래 그림은 한 방향으로 연결되어있는 Single Linked Lsit 구조를 나타낸 것이며, 양 방향으로 연결되어있는 Double Linked List와, 마지막 노드의 Reference가 null이 아니고 Head Node인 Circular Linked List도 있다. Double Linked List는 next node에 대한 reference 뿐만 아니라, previous node에 대한 reference도 가지게 된다.

연결되어있는 노드의 개수를 정해져 있지 않으며(not fixed), 필요에 따라 추가/축소될 수 있다. 다만, 각 data element들에 직접적으로 바로 접근이 불가능 하며, 특정 data element에 접근하기 위해서는 head 부터 시작해서 연결들을 찾아가야하는 단점이 있으며, data와 next node에 대한 reference를 모두 저장해야 하기 때문에 Array-like 형태의 자료구조와 비교하여 메모리를 더 많이 차지한다.

Tree

Tree 구조는 node와 node들을 연결하는 간선(edge)로 구성되어 있다. 각 node는 0개 이상의 child node를 가지지만 각 child node는 단 하나의 parent node를 가진다. 부모가 없는 node를 Root node라고 한다. DOM(Document Object Model)이 Tree 구조를 가진다.

Binary Search Tree(BST)

Tree 각 노드가 최대 2개의 child node만을 가지는 것을 Binary Tree라고 하는데, 이 중, 다음의 특징을 가지는 것을 Binary Search Tree라고 한다.

Graph

Graph 구조에서는 용어가 조금 다르게 사용된다. 앞서 노드라고 불렀던 것을 Vertex(버텍스)라 하며, 엣지를 Arc(아크)라 한다. Tree 구조와는 다르게, Vertex 간 여러개의 Arc가 존재할 수 있는데, Tree 가 Graph의 특수한 형태라고 볼 수 있다.

Directed Graph(방향그래프)와 Undirected Graph(무방향 그래프)가 있으며, 그래프를 코드로 나타내는 방법으로 이차원배열과 연결리스트가 있다. 이차원배열은 공간을 많이 차지(버텍스 수의 제곱)하지만 간단하며, 연결리스트는 공간을 적게 차지(아크 수 * 2)하지만 복잡하다. 즉, vertex의 개수가 적으면 이차원 배열, 크면 연결리스트를 사용하는 것이 효율적이다.!

Hash Table

Hash Table은 key와 value 쌍으로 저장되는데, 저장되는 위치가 Hash Function(해시함수)로 결정된다. Hash Fuction은 key를 hash value로 매핑하는 함수로, hash value는 정수의 index 값이다. 데이터가 저장되는 유한개의 Array-like 저장소를 Bucket이라고 한다. Hash Fuction의 알고리즘이 얼마나 잘 짜여져 있느냐에 따라 Hash Table의 성능이 결정된다. Hash Function은 같은 Key 값에 대해 언제나 동일한 hash value를 반환하며, hash value로 key값을 역추적하는 것은 힘들기 때문에 보안분야에서 많이 쓰이는 자료구조이다.

적은 리소스로 많은 데이터를 효율적으로 관리할 수 있으며, Hash Fuction을 통해 data가 저장된 위치로 바로 접근할 수 있다는 장점이 있다.