JavaScript의 Array

자바스크립트에서의 배열은 다른 언어에서의 일반적인 배열이 아니라 Hash Table 구조를 가진 배열이다 그래서 원소가 하나씩 추가된다면 {key: index, value:value}형태의 원소를 추가한다

push() & pop()

push()

배열의 가장 마지막에 원소를 추가한다.
배열을 순회할 필요 없이 배열의 끝에만 원소를 추가하면 되기 때문에 시간복잡도는 O(1)이 된다.

pop()

배열의 가장 마지막에 있는 원소를 삭제한다.
배열을 순회할 필요 없이 배열의 끝에 있는 원소를 삭제하면 되기 때문에 시간복잡도는 O(1)이 된다.

const arr = ['a', 'b', 'c', 'd'];
// push
arr.push('e');
console.log(arr); // ['a', 'b', 'c', 'd', 'e']

// pop
strings.pop(); // ['a', 'b', 'c', 'd'];

unshift() & shift()

unshift()

배열의 맨 앞에 원소를 '추가'한다.
배열의 맨 앞에 원소를 추가하는 것이기 때문에 기존에 있던 원소들을 뒤로 밀어야함
따라서 배열의 길이가 n일 경우 기존에 있던 n개의 데이터들의 index값을 기존 'index값+1'로 바꿔 주어야 하기 때문에 시간복잡도가 O(n)이 된다.

const arr = ['a', 'b', 'c', 'd'];
// unshift
arr.unshift('e'); // ['e', 'a', 'b', 'c', 'd']; 

shift()

배열의 맨 앞에 원소를 '제거'한다. 이것도 unshift()와 마찬가지로
배열의 맨 앞에 원소를 제거하는 것이기 때문에 기존에 있던 원소들을 앞으로 당겨야함
따라서 배열의 길이가 n일 경우 삭제할 원소를 제외한 n-1개의 데이터들의 index값을 기존 'index값-1'로 바꿔 주어야 하기 때문에 시간복잡도가 O(n)이 된다.

const arr = ['a', 'b', 'c', 'd'];
// shift
arr.shift(); // ['b', 'c', 'd']; 

sort()

배열의 원소들을 인자값으로 넘어온 함수에 따라 값을 정렬한다.

const arr = [1,2,3,4,5,6,7,8,9,10];
// sort
arr.sort(); // [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]

함수가 없는경우, Unicode값을 순서로 정렬한다(국어사전이나 영어사전같은 사전에서의 순서로 정렬함)

const arr = [1,2,3,4,5,6,7,8,9,10];

function compare(a,b){
    return a-b;
}
// sort
arr.sort(compare); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

위와 같이 비교함수를 정의해서 sort의 인자값으로 넘겨주면 return 값이 '음수'라면 a가 먼저 오고 '양수'라면 b가 먼저 온다. 0일 경우 순서가 바뀌지 않는다.

sort()의 경우 정렬 알고리즘으로 'Timsort'라는 알고리즘을 사용하며 시간복잡도는 O(nlog(n))이 나온다

Timsort 참고링크1
Timsort 참고링크2

includes()

배열에 특정 원소가 있는지 판별하고 있으면 true, 없으면 false를 반환한다.

const arr = [1, 2, 3];

console.log(arr.includes(2)); // true
console.log(arr.includes(100)); // false

두번째 인자로 탐색 시작 인덱스를 넣어주면 해당 위치부터 찾는다. 특정원소를 찾기 위해서 최악의 경우 배열의 모든 원소를 탐색해야 하기 때문에 시간복잡도는 O(n)이 된다.

Q1. push() vs 인덱스 접근

// 인덱스 접근
const NUM_OF_DATA = 100_000_000;

function type1() {
    console.time('input');
    const data = [];
    for (let i = 0; i < NUM_OF_DATA; i++) {
        data.push(i + 1);
    }

    console.timeEnd('input');
}

걸린시간 : 2.088s

// push
const NUM_OF_DATA = 100_000_000;

function type2() {
    console.time('input');
    const data = [];
    for (let i = 0; i < NUM_OF_DATA; i++) {
        data[i] = (i + 1);
    }

    console.timeEnd('input');
}

걸린시간 : 1.955s

결론: 시간 차이는 100ms 정도 차이가 난다 0.1초 정도면 큰 차이는 아니지만 그래도 알고리즘 문제에서는 조금이라도 더 빠른걸 써야하기 때문에 push()를 쓰도록 하자.(그리고 가독성도 더 좋다)

글 작성에 참고한 링크들
자바스크립트 Array메서드 시간복잡도1
자바스크립트 Array메서드 시간복잡도2
자바스크립트 push() vs initialize with size