#4 배열

- 배열은 프로그래밍 언어에서 기본적으로 제공하는 자료구조이다.

- 글을 읽기에 앞서 일반적인 프로그래밍 언어에서의 전형적인 배열과 JS의 배열은 차이점이 있다는 것을 알아두자

 

1. 프로그래밍 언어에서의 전형적인 배열

- 일반적으로 프로그래밍 언어에서 배열을 선언할 때는 아래와 같이 선언과 동시에 배열의 크기를 알려준다.

int arr[10] = {1, 2, 3, 4, 5};

- 위와 같이 선언한 배열은 메모리에서 아래와 같은 모습을 하고 있다

- 운영체제가 메모리에서 숫자 10개가 들어갈 수 있는 연속된 빈 공간을 찾아 순서대로 1, 2, 3, 4, 5 를 할당한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 10개 중 할당되지 않은 부분에는 의미 없는 더미 데이터가 저장된다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 운영체제는 배열의 시작 주소(= 숫자 1이 들어간 주소)만 기억한다.

- 어차피 시작 주소만 찾으면 데이터는 연속되어 있으니까

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

int arr[10] = {1, 2, 3, 4, 5};

- 위의 배열에서 숫자 3을 찾고 싶다면 arr[2] 와 같이 index를 이용해 한 번에 접근한다.

- 운영체제는 배열의 시작 주소를 알고 있기 때문에 시작 주소로부터 두 번째 떨어진 주소에서 데이터를 가져온다.

- 이렇게 배열의 index 참조 방법은 배열의 길이와 상관없이 데이터를 한 번에 가져오기 때문에 O(1) 의 성능을 가진다.

cf) O(1) = 상수시간 알고리즘

- 이러한 이유 때문에 배열은 읽기 / 쓰기인 참조에서 좋은 성능을 가진다.

---

- 반대로 배열에서 데이터의 삽입, 삭제 성능은 좋지 않다.

int arr[10] = {1, 2, 3, 4, 5};

- 배열은 선언과 동시에 그것의 크기를 메모리의 연속된 공간에 할당한다.

- 문제는 이렇게 선언된 크기가 이후에는 수정이 불가능하다는 것이다.(JS는 예외)

- 만약, 내가 처음에는 10개의 크기를 가지고 있는 배열이 필요해서 위와 같이 선언했는데 알고보니 나중에 20개의 배열이 필요한 상황이 되버리면 확장이 불가능하다.

- 운영체제는 배열 선언 시에 10개에 맞는 공간만 할당한 상태이고 10개의 공간 끝에는 아래와 같이 이미 다른 중요한 데이터들이 공간을 차지하고 있기 때문에 확장을 할 수 없는 것이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 20개의 공간이 반드시 필요한 상황이라면 운영체제는 크기가(공간이) 20인 연속된 공간의 메모리를 다시 찾아서 할당해야한다.

- 공간을 다시 할당해야 하는 것은 물론 1~10 까지의 기존 데이터를 전부 새로 할당하는 공간에 복사까지 해야한다.

 

Q. 그렇다면 애초에 아래와 같이 배열의 길이를 엄청 크게 하면 되지 않을까?

int arr[1000] = {1, 2, 3, 4, 5};

A. 아래와 같은 문제가 나올 수 있다.

- 사용자가 1000 보다 더 큰 크기의 배열을 원할 때는 어떻게 할 것인가?

- 메모리에서 차지하는 공간은 1000인데 정작 사용하는 데이터 공간은 7 밖에 안 된다면 그것은 메모리 낭비이다.

- 이렇게 배열은 데이터의 추가, 제거의 측면에서는 그다지 효율 및 성능이 좋지 않은 것을 확인할 수 있다.

 

2. JS의 배열

- JS는 위의 경우와 다르게 배열의 크기를 선언과 동시에 정하지 않는다.

- JS는 push, pop 등의 함수를 이용해 배열의 데이터를 쉽게 추가 및 삭제할 수 있다.

- 맞는 말이긴한데 JS에서의 배열은 위에서 설명한 배열과는 다르게 동작한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- JS에서의 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분은 불연속적으로 메모리를 할당한다.

- 위 그림과 같이 불연속적으로 할당된 메모리를 내부적으로 연결해서 개발자에게는 마치 배열인 것처럼 보이는 것이다.

- 그렇기에 일반적인 프로그래밍 언어에서의 배열과는 조금 다르지만 배열이라는 자료구조의 기능적인 측면에서만 본다면 JS에서도 동일한 개념 아래 배열을 사용할 수 있는 것이다.

 

cf)

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/pop

Array.prototype.pop() - JavaScript | MDN

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/push

Array.prototype.push() - JavaScript | MDN

 

정리

배열의 장점	배열의 단점
- 읽기, 쓰기와 같은 참조에서는 O(1) 성능(좋은 성능)	- 크기 예측이 힘들기 때문에 메모리 낭비 발생 가능성 - 데이터 삽입 및 삭제는 비효율적