01. Array 배열의 정의와 구현(JS)

이 글은 개인 학습 차원에서 정리한 글입니다. 부정확한 부분에 대한 피드백은 항상 큰 도움이 됩니다.

들어가기

이번 글에서는 배열에 대해 알아보겠습니다.

배열에 대해 본격적으로 들어가기 앞서 array라는 단어가 도대체 언제 생겨난 단어인지 궁금해졌습니다. 어원사전을 살펴보니 14세기 중반에 전투를 앞둔 병사들을 정렬시키는 것을 put in order, arrange, get ready라 했습니다. 당시 유럽에서는 국가마다 areyer, arrdare 등 단어로 표현했는데, 이 단어는 라틴어 ad('to') + raed('ready')로 파생된 것으로 추측됩니다.

정라하자면 array라 하면 전쟁을 앞둔 용감한 군사들이 순서에 맞게 도열하는 장면을 떠올리면 되겠습니다.

Battle of Hohenfriedberg, The Prussian infantry advance, by Carl Röchling.

소개

정의

그렇다면 컴퓨터 공학에서는 array를 어떻게 정의할까요?

컴퓨터 공학에서, 배열은 요소들의 집합으로 구성된 데이터 구조다. 각 요소들은 인덱스 또는 키로 식별된다 - 위키피디아

배열은 인접 메모리 주소에 저장된 같은 형식의 데이터들을 모아놓은 것이다 - geeksforgeeks

어레이는 마치 완두콩과 같습니다. 알맹이(요소)들이 순서(인덱스)마다 하나씩 있기 때문입니다. - 나

사람마다 다른 정의를 내리고 있지만, array의 주요 특징을 살펴보면 아래와 같네요.

• 선형적(linear)
• 연속적(continuous)

장단점

그렇다면 배열은 어떤 장단점이 있길래 사용하는 것일까요?

배열의 장점은

1. lookup이 빠릅니다.
2. push와 pop이 빠릅니다
3. 순서대로 정리되어 있습니다.

배열의 단점으로는

1. insert, delete이 느립니다.
2. 정적 배열(static array)의 경우 메모리 크기가 고정(제한)되어 있습니다.

Big O

• lookup : O(1)
• push: O(1) or O(n)
• pop: O(1)
• insert: O(n)
• delete: O(n)

// a부터 g까지 데이터들이 모인 배열이 있습니다
const data = ['a', 'b', 'c', 'd', 'e'];

// indexing : O(1)
// - index를 알면 값을 알 수 있습니다
console.log(data[2]); // c

// push: O(1)
// - 뒤에 추가
data.push('f'); 
console.log(data); // [ 'a', 'b', 'c', 'd', 'e', 'f']

// unshift: O(n)
// - 앞에 추가 : 가장 앞에 요소를 추가하면 나머지 요소들은 한칸 씩 뒤로 밀려납니다
data.unshift('d');
console.log(data); // [ 'd', 'a', 'b', 'c', 'd', 'e' ]

// pop: O(1)
data.pop();
console.log(data); // [ 'a', 'b', 'c', 'd', 'e' ]

// splice: O(n)
data.splice(1, 0, 'middle');
console.log(data); // [ 'd', 'middle', 'a', 'b', 'c', 'd', 'e']

여기서 포인트는

• push의 경제성. push와 unshift 모두 요소를 추가한다는 점에서 유사한 기능을 가졌지만, 다른 요소들에 영향을 주지않는 push가 unshift보다 더 빠릅니다.
• splice를 어느 위치에 두냐에 따라 연산 속도는 달라지겠지만, 단순화하여 O(n)으로 표현했습니다.

정적 배열과 동적 배열

위에서 정적 배열은 메모리가 고정되어있다는 한계를 배열의 단점으로 짚었습니다. 이에 대해 좀 더 알아보겠습니다.

• 정적 배열(Static Array) : 배열을 만들 때 메모리의 크기를 미리 정한 배열
• 동적 배열(Dynamic Array) : 크기가 고정되지 않는 배열

두 유형를 구분하는 것은 결국 생성 시 크기가 미리 고정되어있냐 여부입니다.

배열에서
동적 배열(Dynamic Array)은 여유 공간이 없을 때 데이터가 추가될 경우, 자신을 복제하여 배열의 크기를 늘린 후 새 데이터를 추가합니다. 여기서 문제는 동적 배열에서 복제가 진행할 때 O(n) 시간이 걸리는 데, 데이터 추가 시 O(1)이 걸리는 정적 배열에 비해 비용이 높다는 점입니다. 다행히도 geeksforgeeks에 따르면 전체 배열을 삽입하는 경우가 아니면 O(n)이 걸릴 일은 드물다 합니다.

구현

마치 늠름한 군인들의 도열을 연상시키는 배열을 직접 구현해보겠습니다.

// 배열 구현하기

class Array {

  // 배열 길이와 데이터 초기값을 설정
  constructor() {
    this.length = 0;
    this.data = {};
  }

  // 인덱스 값으로 요소 찾기
  get(index) {
    return this.data[index]
  }

  push(value) {
    this.data[this.length] = value;
    this.length++;
    return this.length;
  }

  pop() {
    const itemToDelete = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return itemToDelete;
  }

  delete(index) {
    const itemToDelete = this.data[index];
    // index + 1 순서 요소들을 앞으로 당긴다
    for(let i = index; i < this.length; i++) {
      this.data[i] = this.data[i + 1];
    }
    // 중복되는 마지막 요소 1개는 제외한다
    delete this.data[this.length - 1];
    this.length--;
  }
}

const myArray = new Array();

myArray.push('USA');
myArray.push('Japan');
myArray.push('China');
myArray.push('Rusia');
myArray.push('UK');
console.log(myArray);
// Array { length: 5, data: { '0': 'USA', '1': 'Japan', '2': 'China', '3': 'Rusia', '4': 'UK' }}

myArray.pop();
console.log(myArray);
// Array { length: 4, data: { '0': 'USA', '1': 'Japan', '2': 'China', '3': 'Rusia' }}

myArray.delete(1);
console.log(myArray);
// Array { length: 3, data: { '0': 'USA', '1': 'China', '2': 'Rusia' } }

console.log(myArray.get(0)); // USA

Reference

• https://en.wikipedia.org/wiki/Array_(data_structure)
• https://www.geeksforgeeks.org/what-is-array/
• https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/