[자료구조] 대표적인 자료구조 정리

면접을 보면서 느꼈던 점은 자료구조와 알고리즘은 기본적인 것이라고 생각하는데, 막상 대답하고자 하면 명확하지 않았던 경우가 많았던 것 같다. 이번 기회에 확실히 공부해서 기초를 단단히 해서 보다 논리적으로 문제를 해결하고 싶다. 저번 글에서 자료구조에 대한 전반적인 내용을 다뤘다면, 이번에는 대표적인 자료구조들을 살펴보고 각각의 장단점과 특징을 비교해보자. 

 

배열 (Array)

 배열은 가장 기본적인 데이터 구조다. 배열은 인덱스(Index)와 인덱스에 해당하는 요소(Element)로 구성된다.

특징

1. 길이가 고정되어 생성된다. (정적 메모리 할당)
2. Random Access를 지원한다. 즉, 인덱스를 통해서 각 요소에 직접 접근할 수 있는 특징이 있다.
3. 배열은 논리적 순서와 물리적 순서가 일치한다. 인접한 메모리 위치에 연이어 저장된다. 

시간 복잡도

1. 검색 (Search) : 요소마다 인덱스를 부여했기 때문에, 특정 요소를 접근하는 시간 복잡도는 O(1)이다.  하지만, 인덱스를 모르는 특정 값을 찾기 위해서는 배열의 모든 요소들을 살펴봐야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
2. 추가/삭제 (Insert/Delete) : 삽입이나 삭제를 하기 위해서는 길이가 고정되어 있기 때문에 차례대로 한 칸씩 밀어야 하는 과정이 필요하고 그 과정에서 O(n)의 시간 복잡도가 생긴다. 

 

연결 리스트 (Linked List)

 배열의 추가/삭제 연산에 대한 비효율성을 극복하고자 등장한 데이터 구조이다. 각 요소는 다음 노드 연결에 대한 정보를 담은 포인터 또는 주소와 함께 노드에 저장된다. 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등의 종류가 있다. 

특징

1. 새로운 요소가 추가될 때 런타임에 메모리를 할당한다. (동적 메모리 할당)
2. Sequential Access를 지원한다. 요소에 접근할 때 순차적으로 접근해야 하는 특징이 있다. 
3. 인덱스나 위치와 같은 물리적 배치를 사용하지 않고 참조 시스템(다음 노드 연결에 대한 포인터 또는 주소)을 사용한다. 

시간 복잡도

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 동적인 메모리 크기를 갖기 때문에, 새로운 요소를 추가하거나 삭제할 경우에 해당되는 부분만 변경하면 되기 때문에 O(1)의 시간 복잡도를 갖는다.

 

Array와 Linked List의 차이는 무엇일까?
 
 데이터의 접근의 경우 Array는 Random Access를 그리고 Linked List는 Sequential Access를 지원한다. 따라서, 특정 요소에 접근하는 경우 Array는 직접 접근할 수 있어 효율적이고, Linked List는 처음부터 순차적으로 접근해야 해서 비효율적이다.
 반면에 데이터의 추가/삭제 Array의 경우 크기가 고정되어 있어서, 추가 및 삭제를 위해서는 다른 요소들의 주소도 전부 변경해야 하기 때문에 비효율적인데, Linked List의 경우 추가 및 삭제 시 해당되는 요소의 메모리 주소만 변경하면 되기 때문에 보다 효율적이다.
 그리고 메모리 할당에서도 차이가 나는데 Array는 선언 시 요소들을 인접한 메모리 위치에 연이어 저장하고 크기가 고정되어 있는 정적 메모리 할당, Linked List의 경우 새로운 요소가 추가되면 메모리를 할당하고 그 정보를 저장하는 동적 메모리 할당.

 

스택 (Stack)

 순서가 보존되는 선형 자료구조의 일종으로, LIFO(Last In First Out) 메커니즘을 갖고 있다.

특징

1. 데이터를 받는 순서대로 정렬한다.
2. LIFO, 마지막으로 입력된 것을 순차적으로 가져오는 방법을 갖고 있는 것이 특징이다. (FILO도 동일한 의미다)
3. 동적 메모리

시간 복잡도

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 가장 위에 데이터를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.

 

큐 (Queue)

 순서가 보존되는 선형 자료구조의 일종으로, FIFO(First In First Out) 메커니즘을 갖고 있다.

특징

1. 데이터를 받는 순서대로 정렬한다.
2. FIFO, 가장 먼저 입력된 것을 순차적으로 가져오는 방법을 갖고 있는 것이 특징이다.
3. 동적 메모리

시간 복잡도

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 가장 위에 데이터를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.

 

Stack과 Queue의 차이는 무엇일까?


 두 자료구조 모두 순서가 보존되는 선형 자료구조의 일종이며, 동시에 Push와 Pop과 같은 핵심적인 기능만 알면 되는 추상적 자료구조이기도 하다. 가장 큰 차이점은 처리하는 순서에 있는데, Stack은 가징 마지막으로 입력된 것부터 Queue는 가장 먼저 입력된 것부터 처리하는 메커니즘을 갖는다. 이러한 특징으로 Stack은 DFS나 재귀에 자주 사용되고, Queue는 BFS나 캐시를 구현할 때 사용된다. 

 

