[자료구조] Array

오늘은 Array에 대해서 알아보겠습니다.

 

Array란?

고정된 저장 공간을 미리 할당받고 순차적으로 데이터를 저장하는 자료구조입니다.

 

간단하게 특징을 말하면

 

1. 선언시 저장 공간을 정함

2. 연속적/순차적으로 데이터를 할당

 

이렇게 볼 수 있을 것 같습니다.

 

java 환경에서는 다양한 방법이 있지만 보통

int[] numbers = {1,2,3};
String[] names = {"카리나", "닝닝"};

 

이런 식으로 선언합니다.(저는)

 

Array를 조금 더 깊게 알아보자.

위의 예시 중 int[] 배열이 보이실 겁니다.

이 int Array는 실제 메모리 상에서 어떻게 선언이 될까요?

 

int는 4byte라는것은 알고 계실 겁니다.

그럼 아까 제가 말씀드렸던 첫 번째 특징인 '선언 시 저장 공간을 정함'이 발생하며

4 * 3 = 12byte의 공간을 할당받고 1,2,3이 '연속적/순차적으로 데이터를 할당'됩니다.

 

쉽게 그림으로 보면

 

조금 더 부가 설명을 해드리자면 각 데이터의 첫 번째 주소값이 각 데이터의 주소값입니다.
데이터 1의 주소값은 '0x1'이겠죠?

2의 주소값은 '0x5'입니다.

또한  numbers Array는 제일 첫 번째 데이터인 1의 첫번째 주소값 '0x1'을 가리키고 있습니다.

 

배열(Array)의 이런 특성 때문에 배열의 어떤 인덱스던 즉시 접근이 가능합니다.

 

좀 더 쉽게 풀어

위의 numbers 배열을 예로 들어 2번째 인덱스인 데이터에 접근을 해봅시다.

numbers 배열은 아까 제일 첫번째 데이터인 1의 첫번째 주소값 '0x1'을 가르키고 있다고 설명드렸습니다.

 

그러면 주소값 '0x1'의 데이터는 0번째 인덱스 값입니다.

하지만 저희는 2번째 인덱스에 가야 합니다. 이 배열은 int형 배열이기 때문에 데이터 하나가 4byte입니다.

그럼 인덱스가 하나씩 늘어날 때마다 주소값은 4씩 늘어나야겠죠?

 

그럼 그냥 'Array의 주소값 + 4 * (n-1)'의 주소로 가게 되면(int배열 기준) 우리가 원하는 인덱스의 값에 바로 접근이 됩니다.

그래서 Array의 접근은 O(1)이 되는 겁니다.

 

이렇게 어떠한 인덱스던 즉시 접근 가능한 것을 Random Access 또는 Direct Access라고 부릅니다.

 

위 내용을 통해 Array는 데이터 접근이 많을 때 좋은 자료구조인 것을 알 수 있었습니다.

 

근데 Array도 단점이 있습니다.

값이 고정되어 있기 때문에 데이터가 혹시라도 추가가 되면 공간이 없어 치명적인 문제가 발생할 수 있습니다.

 

그럼 처음에 Array의 크기를 엄청 늘려서 생성하면 되는 것 아니냐고 할 수 있는데
이렇게 생성하게 되면 결국 남는 메모리 공간이 생길 수 있고 이러한 공간은 너무 비효율적으로 사용되게 됩니다. 

 

이런 걸 해결할 수 있는 것이 다음에 알아볼 Dinamic Array입니다.

 

https://changbroblog.tistory.com/146

[자료구조] Dynamic Array

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.