[알고리즘] 배열중간삽입 - Linked List를 알기위한 사전단계

 

배열 순차검색

 

일반적으로 배열은 동일한 크기를 갖고 빈틈없이 연속적으로 이어져있다. 인덱스를 통해 단한번의 연산으로 임의의 요소에 접근할수있다. 하지만 정렬되지않는 배열에서 특정한 값을 탐색하는 경우, 모든 배열요소를 처음부터 값을 발견할때까지 차례대로 탐색해야한다.

 

// 선형 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여
// 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수

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

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

  return -1;
}

console.time("Array Performance Test");
console.log(
  linearSearch(
    [
      7, 19, 54, 23, 81, 66, 77, 31, 92, 18, 15, 61, 43, 25, 56, 95, 44, 67, 23,
      59, 13, 61, 79, 42, 34, 50, 12, 63, 93, 21, 6, 84, 48, 3, 9, 36, 70, 58,
      40, 77, 33, 49, 61, 60, 38, 43, 20, 53, 87, 15, 75, 97, 22, 92, 76, 25,
      44, 98, 14, 52, 65, 5, 83, 90, 89, 49, 73, 71, 41, 27, 11, 8, 55, 29, 64,
      78, 24, 51, 68, 69, 35, 59, 39, 66, 16, 56, 60, 57, 78, 10, 94, 34, 80,
      91, 30, 77, 4, 85, 32, 82, 28, 48, 62, 72, 74, 46, 53, 37, 62, 65, 86, 74,
      26, 93, 45, 38, 13, 0, 17, 95, 98, 67, 43, 23, 73, 2, 41, 21, 34, 65, 19,
      50, 28, 99, 18, 66, 33, 96, 30,
    ],
    30
  )
); // 2
console.timeEnd("Array Performance Test");

맨앞에 7을 검색했을때

 

맨뒤에 30을 검색했을때

 

맨앞의 7의 숫자를 검색하는것보다. 맨뒤에있는 30을 검색한다면 7.076ms -> 7.503ms (밀리초) 정도 걸린다.

 

 

 

배열 삽입

 

또한 배열에 요소를 삽입하거나 삭제하는 경우, 배열 요소를 연속적으로 유지하기 위해 요소를 이동시켜야 하는 단점도 있다.

 

// 배열 크기와 push(), unshift() 시간 차이 비교 함수
function measurePushUnshiftTime() {
  const arraySize = 1000000; // 배열 크기 설정 (1백만)
  const array = generateArray(arraySize); // 배열 생성

  // 배열 맨 뒤에 값을 추가하는 시간 측정 (push)
  let startTime = performance.now();
  array.push(9999999); // 배열의 맨 뒤에 값 추가
  let endTime = performance.now();
  console.log(`push() (맨 뒤에 추가) 시간: ${endTime - startTime} ms`);

  // 배열 맨 앞에 값을 추가하는 시간 측정 (unshift)
  startTime = performance.now();
  array.unshift(9999999); // 배열의 맨 앞에 값 추가
  endTime = performance.now();
  console.log(`unshift() (맨 앞에 추가) 시간: ${endTime - startTime} ms`);
}

// 배열 생성 함수
function generateArray(count) {
  const result = [];
  for (let i = 0; i < count; i++) {
    result.push(i);
  }
  return result;
}

// 함수 실행
measurePushUnshiftTime();

push() 맨뒷자리부터추가되는 메서드, unshift() 맨앞자리 pop되는 메서드

 

 

맨뒤에 요소를 추가하는것보다. 맨앞에 추가한다면 기존에있던 배열들이 한칸씩 이동하므로 0.0047ms -> 0.4485ms  정도 더걸리는것을 볼수있다.

 

 

자바스크립트 배열

자바스크립트 배열은 일반적인 배열과 다르다. 배열의 요소를 위한 각각의 메로리공간은 동일한 크기를 갖지않아도되며 연속적으로 이어져있지않을수도있다. 배열의 요소가 연속적으로 이어져 있지 않는 배열을 희소배열이라 한다.

 

console.log(Object.getOwnPropertyDescriptors([1, 2, 3]));

 

getOwnPropertyDescriptors 배열의 속성들

자바스크립트 배열은 일반 배열의 동작의 흉내된 특수한 객체이다.

인데스를 프로퍼티 키로 갖으며 length프로퍼티를 갖는 특수한 객체이다. 그렇기때문에 모든 값은 객체의 프로퍼티 값이 될수있으므로 어떤 타입의 값이라도 배열의 요소가 될 수 잇다.

 

const arr = [
  'string',
  10,
  true,
  null,
  undefined,
  NaN,
  Infinity,
  [ ],
  { },
  function () {}
];

 

 

 

일반 배열 추가삭제 vs 자바스크립트 추가삭제

1. 자바스크립트 배열은 객체로 구현되어 있다

자바스크립트의 배열은 객체로 구현됩니다. 배열의 인덱스(0, 1, 2, ...)는 객체의 **속성(property)**와 유사한 방식으로 관리되며, 배열의 값은 값으로 저장됩니다. 객체는 자바스크립트 엔진에서 매우 최적화되어 있어, 배열의 크기 조정이나 요소 추가가 매우 빠르게 처리됩니다.

배열에 요소를 추가할 때 배열의 크기가 자동으로 확장되며, 배열의 인덱스를 단순히 증가시키는 방식으로 처리되기 때문에 성능이 빠르게 나타날 수 있습니다. 이와 달리, 고정 크기의 배열에서는 배열의 크기를 초과하는 요소를 추가하려면 새로운 배열을 할당하고 기존 데이터를 복사하는 과정이 필요하므로 시간이 더 많이 걸릴 수 있습니다.

 

 

 

 

 

필자는 java코드를 보고 javascript로 변환하려할때 배열의 관리방법에대한 차이를 모르고 구현하려고하다가 이글을 쓰게되었다. 

이글로 배열의 특징과, javascript가 가지고있는 배열의 장점, 구성요소, 추가시 진행되는 과정들을 알게되었다.