배열이란?

• 연속적인 메모리 위치에 데이터를 저장하는 자료 구조

• 데이터의 순서 유지 가능

• 같은 타입의 데이터를 여러 개 나열한 선형 자료 구조

• 데이터에 빠르게 접근 가능

• 배열의 크기는 고정

  • 데이터가 많아지면 배열을 재할당 해야함

• 선언된 값은 다시 배열을 선언하지 않으면 변경 불가

• 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있음

• 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)

특징

• 추가적으로 소모되는 메모리 양(=overhead)가 거의 없음

• Cache hit rate가 높음

  • cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수)

  • cache hit: 참조하려는 데이터가 캐시에 존재할 떄 캐시 히트

  • cache miss: 참조하려는 데이터가 캐시에 존재하지 않을 때 캐시미스

언제 사용할까?

• 데이터 개수가 확실하게 정해져 있을 때 데이터 저장을 위한 자료구조로 선택하면 좋음

• 삽입/삭제 작업이 적을 때 사용하면 좋음

• 배열에 저장된 데이터를 검색하는 작업이 많을 때( 인덱스로 빠르게 검색 가능)

CRUD에 대해 배열이 어떻게 동작할까?

Create

• 새로운 연속된 공간을 다시 할당받고 기존에 있던 데이터를 모두 새로운 곳으로 옮김

  ex)

int[] arr = new int[5];
arr[0] = 1;
...// 무언가 넣음int[] tmp = new int[6];
for (int i = 0; i < arr.length; i++) {
    tmp[i] = arr[i];
}
arr = tmp;

Read

• 몇번째 데이터라도 덧셈과 곱셈 한번씩이면 접근할 수 있으므로 매우 빠르게 접근 가능

Update

• Read와 마찬가지로 매우 쉽게 접근해서 수정 가능

Delete

• int[] arr = new int[5];에서 arr[3]을 제거하려고 할 때 Create의 예시처럼 new int[4]; 를 만든 후 복사해 넣어야 함

• 공간 자체는 안줄여도 된다고 해도 arr[3]이후의 모든 값을 한칸씩 앞으로 땡겨줘야함

  • 배열의 크기를 사용하는 데이터의 갯수와 관계없이 유지해도 되고 마지막 데이터를 삭제하는 경우라면 한방에 가능

배열의 시간 복잡도

• 데이터 읽기, 수정 : O(1)

• 데이터 추가, 삭제 : O(N)

• 예외 : 배열에 빈 공간이 존재하는걸 허용하며 짜는 경우라면 마지막 데이터의 추가, 삭제는 O(1)