array(배열)

Aaron·2020년 12월 15일
0

자료구조

목록 보기
1/1
post-thumbnail

일반적인 array



출처: PoimaWeb

정의

  • 위키
    • 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조
    • 일반적으로 같은 종류의 데이터들이 순차적으로 저장된다
    • 같은 타입의 데이터들이 동일한 크기의 메모리 공간에 빈틈없이 연속적으로 나열된 자료 구조 (i.o 밀집 배열)

장점

  • 동일한 크기의 요소들이 빈틈없이 연속적으로 나열되어 있으므로
    아래와 같이 단 한 번의 연산을 통해 임의의 요소에 접근할 수 있다.

임의의 요소의 메모리 주소 = 배열의 시작 메모리 주소 + 인덱스 * 요소들의 바이트 크기

  • 예를 들어, 인덱스가 0인 시작 요소의 메모리 주소가 1000이고, 요소들의 바이트 크기가 8인 경우를 생각해보자.

    • 인덱스가 0인 요소의 메모리 주소 = 1000 + 0 * 8 = 1000
    • 인덱스가 1인 요소의 메모리 주소 = 1000 + 1 * 8 = 1008
    • 인덱스가 2인 요소의 메모리 주소 = 1000 + 2 * 8 = 1016
  • 위와 같은 이유로 인덱스를 통해 임의의 요소에 접근하는 것은 매우 효율적이고 고속으로 이루어진다 - O(1)

단점

  • 정렬되지 않은 배열에서 특정 값을 탐색하는 경우, 처음부터 원하는 값을 찾을 때까지 선형 탐색(linear search)을 해야 한다 - O(n)
const linearSearch = (array, target) => {
  for(let i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
};
  • 배열에 특정 요소를 삽입하거나 삭제하는 경우, 요소들이 빈틈없이 연속적으로 나열되도록 하기 위해 특정 요소 외 나머지 요소들을 전부 이동시켜야 한다.


출처: PoimaWeb

Javascript의 array


정의

  • MDN
    • 프로토타입으로 탐색과 변형 작업을 수행하는 메서드를 갖는, 리스트와 비슷한 객체.
    • 배열의 길이와 요소의 자료형이 고정되어 있지 않다. (i.e 요소들이 연속적으로 이어져 있지 않을 수도 있으며, 각 요소들의 메모리 공간은 동일한 크기가 아니어도 된다)
    • 위 일반적인 배열의 동작을 흉내낸 특수한 list-like object다.
    • 아래 예시에서 알 수 있듯, 배열의 인덱스는 사실 property key이고
      length property를 가지며
      요소의 값은 property value다.
      또한 length property를 갖는다.
      자바스크립트 객체의 property value는 어떤 타입도 될 수 있으므로
      어떤 타입의 값이든 배열의 요소가 될 수 있다.
console.log(Object.getOwnPropertyDescriptors([1, 2, 3]));

/*
{
  '0': { value: 1, writable: true, enumerable: true, configurable: true },
  '1': { value: 2, writable: true, enumerable: true, configurable: true },
  '2': { value: 3, writable: true, enumerable: true, configurable: true },
  length: { value: 3, writable: true, enumerable: false, configurable: false }
}
*/

장점

  • 자바스크립트의 배열은 해시 테이블로 구현된 객체이다. 따라서 특정 요소를 탐색 삽입, 삭제하는 경우 일반적인 배열에 비해 효율적이다.

단점

  • 위와 같은 이유로 인덱스를 통한 배열 요소에의 접근은 일반적인 배열에 비해 성능적인 면에서 느리다.
    (그러나 최신 자바스크립트 엔진에서는 이와 같은 단점을 극복하기 위해 배열을 일반적인 객체와 구분하여 보다 배열처럼 동작하도록 최적화하여 구현하였다.)

참조

profile
Maker를 지향하는 웹 개발자입니다.

0개의 댓글