자료구조
배열(Array)
웜블
2021. 12. 21. 22:24
개요
index(번호)와 그에 대응하는 데이터로 이루어진 순차적인 자료구조
특징
- 일반적인 배열(다른 프로그래밍 언어의 배열)
- 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조
- 크기가 고정
- 배열의 요소는 같은 타입이며, 연속적으로 인접
- 물리적으로도 즉, 메모리 상에서도 연속적으로, 순차적으로 저장된다.
- 자바스크립트의 배열
- 각 요소를 위한 메모리 공간의 크기는 동일하지 않아도 된다.
- 각 메모리 공간은 연속적으로 이어지지 않아도 된다. (희소 배열, sparse array)
- 일반적인 배열의 동작을 흉내내어 만든 특수 객체
장점
- 일반 배열
- 임의의 요소로 접근하는 과정(random access)이 매우 빠르고 효율적이다. index를 통해 단 한번의 연산으로 접근 가능하기 때문이다.
- 조회가 많은 시스템에서 유리(예: 대학교 학생 관리 시스템 - 변동이 적고 조회를 자주함)
- 접근 대상 메모리 주소 = 배열 시작 메모리 주소 + index * 요소 바이트 수
- 자바스크립트의 배열
- 특수한 객체이기 때문에 배열의 요소는 사실 이 객체의 프로퍼티 값이다. 자바스크립트에서는 모든 값이 프로퍼티의 값이 될 수 있기 때문에 타입의 제한 없이 배열의 요소가 될 수 있다.
- index 접근이 아닌 특정 요소 자체를 탐색하거나 요소 삽입, 삭제의 경우에는 일반적인 배열보다 빠른 성능을 가진다.
단점
- 일반 배열
- 요소의 삭제, 추가의 성능이 낮다. 배열의 요소를 연속적으로 유지해야하고 배열에 미리 할당된 메모리 크기가 있기 때문에 그 이상의 요소가 추가된다면 비효율적인 resizing 과정을 거쳐야한다. (더 큰 메모리 공간을 생성 후 기존 데이터를 복사하여 이동하고 그 뒤로 추가 요소를 삽입한다)
- 자바스크립트의 배열
- index로 특정 요소에 접근하는 성능이 일반 배열에 비해 낮다. 다만, 일반 객체보다는 2배정도 빠르다. 이는 모던 자바스크립트 엔진을 구현할 때 일반 객체와 구별하여 더 배열처럼 동작하도록 최적화한 결과이다.
기능별 시간복잡도
일반 객체
- 접근
- O(1), index를 알고 있다면 배열의 시작 메모리 주소에 인덱스*요소의 메모리 크기로 1번의 연산으로 접근 가능하다.
- 검색
- O(n), index를 모른다면 하나씩 요소를 탐색할 수 밖에 없다. 최악의 경우 모든 요소를 다 검사해야 한다.
- 추가, 제거
- 빈 공간이 있음을 전제로 접근
- O(1), index로 접근할 경우
- O(n), 해당 index를 모를 경우
자바스크립트
- push, pop
- O(1), 배열의 맨 끝에 요소를 추가, 제거
- unshift, shift
- O(n), 배열의 맨 앞에 요소를 추가, 삭제하므로 원래 있던 요소들의 index를 변경해야한다.
- splice
- O(n), 특정 위치에 요소를 제거, 교체, 삽입하는 기능. 해당 위치(index) 이 후의 요소들의 index를 변경해야 하기 때문에 적용 범위가 중요하다. 최악의 경우는 맨 앞에 요소를 추가하는 경우.
- slice
- O(n), 배열의 일정 범위 안의 요소들을 복사하여 새로운 배열을 반환. 범위에 따라서 시간 증가.
- map, forEach, filter
- 전체 배열을 순회하며 변환(mutation), 필터(filter) 등을 수행한다.
- 내부에서의 동작에 따라 O(n), O(n2), ... 으로 기하급수적으로 시각복잡도가 증가한다.
출처