자료 구조는 알고리즘의 선택과 효율에 영향을 미치기 때문에 필수적으로 알고 있어야 할 것이다. 이번 글에서는 자료 구조에 관한 전반적인 overview 를 해 볼 것이다.
Contents
- Array
- Linked list
01. Array
A data structure consisting of a collection of elements, of same memory size, each identified by at least one array index or key.
배열이라고 하는 array 는 같은 타입들의 변수로 이루어진 집합으로, 메모리의 연속 공간에 값이 채워진 형태이다.
| Pros | Cons |
|---|---|
| 원소 접근 및 데이터 참조 용이 | 비효율적 메모리 활용과 수정 |
Array 는 index 를 이용해 element 에 바로 접근이 가능하며 (i.e., O(1)), 읽기 또는 쓰기 등 참조에 용이하다. 하지만 초기에 선언된 사이즈만큼 메모리의 연속 공간이 필요하므로 몇몇 빈 공간들이 낭비되는 문제점이 있다.
02. Linked list
앞서 설명한 array 의 단점을 보완하기 위해 linked list 는 데이터를 분산해서 저장 및 연결을 실행한다. 따라서, array 의 장점과 단점이 linked list 에서는 단점과 장점이 된다.
A linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
| Pros | Cons |
|---|---|
| 효율적 메모리 활용과 수정 | 비효율적 원소 접근 및 데이터 참조 |
이러한 linked list 는 선언 시 크기를 지정하지 않고 각 요소들을 분산해서 메모리에 저장하되, 주소로 데이터들을 연결하기 때문에 연속된 공간이 필요하지 않다는 장점이 있다. Thus, it can grow or shrink dynamically. 또한 이러한 이유로 node 는 다음의 두 segments 를 포함해야 한다: data and address.
