배열

배열이란?

배열은 연관된 데이터를 모아서 관리하기 위한 자료 구조이다.

 

생성 원리

int[] intArr = new int[5];	// x100 <- 할당받은 메모리 주소값

 

자바에서 배열은, heap 메모리 영역에 생성된다.

배열 생성 후, 할당받은 메모리의 주소값을 변수에 담아 활용하게 된다.

 

 

이렇게 생성된 배열은, 연속된 메모리 구조를 갖는다. (연관된 데이터 모아서 관리하는 게 목적이니까)

이 때, 배열은 인덱스를 갖게 된다. 이 때 인덱스는 0번 부터 시작한다.

 

인덱스는 원하는 메모리 위치에 접근하는 이정표가 된다.

intArr[0] = 1;
intArr[1] = 5;
intArr[2] = 9;
intArr[3] = 15;

 

 

접근 공식

메모리 주소값 + (배열의 타입이 갖는 메모리 크기 x 인덱스)

 

위의 공식을 바탕으로, 인덱스를 통해 딱 1번의 연산을 통해 원하는 위치에 접근하고 값을 입력, 수정, 제거할 수 있다.

 

 

그렇다.

'인덱스를 통한 접근은, 빠.르.다.'

 

빅오 표기법에서 가장 최상의 성능을 나타내는 O(1)을 나타내는 예시가 바로 이것이다.

데이터가 몇개가 되든 1회 연산으로 처리 가능!

 

인덱스를 활용할 수 있다면 최대한 활용 하도록 하자. ( 빠르잖아?)

 

추가

배열의 생성과 인덱스를 통한 데이터 접근 원리는 훑어 보았다.

그럼 이제 배열을 가지고 놀아보자.

 

이번엔, 값의 수정이 아닌 추가를 해 보자.

 

규칙

- 데이터를 추가할 때, 기존의 값은 사라져선 안 된다.

 ㄴ 다만, 배열의 크기를 넘어가게 될 경우, 마지막 칸에 있는 기존 데이터는 소멸된다.

 

 

1. 배열의 첫 번째에 값 추가

private static void addFirstIndex(int[] arr, int addElement) {
        for (int i = arr.length - 2; i >= 0; i--) {
            arr[i + 1] = arr[i];
        }
        arr[0] = addElement;
    }

배열에 담긴 모든 값을 옮기게 되므로, O(n) 이 된다.

 

2. 배열의 특정 위치에 값 추가

private static void addSelectIndex(int[] arr, int index , int value) {
        // 인덱스 n 번부터 뒤로 밀기
        for (int i = arr.length - 1; i >= index; i--) {
            arr[i] = arr[i - 1];
        }
        arr[index] = value;
    }

특정 위치라고는 하나, 첫 번째 인덱스에 추가하는 것과 다를 바가 없다. O(n)

 

3. 배열의 마지막 위치에 값 추가

배열[배열.length - 1] = 배열[마지막 인덱스]

이므로, 배열의 마지막에 값을 추가하는 것은 1회 연산 O(1)으로 끝난다.

 

배열의 한계

배열은 가장 기본적인 자료구조이다. 위에서 언급한 바와 같이, 인덱스를 사용했을 때 빠른 속도로 데이터에 접근할 수 있는 장점을 갖는다. 다만, 배열을 생성하는 시점에 배열의 크기를 미리정해야만 한다는 한계점을 갖는다.

 

테이블 4개인 식당에 10팀이 오면 못 받는 것과 같다.

정된 공간엔 그 이상의 값을 담을 수 없다.

 

이러한 한계를 극복하는 방법을.. 이후에 알아보자! 가즈아!