[ 자료구조 ] 배열 ( Array )

배열 ( Array )

 

• 배열은 연속된 메모리에 저장이 되고, 사이즈 변경이 불가능합니다.
  • 단, 자바스크립트에서는 사이즈가 동적으로 변합니다.
• 자바스크립트의 배열은 해시 테이블로 구현된 객체이므로 인덱스로 접근하는 경우에는 일반 배열보다 속도가 느리지만, 삽입 & 삭제의 경우에는 보다 빠른 성능을 기대 할 수 있다.  ( ArrayBuffer를 쓰면 실제 배열과 비슷하게 동작이 가능 )

일반적인 배열의 메모리

자바스크립트의 해쉬맵으로 구현된 배열 메모리

• 연속된 메모리 구조 덕분에, 삽입과 삭제 작업은 선형 시간인 O(n) 만큼 소요 됩니다.
  • 삽입의 경우, 새로운 값 이후의 인덱스들을 모두 뒤로 밀어야 하고,
  • 삭제의 경우, 빈 인덱스로 이후의 값들을 당겨 와야 합니다.

• 삽입, 삭제는 느리지만 탐색의 경우 인덱스를 통해 O(1) 만에 접근 할 수 있습니다.
• 하지만, 정렬 되지 않은 배열에서 특정한 값을 찾을 때는 선형 탐색(O(n)) 만큼 걸린다.

function linearSearch(arr, target) {
  const length = arr.length;

  for ( let i = 0; i < length; i++ ) {
    if ( arr[i] === target ) return i; 
  }

  return -1;
}

 

Reference

 

https://evan-moon.github.io/2019/06/15/diving-into-js-array/

JavaScript 배열(Array)의 발전과 성능에 대해서 자세히 알아보기