[JS] 배열

배열의 특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.
• C언어와 같은 컴파일러 언어에서는 자동으로 크기가 증감되지 않고 새로운 메모리를 할당하는 방법으로만 크기를 늘려줄 수 있다.(Malloc 등)
• 반면 스크립트 언어(JavaScript, Python 등)는 동적으로 크기가 증감되도록 설계가 되어있음.
• index를 알고 있다면 O(1)으로(상수 시간) 원소를 찾을 수 있음.
• 원소를 삭제하면 해당 index에 빈자리가 생김.

배열 요소 삭제 후 앞당기기 or 배열 중간에 요소를 추가한다면?

가정

• 배열 요소를 삭제할 때 정렬 혹은 탐색을 위해 요소를 앞당겨야하는 상황이거나 요소를 배열 중간에 추가하는 상황을 가정해보자

과정

• 요소를 삭제 후 순서를 맞추려면 O(n)(선형 시간) 만큼 시간이 걸릴 수 있음.
• 중간에 요소를 추가하고 싶다면 마찬가지로 O(n) 만큼 시간이 걸릴 수 있음.

결과

• 요소 추가나 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.
• 배열은 탐색이 많은 경우 유리하다 → index 때문에!

JavaScript에서 배열 사용법

배열 생성

let arr1 = []; // []
let arr2 = [1,2,3,4,5]; // [1,2,3,4,5]
let arr3 = Array(10).fill(0); // [0,0,0,0,0,0,0,0,0,0]
let arr4 = Array.from({ length: 10 }, (_, i) => i); // [0,1,2,3,4,5,6,7,8,9]

배열 요소 추가, 삭제

const arr = [1, 2, 3];

arr.push(4); // 4가 끝에 추가 됨, O(1)
arr.push(5,6); // 여러개를 한번에 추가, O(1)

// 참고 splice 두번째 인자는 배열에서 제거할 요소의 수 0이하면 어떤 요소도 제거 안함.
// 생략하거나 값이 (array.length - splice 첫번째 인자)보다 크다면 start 부터 모든 요소 제거.
arr.splice(3, 0, 128); // 3번 인덱스에 128을 추가, O(n), [1,2,3,128,4,5,6]

arr.splice(3, 1); // 3번 인덱스 값 제거, O(n), [1,2,3,4,5,6]

console.log(arr[3]); // 4, 즉 splice는 삭제 후 요소들을 앞당기기 때문에 O(n)이 걸리는 메서드다.

특이점

• 자바스크립트의 Array는 동적으로 작동한다.
• 자바스크립트 Array의 인덱스는 숫자가 아닌 문자열이나 논리값이 들어갈 수 있다. → 이 이유는 자바스크립트의 Array는 근본적으로는 객체타입이기때문이다. → 일반적인 객체와 다른점은 length가 내부적으로 관리가 된다! 그래서 인덱스와 무관한 값을 인덱스로 사용하게 된다면 그 원소들은 배열 길이에 영향을 미치지 않음.

+추가내용

배열의 시간복잡도는 경우에 따라 다르고 상황에 따라 다르다!

데이터 탐색

• 임의 접근 방식을 사용하기 때문에 데이터를 탐색할 때 처음부터 찾을 필요가 없다. 인덱스 번호가 있기 때문에 인덱스를 통해 매우 빠르게 탐색할 수 있음. 이 때 배열은 O(1)의 시간복잡도를 가진다.

데이터 추가

• 추가하려는 데이터의 위치가 맨 뒤가 아니라면, 추가되는 데이터 위치 이후에 있는 모든 데이터들을 한 칸씩 미뤄야하므로 O(n)의 시간복잡도를 가짐.(위에 설명)
• 추가하려는 데이터의 위치가 맨 뒤고 배열에 공간이 남아있다면 O(1)의 시간복잡도를 가짐.

데이터 삭제

• 삭제하려는 데이터의 위치가 맨 뒤가 아니라면 추가와 마찬가지 원리로 O(n)의 시간복잡도를 가짐.(위에 설명)
• 추가하려는 데이터의 위치가 맨 뒤고 배열에 공간이 남아 있다면 O(1)의 시간복잡도를 가짐.