[자료구조] 배열 (Array)

게임 개발에 있어서 자료구조와 알고리즘은 가장 기본적으로 알아야 할 지식이다.
이 중 자료구조의 가장 처음이자 기초적인 배열에 대해 알아보자.

 

배열

배열은 연속된 메모리 공간에 순차적으로 저장되는 데이터들을 말한다.

이는 각각의 값을 구성하는 요소(element)와 그 위치를 가리키는 인덱스(index)로 구성된다.

---

특징

1. 동일한 데이터유형을 가진다.
2. 연속된 메모리를 사용하여 저장하기 때문에 낭비되는 공간이 거의 없다.
3. 데이터의 순서가 있고, 인덱스를 통해 각 요소에 바로 접근할 수 있다.

---

시간복잡도

1. 읽기(read) : 각 요소에 대해 인덱스를 통해서 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가진다.
2. 삽입(insert) 및 삭제(delete) : 길이가 한정적이기 때문에 삽입을 하려면 뒤에 한 칸씩을 밀어야 하고 삭제를 한다고 하면 한 칸씩 당겨야 한다. 그 과정에서 O(n)의 시간 복잡도가 발생한다.
3. 검색(search) : 인덱스를 알고 있다면, 그 인덱스를 이용해 접근하면 되므로 O(1) 이다.
   하지만 알지 못한다면 처음부터 원하는 요소가 어디있는지 탐색해야 한다. 그러므로 O(n)의 시간 복잡도가 발생한다.

---

장점

1. 인덱스를 활용해서 빠른 접근이 가능하다.
2. 공간 낭비가 적다.
3. 간단하다.

단점

1. 정적 메모리를 사용하기 때문에 크기 변경을 할 수 없다.
2. 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제에 많은 비용이 발생한다.