Java 자료 구조 - 배열

배열

자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나누니다.  배열은 이 중 연속 방식의 가장 기본이 되는 자료형이다. 배열의 값은 집합으로 구성되며, 하나 이상의 인덱스 또는 키로 식별한다.  추상 자료형(Abstrac Data Type, 이하 ADT)의 실제 구현은 대 부분 배열 또는 연결 리스트를 기반으로 한다. 스택은 연결리스트로 구현하고 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 충분히 가능하다.

 

C언어를 기준으로(C는 자료구조의 가장 기본적인 형태를 소개하기에 가장 적합한 언어이다.)배열 설명을 보면, 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능 하다. 

 

그림 7-1 물리메모리에 순서대로 배치된 배열

int arr[5] = {4, 7, 29, 0, 1};

 

위 C코드는 정수형 멜리먼트 5개로 이루어진 배열을 생성한다. 물리 메모리, 즉 실제 메모리에는 배열 엘리먼트의 값 4, 7, 29, 0, 1이 그림 7-1과 같이 순서대로 배치된다. 그림에서는 배열을 정수형 int로 선언했는데, int의 크기는 컴파일러와 프로세서 구조에 따라 상이하다. 과거 16비트 이전에, int는 2바이트였다. 그러나 이 그림에서와 같이 오늘날 32비트 이상의 시스템에서는 int를 4바이트로 사용한다. 앞으로의 게시물에서도 메모리에 대한 접근은 바이트 단위로 한다. 따라서 가리키는 주소는 1바이트마다 1씩 증가하고, int형 배열의 엘리먼트는 4바이트이다. 따라서 배열의 주소 또한 4씩 증가한다.

 

배열은 어느 위치나 O(1)에 조회가 가능하다는 장점이 있다. 예를 들어 그림 7-1의 배열에서 4번째 값에 접근하고 싶다면 int 배열이므로 각각 배열에서 3번째 값에 접근하고 싶다면 int 배열이므로 각각 4바이트, 즉( 3 - 1) x 4 = 8이 되고, 0x00에서 시작해서 8만큼 증가한 16진수는 0x08이 된다. 이 주소를 찾으면 해당 메모리에 배치되어 있는 값 29를 바로 읽어 올 수 있다. 배열의 요소가 5가 아니라 1억개 라도 마찬가지다. 즉시 주소를 계산할 수 있고, 언제든 해당 메모리 주소에 있는 값을  O(1)에 조회 가능하다.  

 

동적 배열

배열이란 고정된 크기만큼의 연속된 메모리 할당이다. 그러나 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 적은 영역을 할당해 모자라거나, 때로는 너무 맣은 영역을 할당해 낭비될 때도 있다. 그렇다면 미리 크기를 지정하지 않고 자동으로 조정할 수 있다면 좋지 않을까? 이런 고민을 해결하고자 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장했다.

 

대부분의 프로그래밍 언어는 동적 배열을 지원하며, 자바에서는 ArrayList가 대표적인 동적 배열 자료형이다. 이 외에도 파이썬이나 루비 같은 동적 프로그래밍 언어(Dynamic Programming Languge)는 아예 정적 배역 자체가 없다. 

 

동적 배열의 원리는 간단하다. 미리 초기값을 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 , 늘려주고 모두 복사하는 식이다. 대개는 더블링(Doubling)이라 하여 2배씩 늘려주는데, 당연히 모든 언어가 항상 그런 것은 아니며 각 언어마다 늘려가는 비율은 상이하다.

 

자바의 동적 배열인 ArrayList의 더블링 구조를 잠깐 살펴보자. ArrayList는 초기 값으로 크기가 10인 배열을 설정하고, 값으로 공간이 가득 차면 더블링으로 늘려준다. 명치은 더블링이지만 정확히 2배로 늘려주는 것은 아니며, 이 재할당 비율을 그로스 팩터(Growth Factor) '성장 인자'라고 하는데 자바의 ArrayList는 다음과 같이 비트 연산으로 계산하도록 구현되어 있으면, 이 비율은 정확히 1.5(50%)배다.

 

int newCapacity = oldCapacity + (oldCapacity >> 1);

 

즉 배열이 가득 차면 1.5배 더 큰 메모리 영역을 할당하고 다시 데이터를 모두 복사하는 식으로 늘려나간다.

💡 tip) 비트 Shift 연산자

<< : 피 연산자의 비트열을 왼쪽으로 이동 시키며 이동에 따른 빈 공간은 0으로 채움.
>> : 피 연산자의 비트열을 오른쪽으로 이동시키며, 이동에 따른 빈 공간은 음수의경우엔,1 양수의 경우엔 0으로 채움
>>> : 피연산자의 비트열을 오른쪽으로 이동시키며, 이동에 따른 비공간은 0으로 채움

 

그림 7-2 동적 배열에 엘리먼트를 추가하는 구조

동적 배열의 구조를 나타낸 그림 7-2에서는 자바의 ArrayList에 아이템을 삽입할 때 동적배열의 용량이 가득 차면 크기를 늘려나가는 모습을 확인할 수 있다. 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다. 그러나 더블링이 필요할 만큼 공간이 차면, 위 그림 처럼 크기가 애초에 잡아 놓은 초기값을 넘어서면 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존읜 데이터를 복사해주는 작업이 필요하므로 O(n)비용이 발생한다. 즉 최악의 경우 엘리먼트 삽입시 O(n)이 되지만 자주 일어나는 일은 아니므로, 분할 상환 분석에 따른 입력 시간 Amortized Insert Time은 여전히 O(1)이다. 이처럼 동적 배열은 분할 상황 분석에 따른 시간 복잡도를 설명하는데 대표적인 자료형이기도 하다.

 

* 분할 상황 분석 : 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원너 사용량을 분석하기 위해서 사용하는 기법

 

 

[출처 - 자바 알고리즘 인터뷰 with 코틀린 , 저 박상길]

https://www.onlybook.co.kr/entry/java-algorithm-interview

자바 알고리즘 인터뷰 with 코틀린