[JavaScript] 자료구조 : 배열(Array)

배열

배열은 기본 자료형 다음으로 가장 쉬운 자료구조인듯 하다. 대부분의 프로그래밍 언어에서도 많이 쓰는 자료 구조라고 하더라.

배열은 크게 2가지의 종류가 있는데 (동적 / 정적), 자바스크립트는 동적 배열이라 쉬운 듯 하다. 정적 배열을 사용하는 언어로도 배열을 다뤄봤는데 삽시간에 더 이상 배워지기가 싫어지는 느낌이 들었다.

 

배열은 자료들이 메모리 주소에 순서대로 차곡차곡 정렬되어 있는 형태다. index를 통해 임의 element에 매우 빠른 접근을 가능하게 하고,

메서드들이 간단한 문법을 사용하며 반복에 용이한 메서드들 또한 많아 ex) for, for...of, forEach 등 특정 데이터를 순차적으로 반복 처리해야 하는 경우 배열은 최상의 자료구조라고 한다.

 

그래서 배열이 짱이냐?

배열에는 다양한 메서드들이 존재하는만큼, 어떤 메서드를 사용하냐에 따라 시간 복잡도에 영향을 끼친다.

 

push와 unshift를 비교해보자.

push 메서드는 기존 배열의 가장 끝에 특정 element를 추가하는 메서드이다.

push의 경우는 배열을 순회할 필요없이 끝에 추가만 하면 되기때문에 시간 복잡도는 O(1)이다.

(가장 끝에 element를 제거하는 pop 또한 동일)

 

그와 달리 unshift는 배열의 앞에 element를 추가하는 메서드이다.

unshift를 사용하면 맨 앞에 element를 추가되고, 나머지 배열을 순회하며 새로운 index 값을 부여해야 한다.

순회할 필요가 없는 pop과 달리 unshift는 O(n)의 시간 복잡도를 가지게된다.

 

unshift를 보면 알 수 있듯이, push나 pop을 제외하고 원본 배열을 수정하는 메서드들은 배열을 수정한 뒤 나머지 element들의 index 또한 수정하는 작업을 거쳐야 하기때문에 O(n)의 시간 복잡도가 발생하는 것을 알 수 있다. 당장의 작은 배열로는 별 차이 없을 수 있지만, 배열의 크기가 커질수록 이는 성능저하의 요인이 되므로 각 메서드들의 동작 원리를 이해하는 것이 좋은 코드를 짜는데 도움이 될 것이다.

종합

장점 : 쉽고 빠른 접근

단점 : 삽입 및 삭제 성능