선형 자료구조 - 배열(Array)

MyeonghoonNam·2021년 6월 15일

자료구조

목록 보기

2/9

배열의 형태

연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다.

배열의 특징

연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다.
크기가 고정적이고 공간이 낭비되거나 재할당이 필요할 수 있다.
- 자바스크립트 처럼 대부분의 스크립트 언어는 배열의 크기를 동적으로 변경할 수 있다.
논리적인 저장 순서와 물리적(메모리) 저장 순서가 일치한다.
인덱스를 사용해 특정 원소에 접근이 가능하다.(Random Access => 비순차적 접근)
메모리는 배열이 선언될 때(컴파일 할 때) Stack영역에 할당한다.

배열의 시간복잡도

배열의 맨 뒤에 데이터를 삽입 / 삭제 하는 경우 : O(1)

배열의 끝 주소 = 시작 주소 + (1칸이 차지하는 주소 X 배열 길이)

위 수식을 통해 배열의 끝 주소를 찾고, 배열의 길이를 1 증가시킨 후, 추가할 원소 데이터를 저장하면 된다.

그러므로 시간복잡도는 O(1)이다.

위에서 알아본 배열의 가장 끝에 원소 추가하기와 비슷하게 배열의 끝 주소를 찾고, 배열의 길이를 1만큼 줄이면 되므로 시간복잡도는 O(1)이다.
배열의 맨 뒤를 제외한 경우의 위치에 데이터를 삽입 / 삭제 하는 경우 : O(N)

임의의 위치에 원소를 새로 추가해서 끼워넣으려면 그 뒤에 존재하는 모든 원소들을 한 칸씩 뒤로 밀어야 한다.

뒤로 미는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 밀어야 한다면 O(1XN) = O(N)이 걸리게 된다.

추가하려는 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 뒤로 밀어내는 연산의 수도 줄어든다.

평균적으로 N/2 개의 원소를 뒤로 밀어내야 하므로 시간복잡도는 O(N/2) = O(N)이다.

삭제 연산도 임의의 위치에 원소를 추가하는 것과 비슷하게 수행된다.

임의의 위치에 있는 원소를 삭제하면 그 뒤에 존재하는 모든 원소들을 한 칸씩 앞으로 당겨와야 한다.

왜 굳이 앞으로 당겨와야 할까?

배열의 정의 상 배열은 메모리의 데이터(원소)를 연속하게 배치한 자료구조이기 때문이다.

앞으로 당기는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 앞으로 당겨야 한다면 O(1XN) = O(N)이 걸리게 된다.

제거하려는 원소의 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 앞으로 당기는 연산의 수도 줄어든다.

반대로 제거하려는 위치가 배열의 처음과 가까울수록 그 뒤에 존재하는 원소의 개수가 많아져 앞으로 당기는 연산의 수도 늘어난다.

평균적으로 N/2 개의 원소를 앞으로 당겨야 하므로 시간복잡도는 O(N/2) = O(N)이다.
배열의 특정 위치 데이터를 탐색하는 경우 : O(1)

메모리 상에 일렬로 나열되어 있으니 배열의 시작 주소에서 k칸 만큼 더하면 k번째 원소를 찾을 수 있다.

k번째 원소의 위치 = 시작주소 + (1칸이 차지하는 주소 X k)

단순 사칙연산 계산에 의해 O(1)만에 k번째 원소를 찾을 수 있다.

장점

인덱스를 통해 찾으려는 원소에 O(1)의 시간복잡도 만에 빠르게 접근할 수 있다.
- 자료구조의 크기가 클수록 더 강력한 장점이다.
연속된 메모리 공간에 존재하기 때문에 관리가 편하다.

단점

새로운 원소의 삽입 / 삭제의 경우 O(N)의 시간복잡도가 걸려 느리다.
연속된 메모리 상에 원소들이 존재하므로 처음 배열을 선언한 크기만큼 데이터를 저장하지 않는다면 메모리 낭비가 발생한다.
연속적인 메모리 할당이 필요하여 메모리 공간을 많이 사용하게 될 수 있다.

배열을 사용하기 좋은 경우

데이터의 수가 확실하게 정해진 경우.
데이터의 삭제와 삽입이 적은 경우.
데이터의 탐색이 많이 이루어지는 경우.

구현 - javaScript

javaScript는 내장된 배열 메소드들이 많지만 메소드들을 사용하지 않고 구현해보았다.
javaScript에서의 배열은 배열의 크기가 가변적이라 배열의 밀고 당기는 메소드를 구현할 필요가 없으나 다른 언어의 관점에서 구현해보았다.

'use strict';

class Array {
  constructor() {
    // 배열의 빈 공간을 제외한 데이터들의 개수
    this.length = 0;
    this.data = [];
  }

  // 배열의 원소 탐색
  // 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다.
  get(idx) {
    console.log(this.data[idx]);
  }

  // 배열의 맨 뒤에 원소 추가
  push(value) {
    this.data[this.length] = value;
    this.length++;
  }

  // 배열의 맨 뒤 원소 제거
  pop() {
    const popValue = this.data[this.length - 1];

    delete this.data[this.length - 1];
    this.length--;

    return popValue;
  }

  // 배열의 맨 앞 원소 추가
  unshift(value) {
    this.pushArray(0);
    this.data[0] = value;
    this.length++;
  }

  // 배열의 맨 앞 원소 제거
  shift() {
    const shiftValue = this.data[0];

    delete this.data[0];

    this.pullArray(0);
    this.length--;

    return shiftValue;
  }

  // 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 추가
  insert(idx, value) {
    this.pushArray(idx);
    this.data[idx] = value;
    this.length++;
  }

  // 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 제거
  delete(idx) {
    const deleteValue = this.data[idx];

    delete this.data[idx];

    this.pullArray(idx);

    this.length--;

    return deleteValue;
  }

  // 배열의 데이터를 뒤로 밀기
  pushArray(idx) {
    for (let i = this.length - 1; i >= idx; i--) {
      this.data[i + 1] = this.data[i];
    }
  }

  // 배열의 데이터를 앞으로 당기기
  pullArray(idx) {
    for (let i = idx; i < this.length; i++) {
      this.data[i] = this.data[i + 1];
    }

    delete this.data[this.length - 1];
  }
}

const myArray = new Array();

myArray.push(1);
console.log(myArray);

myArray.push(2);
console.log(myArray);

myArray.push(3);
console.log(myArray);

myArray.delete(1);
console.log(myArray);

myArray.pop();
console.log(myArray);

myArray.push(4);
console.log(myArray);

myArray.insert(1, 5);
console.log(myArray);

myArray.unshift(6);
console.log(myArray);

myArray.shift();
console.log(myArray);