[자료구조] 배열(Array)이란?

배열(Array)

• 연속된 메모리 공간에 순차적으로 저장된 데이터 모음
• 같은 타입의 데이터를 저장
• 요소(elemnet): 배열을 구성하는 각각의 값
• 인덱스(index): 배열에서의 위치를 가리키는 숫자 (0부터 시작)

 

배열 표현

• 크기가 5인 Int형 배열 array를 선언

swift

var array: [Int] = [1, 2, 3, 4, 5]

python

array = [1, 2, 3, 4, 5]

C

int array[5] = {1, 2, 3, 4, 5};

Java

Int[] array = {1, 2, 3, 4, 5};

 

다차원 배열 (Multidimensional Array)

• index가 2개 이상으로 이루어진 배열
• 다차원 배열은 인덱스를 2개부터 최대 n개까지 만들 수 있음

//2차원
var array: [[Int]] = [[1,2], [2,3], [3,4]]

//3차원
var array: [[[Int]]] = [[[1,2], [3,4]],[[11, 12], [13,14]]]

 

배열의 시간 복잡도

Operation	average case	worst case
read	O(1)	O(1)
insert	O(n)	O(n)
delete	O(n)	O(n)
search	O(n)	O(n)

 

배열의 특징

• 동일한 데이터 타입으로 구성
• 연속된 메모리에 단일 블록화하여 데이터 저장
• 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장
• 데이터에 순서가 있으며, indexing 및 slicing 가능
  • indexing: index를 사용해 특정 요소를 읽어오는 것
  • slicing: 요소에 특정 부분을 분리해 조작하는 것

 

배열의 장점

• index를 이용한 접근이 가능해 모든 요소에 빠르게 접근 가능
• 공간 낭비가 적음
• 간단하고 사용이 쉬움
• 참조를 위한 추가적인 메모리 할당이 필요 없음

 

배열의 단점

• 배열을 선언한 후, 할당된 정적 메모리 때문에 크기를 변경할 수 없음
• 자료의 삽입과 삭제에 비효율적
• 메모리 재사용 불가

 

배열의 사용

• 순차적 데이터를 저장하며, 값보다는  순서가 중요한 경우
• 다차원 데이터를 다루는 경우
• 특정 요소를 빠르게 읽어야 하는 경우
• 데이터 사이즈가 바뀌지 않으며, 요소가 자주 추가되거나 삭제되지 않는 경우