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

MyeonghoonNam·2021년 6월 15일
0

자료구조

목록 보기
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);
  • 결과



참고자료

profile
꾸준히 성장하는 개발자를 목표로 합니다.

0개의 댓글