[자료구조] Array

정의

• Array는 메모리 상에 같은 종류의 데이터를 연속적으로 배치한 자료구조이다.
• 크기가 정해져 있고, 변경할 수 없는 정적(Static)인 자료구조이다.

특징

• 배열의 크기는 생성하면서 정해지고 변경이 불가능하다.
  • 연속적인 공간에 저장을 해야하는데, 이후 공간 사용이 가능한지 알 수 없기 때문이다.
  • 미리 크기가 정해져 있기 때문에, 추가적으로 소모되는 메모리 양이 거의 없다.
  • 배열을 생성하려면 메모리 상에 연속한 구간을 할당해야 해서 할당에 제약이 걸릴 수 있다.
• 배열은 값에 대한 유일무이한 식별자인 인덱스를 가지고 있기 때문에, 인덱스를 이용해서 데이터에 접근이 가능하다.
  • 논리적인 저장 순서(인덱스)와 물리적인 저장 순서(메모리 주소)가 일치하기 때문에 인덱스 로 접근하여 사용이 가능하다.
  • 찾고자 하는 값의 인덱스를 안다면 O(1)에 접근이 가능하다. 즉 random access가 가능하다.
• 데이터에 대한 인덱스 값이 고정되어 있어야 하므로, 데이터가 삭제되면 빈 공간으로 남겨두어야 하기 때문에 메모리가 낭비된다.
  • 혹은, 배열을 연속적인 특징을 유지하기 위해서 shift를 진행한다면 O(N)의 cost가 발생하게 된다.
• 연속된 메모리 공간에 할당하므로 순차탐색이 가장 빠른 자료구조이며, 캐시 지역성을 활용하여 cache hit rate가 높다.

장점

• 인덱스(index)를 통해서 원소에 빠르게 접근이 가능하다.

단점

• 생성 후에는 크기 변경이 불가능하다.
• 임의의 위치에 원소를 추가하고 삭제하는데 오래 걸린다.
• 연속된 메모리 상에 존재하므로, 처음에 선언한 크기만큼 사용하지 않는다면 메모리가 낭비된다.

언제 사용해야 할까?

• 데이터의 개수가 확실히 정해져 있는 데이터의 저장을 위해 사용한다.
• 삽입/삭제가 빈번히 일어나지 않는 경우에 쓰인다.
• 데이터의 검색이 많은 경우에 사용된다.

in Kotlin

val stringArray = arrayOf("A", "B", "C")
// primitive type Array 생성
// ByteArray, ShortArray, IntArray, DoubleArray, CharArray, BooleanArray
// String type은 
val intArray = inArrayOf(1, 2, 3, 4, 5)

// Array의 크기 만큼 값을 지정하면 null로 초기화된다.
val arrayOfNulls = arrayOfNulls<Int>(5)
// 크기가 0인 Array 생성
val emptyArray : Array<Int> = emptyArray()

// 생성자를 통한 생성
val arrayLambda = Array(5) { index -> index }