Binyard

Appearance

배열 (Array) ​

배열은 여러 개의 데이터를 순서대로 저장하는 자료구조로, 인덱스를 통해 빠르게 접근하고 여러 데이터를 효율적으로 관리할 수 있다.


일반적인 배열 ​

일반적인 배열은 같은 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조이다.

js
// 인덱스 0 1 2 3 4
// 값 1 2 3 4 5
[1, 2, 3, 4, 5];

배열은 각 요소를 순서대로 저장하고,
프로그램은 배열의 시작 위치를 기준으로 인덱스를 계산해 원하는 값에 접근한다.

배열은 시작 위치를 알고 있기 때문에, 원하는 인덱스의 값을 빠르게 가져올 수 있다.


배열의 인덱스 접근 ​

배열에서 특정 인덱스의 값을 읽는 작업은 배열의 길이와 상관없이 빠르게 처리된다.

js
const numbers = [10, 20, 30, 40, 50];

console.log(numbers[0]); // 10
console.log(numbers[3]); // 40

배열의 길이가 5이든 100이든, numbers[3]처럼 특정 인덱스에 접근하는 작업은 한 번에 처리할 수 있다.
따라서 배열의 인덱스 접근은 O(1)의 시간 복잡도를 가진다.
이처럼 배열은 읽기와 쓰기, 즉 특정 위치의 값을 참조하거나 수정하는 작업에서 좋은 성능을 보인다.


배열의 삽입과 삭제 ​

배열은 인덱스로 접근하는 작업은 빠르지만,
데이터를 삽입하거나 삭제하는 작업은 상대적으로 비효율적일 수 있다.


앞에 데이터 추가하기 ​

js
const numbers = [10, 20, 30];

numbers.unshift(0);

console.log(numbers); // [0, 10, 20, 30]

배열의 앞에 데이터를 추가하면 기존 요소들의 인덱스가 하나씩 뒤로 밀린다.
기존 요소들의 위치를 다시 조정해야 하므로 배열의 길이가 길수록 더 많은 작업이 필요하다.
따라서 배열의 앞에 데이터를 추가하는 작업은 보통 O(n)이다.


앞에서 데이터 삭제하기 ​

js
const numbers = [10, 20, 30];

numbers.shift();

console.log(numbers); // [20, 30]

배열의 첫 번째 요소를 삭제하면 뒤에 있던 요소들이 앞으로 한 칸씩 이동한다.
이 경우에도 배열의 길이에 따라 이동해야 하는 요소가 많아지므로 시간 복잡도는 보통 O(n)이다.


JavaScript 배열의 특징과 내부 구조 ​

JavaScript의 배열은 일반적인 배열처럼 인덱스를 사용해 값을 다룰 수 있다.

js
const numbers = [10, 20, 30];

console.log(numbers[0]); // 10

하지만 JavaScript 배열은 일반적인 배열보다 더 유연하게 동작한다.

js
const arr = [1, "hello", true, null];
console.log(arr); // [1, "hello", true, null]

일반적인 배열은 보통 같은 타입의 데이터를 연속된 메모리 공간에 저장하지만,
JavaScript 배열은 서로 다른 타입의 값도 함께 저장할 수 있다.


js
const numbers = [10, 20, 30];
numbers.push(40);
console.log(numbers); // [10, 20, 30, 40]

또한 배열의 길이를 동적으로 변경할 수 있다.


JavaScript 배열의 내부 최적화 ​

JavaScript 엔진은 배열의 형태에 따라 내부 최적화 방식을 달리한다.

  • 일반 배열(Fast Array): 0부터 순서대로 정수 인덱스를 가진 경우 → 일반적인 배열처럼 최적화
  • 해시 배열(Dictionary Mode): 인덱스가 듬성듬성 비어 있거나 일반적인 배열 형태에서 벗어나면,
    JavaScript 엔진은 배열을 객체에 가까운 방식으로 처리할 수 있다.
js
const fastArray = [10, 20, 30, 40]; // Fast Array로 최적화됨
const slowArray = [];
slowArray[0] = 10;
slowArray[1000] = 20; // Dictionary Mode로 처리됨

💡 push와 pop

JavaScript 배열에서는 push()와 pop()을 사용해 배열의 마지막에 데이터를 추가하거나 제거할 수 있다.

push() ​

push()는 배열의 마지막에 요소를 추가한다.

js
const numbers = [10, 20, 30];

numbers.push(40);

console.log(numbers); // [10, 20, 30, 40]

배열의 마지막에 데이터를 추가하는 작업은 보통 O(1)이지만, JavaScript 배열의 내부 용량을 초과하면 재할당으로 인해 O(n)이 될 수 있다. 여러 번 반복하면 평균적으로 O(1)이므로 amortized O(1)이다.


pop() ​

pop()은 배열의 마지막 요소를 제거한다.

js
const numbers = [10, 20, 30];

numbers.pop();

console.log(numbers); // [10, 20]

마지막 요소를 제거하는 작업도 다른 요소들의 인덱스를 다시 조정할 필요가 없기 때문에 보통 O(1)이다.


배열의 장단점 ​

장점 ​

배열의 가장 큰 장점은 인덱스를 통한 빠른 접근이다.

  • 특정 위치의 값을 읽거나 수정하는 작업은 O(1)의 시간 복잡도를 가진다.

단점 ​

배열은 데이터를 삽입하거나 삭제할 때 비효율적일 수 있다.

  • 앞/중간 삽입·삭제: O(n) 시간 복잡도 (요소 이동 필요)
  • 메모리 낭비: 동적 할당 시 미리 예약된 메모리가 있을 수 있음
  • 타입 유연성: JavaScript는 타입 혼용으로 인한 엔진 최적화 어려움

배열의 시간 복잡도 ​

배열에서 자주 사용하는 작업의 시간 복잡도는 다음과 같다.

작업예시시간 복잡도
인덱스로 접근arr[index]O(1)
인덱스로 수정arr[index] = valueO(1)
마지막에 추가push()평균 O(1)
마지막에서 삭제pop()O(1)
앞에 추가unshift()O(n)
앞에서 삭제shift()O(n)
중간에 추가/삭제splice()O(n)
전체 순회for, for...ofO(n)
값 찾기includes(), indexOf()O(n)