[자료구조] Array(배열) - 정의, 예제, 시간복잡도, 장단점

# 자료 구조 시리즈

1. Array (배열)
2. Linked List (연결 리스트)
3. Stack
4. Queue
5. Tree (Binary / Segment)
6. Graph
7. Deque
8. Heap & Priority Queue
9. Trie

 

자료구조(Data Structure)에서는 자료에 효율적으로 접근하고 수정할 수 있도록, 데이터를 구성하고 저장하는 방법을 공부합니다. 자료구조는 데이터의 형태에 따라 크게 선형과 비선형으로 구분됩니다. 선형 자료구조는 데이터가 일렬로 나열되어 있는 반면, 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다는 것이 핵심입니다. 전자의 예시로는 Array, Linked List, Stack, Queue 등이 있으며 후자에는 Tree, Graph 등이 있습니다.

 

 

Array (배열)

---

1. 정의

  Array(배열)은 연속된 메모리 공간에 순차적으로 저장된, 동일한 type의 데이터 모음입니다. 아래는 Java 코드로 정의하고 생성한 Array 객체입니다.

// Java

/* Declaring Arrays */
int[] arrayOfInt;
String[] arrayOfString;

/* Creating Arrays */
arrayOfInt = new Int[100];
arrayOfString = new String[10];

/* Initializing Arrays */
for (int i = 0; i < arrayOfInt.length; i++) {
    arrayOfInt[i] = i;
}
arrayOfString = new String[]{"hello", "world"};
String[] name = {"Stacy", "Tracy", "Dorothy"};

 

// Kotlin

fun main() {
    var arr = Array<Int>(3, {0})
    var arr = IntArray(3)
    arr[1] = 1
    arr[2] = 2
    
    arr.forEach { println(it) }
}

 

  다른 type의 데이터들이 모인 집합체는 'record' 또는 'heterogeneous array'라고도 합니다. type에 엄격한 정적(static) 언어인 C, C++, Java와 달리 JavaScript나 Python과 같은 동적(dynamic) 언어에서는 아래처럼 array 내부에 Integer, String, Double, Boolean type의 데이터를 정의할 수 있습니다. (참고로 C에서는 'union'이라는 자료구조가 존재하여 python의 heterogeneous array처럼 표현할 수 있습니다.)

# python
my_array = [1, "hello", 3.14, True]

 

  선언할 때 배열의 크기를 고정하고, 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다는 것도 Array의 특징입니다. 이해를 돕기 위해 아래 그림을 살펴보면, 연속된 메모리 공간에 데이터들이 address 및 index와 함께 순차적으로 저장되어 있는 것을 알 수 있습니다. address(주소)의 컴퓨터 공학적인 정의는 메모리 상 데이터의 위치로, Array 생성 시 element들은 연속된 메모리 위치에 저장되고, 각 element는 접근할 수 있는 고유한 address를 갖게 됩니다. element를 꺼내기 위해서는 index를 통해야 합니다. my_arrary 내 element인 3.14에 접근하려면 우리는 index 2를 사용하여 my_array[2]로 호출할 수 있습니다. index와 array의 크기를 통해 address를 계산할 수 있을 뿐, index와 address는 동일한 개념이 아닙니다.

https://www.simplilearn.com/tutorials/data-structure-tutorial/arrays-in-data-structure

 

반응형

---

2. Array의 시간 복잡도 (Time Complexity)

  앞에서 설명했듯, Array는 index를 통해 element에 접근할 수 있습니다. 시간복잡도 상에서 index에 접근하는 것은 상수 시간(constant time)만큼 걸리기 때문에 Array 조회 시의 시간복잡도는 O(1)입니다. 만약 Array에 데이터를 삽입/삭제한다면 기존 index로 할당된 element들을 왼쪽 또는 오른쪽으로 재배치(shift)할 필요가 있으므로 시간복잡도는 O(n)입니다.  곧 다룰 Linked List와 비교한 Array의 시간 복잡도를 케이스별로 나타낸 표입니다.

https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

---

3. Array의 장단점

  (1) 장점

1. index를 이용한 접근이 가능하여 모든 element에 빠르게 접근할 수 있습니다. (최대 시간복잡도 O(n))

2. 참조를 위한 추가적인 메모리가 필요하지 않습니다.
(데이터 외에 pointer 등의 부가 정보가 필요한 List, Graph와 달리 Array는 데이터만 저장하기 때문에 기록밀도가 1입니다.)

3. 연속된 메모리 공간에 element들을 순차적으로 저장하기 때문에 메모리 관리가 편합니다.

 

  (2) 단점

1. Array 정의 시 정적 메모리를 할당하기 때문에 Array의 크기를 변경할 수 없습니다. 크기를 변경하려면 새로운 Array를 만들어 기존 데이터를 옮겨야 하는 수고로움을 감수해야 합니다.

2. 사용하지 않는 주소에 대해서도 메모리를 필요로 하기 때문에 메모리 낭비가 발생될 우려가 있습니다. 삽입/삭제가 빈번하게 발생하는 상황에서 빈 공간을 미리 결정하는 것은 사실상 불가능에 가깝고, Overflow나 공간 낭비를 초래할 수도 있습니다.

 

  (3) Array를 언제 사용하면 좋을까?

  데이터 개수가 확실하게 정해져 있을 때는 데이터 저장을 위해 Array를 자료구조로 선택하면 좋습니다. (알고리즘 문제에서 메모리 공간의 크기를 알 수 있도록 데이터의 개수 N을 준다면 Linked List보다는 Array) 다만, 삽입과 삭제 작업이 많다면 O(n)만큼의 시간복잡도가 삽입/삭제 시마다 추가되기 때문에 데이터를 검색하는 작업이 많은 경우 index의 장점을 십분 살려 Array를 사용하시는 것을 추천합니다.

 

 

---

참고자료
 - https://yoongrammer.tistory.com/43
 - https://gitub.com/Seogeurim/CS-study

 

[Kubernetes] CKA(Certified Kubernetes Administration) 자격증 후기/접수 방법/출제 범위/할인바우처 (+CKAD, CKS

[인공지능] 생성 모델 (Generative AI Model)이란? (1) : AutoEncoder, VAE, GAN

[GitHub] 깃허브 잔디 심는 법 - GitHub Contributions