해시 테이블 (Hash Table)

 해시 테이블은 키(Key)와 값(Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 검색이 필요할 때 용이하다. 해시 테이블을 구현하기 위해서는 연결 리스트와 해시 함수(Hash Function)가 필요하다. 해싱(Hashing)은 해시 함수를 통해서 임의의 값을 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 입력받아서 해시 함수를 통해 얻은 해시(Hash)를 배열의 인덱스로 환산해서 값에 접근하는 것을 의미한다.

특징

1. 키 값을 배열의 인덱스로 사용하기 때문에, 값을 직접 접근할 수 있다. 따라서, 해시 테이블의 평균 시간 복잡도는 O(1)이다.(운이 없어, 충돌(Collision)이 일어나는 경우 O(n))
2. 충돌이 발생할 수 있다. 이 경우 분리 연결법(Separate Chainging) 혹은 개방 주소법(Open Address)을 사용하여 해결한다.
3. 데이터가 저장되기 이전에 미리 공간을 만들어야한다. 공간 복잡도가 크다.
4. 해시 함수를 통해서 배열 인덱스의 범위를 조절할 수 있다. 이를 리사이징(Resizing)이라고 한다. 
5. 키와 해시의 연관성이 없어 보안에도 자주 사용된다. 

충돌 해결방법은 무엇이 있을까?

(1) Separate Chaning :  Linked List 혹은 Tree를 사용하는 방법이다. 충돌이 발생하는 경우 인덱스가 가리키고 있는 값에 노드를 추가하여 값을 추가한다. 대신, 두 방법 모두 많이 추가하면 비효율적이다. 
(2) Open Address : 해시 테이블의 빈공간을 사용하는 방법이다. 추가적인 메모리 공간을 필요하지 않은 장점이 있다. 그 방법에는 Linear Probing, Quandratic Probing, Double Hasing 등이 있다. 

 

그래프 (Graph)

 그래프는 비선형 자료구조로, 노드(Node)/정점(Vertice)과 이들 사이를 연결하는 엣지(Edge)로 구성된 자료구조를 의미한다. 

특징

1. 그래프는 방향이 있을 수도(Directed) 없을 수도(Undirected) 있다.
2. 다양한 구조로 설계된다. 구조에 따라서 시간 복잡도가 달라지고 다양하게 응용이 가능하다. 
3. 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
4. 시간 복잡도/공간 복잡도를 이야기할때 노드(N)/정점(V)과 엣지(E)의 수를 사용하여 표현한다.

시간 복잡도

1. 두 노드의 연결 확인 : 인접 행렬의 경우 고유 인덱스로 바로 접근 가능하여 O(1)의 시간 복잡도를 갖는다. 인접 리스트의 경우 한  노드의 인접 리스트 안의 특정 노드가 있는지 확인해야 하기 때문에, 최악의 경우 전체를 봐야하므로 O(N)/O(V)의 시간 복잡도를 갖는다. 
2. 한 노드에 연결된 모든 노드 확인 : 인접 행렬의 경우 특정 노드를 나타내는 행렬을 돌아서 연결된 노드를 가져와야 하기 때문에, O(N)/O(V)의 시간 복잡도를 갖는다. 인접 리스트의 경우 연결된 노드의 갯수는 곧 엣지의 갯수이므로, 엣지의 갯수만 확인하면 되므로 O(E)의 시간 복잡도를 갖는다.   
3. 추가/삭제 (Insert/Delete) : 추가의 경우 노드/정점이나 엣지 모두 O(1)의 시간 복잡도를 갖는다. 하지만, 삭제의 경우에는 노드/정점의 경우 특정 노드/정점을 찾는 시간과 그와 연결된 엣지를 삭제해야 하므로 O(N+E)/O(V+E)의 시간 복잡도를 갖는다. 엣지의 경우 특정 엣지를 찾는 시간이 소요되므로 O(E)의 시간 복잡드를 갖는다.   

 

트리 (Tree)

 트리는 비선형 자료구조로, 노드로 구성된 계층적 자료구조이다. 최상위 노드(Root)를 만들고, 부모(Parent) 노드에 자식(Child) 노드를 추가하고 그리고 그 자식 노드가 부모 노드로써 또 다른 자식 노드를 추가하는 구조를 가지고 있다. 

특징

1. 트리에 또 다른 트리가 있는 재귀적 자료구조이다.
2. 데이터를 순차적으로 저장하지 않는, 비선형 자료구조이다.
3. 이진트리(Binary Tree), 이진탐색트리(BST, Binary Search Tree), 균형트리(B-Tree, Balanced Tree), 힙트리(Heap Tree) 등 다양한 종류가 존재한다. 

 

---

Reference

1. 자료구조 시각화 : https://www.cs.usfca.edu/~galles/visualization/Algorithms.html