[자료 구조] 배열 & 동적 배열

0. 개요

자료구조란 데이터를 구성하고 저장하는 방법을 설명, 데이터를 식별하는 방법을 제공, 데이터의 관계를 보여주는 개념

 

즉, 데이터들을 효율적으로 활용하기 위해 우리는 자료 구조를 배우고 사용한다.

앞으로 배워나갈 자료구조들은 특정한 상황의 문제들을 푸는데 각각 특화되어 있다.

 

위의 그림이 자료구조를 도식화 한 내용이다.

단순구조, 선형구조, 비선형구조, 파일구조가 있고 각 자료 구조들을 하나하나씩 정리할 계획이다.

추상 자료형(Abstract Data Type)

단순히 어떤 기능들에 대해 나열 한 것.

 

ADT의 경우 기능에 대해 세부적인 구현에 대해서는 이야기 하지 않고, 단순히 어떤 기능들이 있는지를 표현한 것이다.

예를 들면, [문서 작성 & 웹 서핑 & 메일 & 프로그램 개발]

과 같이 컴퓨터의 기능들을 나열했다. 기능의 세부적인 구현이 아닌 기능만을 나열했기 때문에 이런 것들이 바로 추상 자료형이다.

1. 배열

먼저 선형 구조 중 배열에 대해 살펴보도록 하겠다.

선형 구조란 <데이터들을 서로 인접한 순차적인 방식으로 나열된 구조>이다.

 

배열의 경우 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는다.

또한, 크기가 고정되어 있어, 생성한 배열의 크기를 변경하는 것은 불가능하다!

[3,5,2] 배열을 입력 받았을 때 메모리에 위의 그림과 같이 들어간다.

(int 자료형의 경우 4byte 이기 때문에 4개의 bit를 차지)

그렇기 때문에 2에 접근하고 싶다면, (3-1)*4 =8. 8번째에 해당하는 주소를 찾으면 된다.

이렇게 주소값, 인덱스를 통해 바로 값을 가져올 수 있기 때문에 배열의 경우 O(1)에 값 조회가 가능하다!

 

정리하자면

• 배열 내의 데이터들은 순차적, 연속적으로 정렬되어 있음.
• 배열에 메모리를 할당하기 전에 배열 크기를 지정해야 함
• 인덱스를 통해 접근하여 바로 값을 가져오기 때문에 O(1)에 값 조회가 가능함.

2. 동적 배열

배열의 경우 크기를 미리 지정해야 한다. 즉, 고정된 크기만큼 연속적으로 메모리에 할당해서 크기를 정확하게 측정하기 어려운 상황에서는 메모리 영역이 낭비되거나 모자랄 수 있다.

이러한 불편함을 해소하고자 크기를 미리 지정하지 않고 리사이징 할 수 있는 배열인 동적 배열이 나타났다.

원리

• 미리 초깃값을 작게 잡아 배열을 생성한다.
• 데이터가 추가되고 배열이 꽉차게 되면 늘려준 뒤 기존 배열의 값을 모두 복사한다. -> 더블링이라 함.
• 늘려주는 비율은 언어마다 상이한데 java를 기준으로 진행을 확인해보자.

Java

자바의 동적 배열은 ArrayList로 다음과 같이 선언한다.

ArrayList<Integer> arrayList = new ArrayList<>();

 

ArrayList의 경우 초깃값으로 크기가 10인 배열을 설정한다. 그 뒤 메모리가 꽉차게 되면 더블링으로 늘려준다.

이때 재할당 비율을 성장 인자(growth Factor)라고 하는데 다음과 같이 설정한다.

int growthFactor = old + (old >> 1);

 

이 비율이 정확히 1.5배라고 한다.

즉, 1.5배 더 큰 메모리 영역을 할당하고 기존 배열에 있던 값들을 모두 복사해준다.

 

정리

• 동적 배열은 크기를 미리 지정해주지 않고, 메모리가 가득차면 더블링을 통해 늘려줄 수 있다.
• 이때 기존 값들을 복사하여 새로운 배열에 할당해준다.
• 조회는 기존의 배열과 마찬가지로 O(1)에 가능하다.
• 삽입에 경우 데이터 복사의 작업이 필요하기 때문에 최악의 경우 O(n)이지만 대부분 O(1)이다.
• 삭제 연산의 경우 맨 앞의 데이터 지울때 -> O(n)[데이터를 한 칸씩 밀어야 하므로]
  맨 뒤의 데이터 지울 때 -> O(1)이다.