[데이터구조] 배열 / 객체 / Set / Map

 

일반적으로 사용하는 데이터 구조와 그에 대한 메서드의 시간 복잡도를 알아보자

 

Array (배열)

const arr = [1, 2, 3, 'string']

 

값들을 저장할 수 있는 데이터 구조로, 같은 하나의 배열 안에 다양한 타입을 포함할 수 있다.

생성하기 전에 크기를 지정할 필요없이 사이즈 변경이 가능하다.

인덱스는 0에서부터 시작하고 삽입한 순서대로 유지된다.

배열은 반복이 가능하기 때문에 for 문 안에서 사용할 수 있다.

 

배열의 끝에 삽입을 하거나 배열의 끝에서 삭제할 경우: O(1)

배열의 처음에 삽입 혹은 처음에서 삭제할 경우: O(N)

인덱스로 요소에 접근하는 경우: O(1)

검색하는 경우: O(n)

 

따라서 자주 사용하는 메서드를 분류해 보자면,

push, pop: O(1)

shift, unshift, concat, slice, splice: O(n)

forEach, map, filter, reduce: O(n)

 

Object (객체)

const obj = { name: 'key', value: 200 }

 

key - value 짝으로 이루어진 정렬이 되지 않은 데이터 구조이다.

키는 반드시 string이거나 symbol이어야 하며 값은 아무런 데이터 타입이어도 가능하다.

값을 가져오기 위해서는 알맞은 키를 보내주어야 하며 . 을 붙이거나 [] 표현을 통해서 가져올 수 있다.

보통은 점을 가지고 표현을 많이 하며, 만약 키값에 -나 공백이 있는 경우에는 대괄호를 통해 표현한다.

 

객체는 반복이 불가능하기 때문에 반복문에서 사용할 수 없다.

 

객체에 요소를 추가하거나 삭제할 때 키로 접근이 가능하기 때문에 O(1)

검색할 때는 O(n)

 

keys(), values(), entries() : O(n)

 

hasOwnProperty() 메서드는 set의 has 혹은 map의 has 메서드보다 속도가 빠르다.

(참고: https://stackoverflow.com/questions/31091772/javascript-es6-computational-time-complexity-of-collections)

 

Set

const set = new Set([1, 2, 3])

 

값들을 저장할 수 있는 데이터 구조이고 같은 값은 중복이 될 수 없이 unique 해야 한다.

다양한 데이터 타입을 저장할 수 있고 크기를 미리 지정하지 않아도 자유롭게 변경할 수 있다.

포함된 요소의 순서는 보장되지 않는다. 반복문에서 사용할 수 있다.

 

특히 요소의 숫자가 큰 경우에는 배열보다 검색하는 속도가 더욱 빠르다.

 

add(), has(), delete(): O(1)

clear(): O(n)

 

 

Map

const map = new Map(['a', 1], ['b', 2])

 

key-value로 이루어진 정렬되지 않는 데이터 구조로, 어떤 데이터 타입도 담을 수 있다.

값을 찾기 위해서는 키를 제공하면 된다. 반복문에서 사용할 수 있다.

 

배열에는 함수를 포함할 수 있으나 map에서는 함수는 저장할 수 없다.

 

get(), set(), add(), has() : O(1)