Array 자료구조

Array(배열)

배열이란 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.
배열은 메모리 상에 데이터를 연속으로 배치한 자료구조이다.
배열을 구성하는 각각의 값을 요소(element)라고 한다.
배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.
하나의 요소에는 하나의 타입만 저장할 수 있다.

배열의 시간복잡도

특징

1. 동일한 데이터 유형을 갖고있다.

   • 주로 동일한 데이터 유형을 갖고 있지만 이질적인 데이터도 지원 가능한 프로그래밍 언어가 있다.
   • 이질적 데이터들이 모인 집합체는 주로 레코드라고 한다.

2. 배열의 시간복잡도를 보면 배열의 각 요소에 접근하는 시간은 o(1)로 모두 동일하다.

   • 기본위치 + 오프셋(요소크시 * 인덱스) 연산으로 모든 요소에 접근이 가능하다.

3. 연속된 메모리에 단일 블록화하여 데이터를 저장한다.

   • 낭비되는 공간이 거의 없다.
   • 큰 배열일 경우, 필요한 메모리 할당이 불가능할 수 있다.

4. 매모리 상에서 순차적으로 저장되기 때문에 데이터 순서가 있고, index를 활용하여 indexing 및 slicing이 가능하다.

   • indexing: index를 사용해 특정 요소를 리스트로부터 읽어들이는 것
   • sciling: 요소에 특정 부분을 따로 분리해 조작하는 것

장점

1. 인덱스로 빠르게 접근이 가능하기 때문에 검색이 필요할 경우 용이하다.
2. 공간 낭비가 적다 (기록밀도가 1이다)
3. 간단하고 사용하기 쉽다.

단점

1. 배열을 선언한 후에는 메모리 크기를 변경할 수 없다.
2. 중간에 특정 요소를 삽입 및 삭제하는 경우에는 요소들을 이동시켜야 하기 때문에 어렵다.

배열을 사용하는 경우

1. 순차적으로 데이터를 저장할 경우
2. 다차원 데이터를 다룰 경우
3. 검색이 필요한 경우
4. 삽입 및 삭제가 많이 없는 경우