결론
배열 자료구조를 Read, Search, Insert, Delete 4가지 동작 관점에서 바라보았을 때,
요소에 접근하는 동작(Read)은 인덱스를 통해 단 한 번의 연산(O(1))으로 가능하지만
요소의 탐색은 선형 시간 복잡도 O(n)을 가진다.
위해 삽입, 삭제 동작시 배열의 요소들은 연속적으로 유지하기 위해 다른 요소들을 이동시켜야 하므로 비효율적일 수 있다.
순차적으로 값에 접근하기 적합한 자료구조이다.
자바스크립트의 배열과 자료구조에서의 배열은 다르다.
개요
자료구조에서 배열이란 각 요소가 동일한 크기의 메모리 공간에 담겨 있고(같은 자료형 데이터), 빈틈 없이 연속적으로 이어진 자료구조이다.
배열이 메모리 공간에 저장되면, 컴퓨터는 이 메모리 공간의 시작 주소를 알고 있다.
그리고 배열은 위치를 나타내는 인덱스를 통해 요소에 접근할 수 있으며 인덱스는 0번부터 시작한다.
인덱스를 통해 단 한 번의 연산(step)으로 임의의 요소에 접근할 수 있다
따라서 요소에 접근하는 동작은 상수 시간 복잡도 O(1)을 가진다.
배열의 크기는 동적으로 변경될 수 있다.
4가지 동작 관점에서 바라본 배열
1.Read(접근) 관점
배열은 각 요소마다 인덱스가 있기 때문에 위치(인덱스)만 안다면 해당 요소에 바로 접근할 수 있다.
(RAM의 특징 : 특정 메모리 공간에 바로 접근할 수 있다.)
| 치킨 | 피자 | 짜장면 | 돈까스 |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
피자 데이터의 인덱스가 1번이라는 것을 알고 피자 데이터에 접근하고 싶다면 인덱스 1번을 이용해 바로 접근하면 된다.
컴퓨터는 배열이 저장된 메모리 공간의 시작점(위치, 인덱스)을 알고 있고, 배열의 요소들은 시작 주소부터 연속적인 공간에 저장되어 있으므로 배열의 요소들을 빠르게 읽어들일 수 있다.
따라서 많은 자료를 읽어 들어야 한다면, 배열은 효율적인 자료구조가 될 수 있다.
2.Search(탐색) 관점
탐색이라는 작업은 해당 데이터가 배열에 있는지 없는지를 모르기 때문에 수행하는 작업이다.
그리고 있다고 해도 찾기 전까진 해당 요소의 위치(인덱스)가 어디인지 모른다.
따라서 배열의 모든 인덱스에 순차적으로 접근해 해당 인덱스의 요소가 찾고자 하는 값인지 비교해야 한다.
선형 시간 복잡도 O(n)을 가진다.
| 치킨 | 피자 | 짜장면 | 돈까스 |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
배열에 짜장면이라는 값이 있는지 찾아보아야 할 때,
0번 인덱스에 접근해서 값이 짜장면인지 확인하고 아니라면, 그 다음 인덱스에 접근해서 짜장면인지 확인하는 과정을 값을 찾을 때까지 수행한다.
배열에서 데이터를 탐색할 때, 최선의 경우는 찾고자 하는 데이터가 배열의 첫 번째 인덱스에 있는 경우이다.
반대로 최악의 경우는 데이터가 없거나 배열의 마지막 인덱스에 데이터가 존재하는 경우이다.
이때에는 첫 번째 인덱스부터 마지막 인덱스까지 모두 접근해서 값을 확인해보아야 한다.
이렇게 처음부터 끝까지 순서대로 탐색하는 방법을 선형탐색(=순차탐색)이고 한다.
결론 : 배열이라는 자료구조에서 데이터를 탐색하는 동작은 효율적이지 않을 수 있다.
(배열을 더 빠르게 탐색하는 방법이 존재한다.)
3.Insert(추가, 삽입) 관점
배열은 이미 연속적인 메모리 공간을 차지하고 있다.
따라서, 요소를 삽입한 이후에도 연속적인 특성을 유지하기 위해 데이터 삽입시 배열의 나머지 요소들을 움직여야 한다.
그리고 컴퓨터는 이 공간의 시작 주소를 알고 있다.
만약, 새로운 데이터를 기존 배열에 추가하는 작업을 수행해야 한다면
최선의 경우는 배열의 마지막에 추가하는 경우이고, 최악의 경우는 배열의 첫 번째 인덱스에 값을 추가할 때이다.
배열의 마지막에 데이터를 추가할 때, 컴퓨터는 배열이 위치한 메모리 공간의 시작 위치를 알고 있기 때문에 마지막에 바로 추가해주면 된다.
하지만, 배열의 맨 처음에 값을 추가한다면, 기존에 있던 데이터들을 모두 한 칸씩 옆으로 이동한 후 배열의 첫 번째 인덱스에 값을 추가해야 한다.
즉 데이터를 추가할 때, 배열의 크기가 클수록 옮겨야 하는 데이터가 많아지므로 데이터를 배열에 추가 동작은 비효율적일 수 있다.
4.Delete(삭제) 관점
배열에 값을 추가하는 과정과 비슷하다.
컴퓨터는 배열의 시작 위치를 알고 있기 때문에
배열의 마지막 인덱스의 값을 삭제하는 경우, 바로 접근해서 삭제하면 된다.
따라서 이 경우가 최선의 경우가 될 것이다.
| 치킨 | 피자 | 짜장면 | 돈까스 |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
최악의 경우는, 배열의 첫 번째 인덱스의 데이터를 삭제하는 경우이다.
치킨이라는 데이터를 삭제한다면, 피자가 0번 인덱스 위치로 이동하고, 짜장면이 1번 인덱스로, 돈까스가 2번 인덱스로 옮겨가야 한다.
만약, 배열의 크기가 커진다면 이렇게 옮기는 작업은 비효율적일 수 있다.
자료구조의 배열 vs 자바스크립트 배열
자바스크립트의 배열은 각 요소가 동일한 크기의 메모리 공간을 갖지 않아도 된다.
즉, 다양한 타입의 데이터들이 배열에 담길 수 있다.
또한 연속적으로 이어져 있지 않을 수도 있다.
(연속적으로 이어져있지 않은 배열을 희소배열이라 한다.)
이처럼 자료구조에서 말하는 일반적인 배열과 자바스크립트에서 말하는 배열은 다르다.
자바스크립트의 배열은 일반적인 배열을 흉내낸 하나의 객체이다.
(인덱스를 나타내는 문자열을 프로퍼티 키로 가지고 length 프로퍼티를 가지는 객체)
따라서, 배열 객체의 length 프로퍼티의 값을 임의로 바꿀 수도 있다.
실제 length 보다 작은 경우를 설정할 때에는 배열의 길이가 줄어든다.
실제 length 보다 큰 경우 실제 배열의 길이가 늘어나지 않는다.(반복문을 통해 배열을 순회할 때 문제가 발생할 수 있다.)
자바스크립트의 배열은 연속적이지 않을 수 있다.
따라서 아래와 같은 코드를 작성할 수 있다.(사용하지 않는 것이 좋다.)
const arr = [,2,,4];
console.log(arr.length) //4
console.log(arr) // [empty , 2 , empty , 4] 실제 empty라는 값이 들어있는 것이 아니다. 자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 요소에 접근하는 경우, 일반적인 배열보다 느릴 수 밖에 없다.
하지만 특정 요소를 탐색하거나 삽입, 삭제하는 경우에는 일반적인 배열보다 빠른 속도를 기대할 수 있다.
자바스크립트의 배열은 객체이다.
자바스크립트에서 배열의 단점을 극복하기 위해 자바스크립트 엔진은 자바스크립트 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다.
