배열

배열

가장 기본적인 자료구조. 연속성을 띈다.

인덱스를 통해 쉽고 빠르게 데이터에 접근할 수 있는 자료 구조이다.

 

배열 생성 원리

배열 생성 요청 - 메모리 할당 - 배열 생성 - 참조주소값 반환

 

int [] arr = new int[n]; // x100 이라 했을 때

배열은 연속된 자료구조이므로,

배열이 갖는 주소값들 또한 x100과 밀접한 관계(규칙성)을 갖는다.

 

배열에 담기는 메모리 크기 * index 로 접근 가능하다는 모양.

 

따라서, 특정 위치에 접근할 때 

배열의 기본 주소값 + 배열 타입 메모리 크기 * index

 

1회의 연산으로 해당 위치의 데이터에 접근 가능함.

 

 

빅오표기법

알고리즘 성능 분석에 사용되는 수학적 표현식.

알고리즘 수행 시 발생하는 연산 수를 간략하게 표기함.

 

배열에 값을 입력할 때

arr[n] = 입력값;

이므로, 

배열의 입력 빅오표기법은  O(1);

전체 조회는 별 수 없으므로, O(n);

 

특정 위치값 조회는 인덱스를 알고 있을 경우 입려고가 마찬가지로 O(1);

 

최적 : 1회의 연산

최악 : O(n)  중첩 for문 발생시 연산 수가 기하급수적으로 증가하고 성능 저하로 이어지기 쉽다.

평균 : O(n/2) 로 적당히 중간 정도에서 찾지만 빅오표기법에선 상수 제외 O(n)으로 표기함.

 

 

배열의 데이터 추가

조회, 수정을 위해 특정 위치에 접근하는 것은 O(1)이다.

그러나, 추가, 삭제 해야 할 경우, O(n) 의 연산이 발생한다.

 

[1][2][3][4][5] 배열 가 있을 때, value 3의 위치. 즉 index[2] 에 값을 추가할 경우,

 

[1][2][N][3][4][5] 기존에 index[2,3,4] 의 값들을 +1씩 옮겨줘야 한다.

따라서 O(n)의 추가(shift) 연산이 발생한다.

삭제도 마찬가지.

 

배열의 경우 위치에 따라 연산 횟수가 크게 차이 난다.

마지막 - O(1) 

기존 값 이동 연산이 필요 없다.

중간 - O(n)

O(n/2) 지만 빅오표기법은 n 생략

처음 - O(n)

가장 많은 연산 수를 발생시킨다.

 

배열의 한계

1. 고정된 길이

배열은 가장 기본적인 자료구조이다.

생성 시, 반드시 길이를 결정해야하며, 이는 변하지 않는다.

10자리 준비했는데, 11손님 오면 터져버리는 녀석.

 

2. 부족한 기능

자료구조로서의 성능 외 다른 기능을 기대하기 힘들다.

값 저장, 추가, 수정, 조회 외 작업이 어렵다.

 

이러한 한계를 극복하기 위해 만들어진 것이 Collection 들이다.