본문 바로가기

■ 프로그래밍/Front-end

자료 구조(Data Structure) (2) - Array(배열)

Array(배열)는 자바스크립트 카테고리에서 한 번 다룬적이 있다. (2020/03/03 - 배열(Array) (1) - 생성, 접근, length)

이번 글은 배열을 어떻게 쓰는지 보다, 배열의 특성, 장단점에 대해 다룰 것이다. 

(자료 구조에 저장하는 데이터는 일반적으로 요소(element)라 한다)

 

Array 특징: "순차적(ordered)으로 데이터를 저장한는 자료 구조"

- 주로 서로 연결된 데이터들을 순차적으로 저장할 때 사용

- 순서가 상관 없더라도, 서로 연결된 데이터들을 저장할때 사용

- 삽입(Insertion) 순서대로 저장 (즉, 새로 삽입되는 요소는 배열의 맨 끝에 위치한다)

- 이미 생성된 것도 수정 가능(mutable)

- 동일한 값 여러번 삽입 가능

- Multi-dimentional Array(다중차원 배열): 배열안에 배열이 들어올 수 있음

 

Array 내부 구조

출처: https://www.geeksforgeeks.org/array-data-structure/

Array는 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장한다. 따라서 어느 자리에 있는지 번호로 지정할 수 있으며, 이 번호를 index라 한다. index는 0부터 시작된다. 

index를 사용해 array의 요소를 읽을 수 있으며, 요소의 특정 부분(ex. n번 째부터 m번 째까지)을 잘라(slicing) 올 수 있다. 

 

Array 단점

순차적으로 데이터를 저장하는 것은 Array의 특징이자 단점이 될 수 있다. 

출처: https://beginnersbook.com/2013/12/java-arraylist/

Array의 중간 요소를 삭제할 경우, 뒤에 있는 데이터를 삭제한 요소 수 만큼 앞으로 이동시켜줘야 한다. 

 

데이터를 새로 추가할 때 Resizing 문제가 생길 수 있다. Resizing이란 메모리의 사이즈를 다시 조정한다는 뜻이다. 

배열은 메모리를 순차적으로 채우며, 처음 생성될 때 어느 정도 메모리를 미리 할당(pre-allocation)한다. 

메모리를 pre-allocation하면서 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있다. 하지만 처음 할당한 것보다 요소가 더 많아진다면 resizing이 필요하다. 

Array의 특성상, 추가적으로 할당 된 메모리 또한 순차적으로 들어가야 하기 때문에 상대적으로 오래 걸린다. 

만약 10개의 메모리 공간이 다 찼을 때 다시 10개를 추가해야 할 경우, 20개 크기의 메모리 생성 후, 기존 10개를 복사하고 그 다음 11번 째부터 데이터가 순차적으로 추가된다. 

Array Resizing

이렇듯 Array의 데이터를 삭제하고 추가할 때 실제 메모리 상에서 이루어지는 작업이 커서, 보통 정보가 자주 삭제/추가 되는 데이터일 경우 Array를 사용하지 않는다. 

 

Array 사용

- 순차적인 데이터를 저장할 때 (ex. 주식 가격, 대회 결과, 날씨 등)

- 다차원 데이터를 다룰 때 (ex. 배열 안의 배열이 필요할 경우)

- 어떤 특정 요소를 빠르게 읽어야 할 때 (ex. index로 바로 불러와야 할 경우)

- 데이터 사이즈가 자주 바뀌지 않을 때

- 요소가 자주 삭제 되거나 추가되지 않을 때