[자료구조] 배열이란?

배열

배열은 연관된 데이터들을 모아서 관리하기 위해서 사용하는 자료구조이다.
그래서 모든 배열의 원소의 타입이 같아야한다.

메모리상에 특정 공간을 미리 점유하고 이 공간에 배열에 있는 데이터들을 순서대로 배치해 메모리를 관리한다.

배열은 선언할 때 미리 크기가 정해지기 때문에 만일 배열 데이터를 많이 사용하지 않으면 사용하지 않는 메모리 공간이 낭비될 수 있다는 단점이 있다.
그리고 배열의 중간에 있는 원소를 마음대로 빼거나 넣은 수는 없고 배열의 마지막 부분에서만 삽입과 삭제가 가능한 특징이 있다.

1. 삽입

배열의 마지막 부분에 데이터를 삽입할 수 있다.
O(1)의 시간복잡도가 필요하므로 굉장히 빠르게 삽입하는게 가능하다.
만약 배열 중간에 삽입하고 싶다면 삽입하려고 하는 위치를 기준으로 뒤에있는 배열의 원소들을 모두 뒤로 미루고 삽입을 해야하므로 O(n)만큼의 시간복잡도가 소요된다.

2. 삭제

배열의 마지막 부분에 데이터를 삭제할 수 있다.
O(1)의 시간복잡도가 필요하므로 속도는 마찬가지로 빠르다.
마찬가지로 중간에 원소를 삭제하고 싶다면 삽입과 마찬가지의 시간복잡도가 소요된다.

3. 순회

배열의 시작부터 마지막까지 순회하기 위해서는 처음부터 순서대로 순회하면 되므로 O(n)의 시간복잡도가 소요된다.

JS 배열의 특이사항

위에 정리한 내용까지가 내가 알고있던 배열에대한 내용이지만 JS의 배열은 일반적인 배열과는 차이가 있다.

JS 배열은 일반적인 배열의 동작을 흉내 낸 특수한 객체이다.

const arr = ['apple', 'banana', 'orange'];

typeof arr // object

JS의 배열은 객체이기 때문에 배열의 원소마다 동일한 크기의 메모리를 할당하지 않을 수 있고 연속적으로 배열의 원소가 메모리상에 존재하지 않을 수도 있다. 이를 희소 배열 이라고한다.

출처

JS Deep Dive