[Topic #자료구조 01] Array를 이용한 List 구현 with JavaScript

첫 번째 토픽 키워드 주제는 자료구조입니다.

JavaScript 언어를 활용하여 Array를 이용한 List 구현을 해보겠습니다.

 

구현을 시작하기 전에 먼저 간단히 Array와 List를 비교하겠습니다.

 

Array는 보통 '정적인 배열이다' 라고 해서 처음부터 사이즈가 정해져 있는 크기의 배열입니다.

그래서 만약 처음에 사이즈를 100으로 잡아놓은 배열이 꽉차게 되면 더 이상 요소를 넣을 수 없게 됩니다.

이때 요소를 더 넣게(Push) 된다면 그 배열이 가지고 있는 사이즈가 넘쳐서 오버 플로 (overflow) 라고 합니다.

만약 요소가 하나도 없는 배열에서 요소를 빼는(Pop) 연산을 한다면 그것은 언더 플로 (underflow)가 됩니다.

스택을 이용한 연산이었다면 우리가 많이 들어본 스택 오버 플로, 스택 언더 플로가 되는 것입니다.

(스택 오버 플로라는 해외 개발자 질의응답 및 구인구직 사이트가 바로 이 어원에서 나온 것입니다.)

 

List는 Array와는 반대로 '동적인 배열이다' 라고 보시면 됩니다.

'동적이다' 라는 말은 처음부터 배열의 사이즈를 잡아놓지 않고 계속 push 하거나 pop 연산을 수행할 수 있는

자료구조입니다. 따라서 정적인 Array와는 다르게 상당히 유연하며 메모리 상에서도 여러 요소가 같은 곳에

위치하지 않고 서로 떨어져 있어도 링크라는 개념을 활용하면 동적으로 확장시키거나 축소시킬 수 있습니다.

 

저는 다음과 같이 ES6 클래스를 이용해서 Array를 이용한 List를 구현했습니다.

 

// Array를 이용한 List 구현

// ES6 클래스
class List {
  constructor(size) {
    this.data = new Array(size);
    this.cnt = 0;
  }

  // 시간 복잡도: O(n)
  insertHead(value) {
    for (let i = this.cnt; i > 0; i -= 1) {
      this.data[i] = this.data[i - 1];
    }
    this.data[0] = value;
    this.cnt += 1;
  }

  // 시간 복잡도: O(1)
  insertTail(value) {
    this.data[this.cnt] = value;
    this.cnt += 1;
  }

  // 시간 복잡도: O(n)
  deleteHead() {
    for (let i = 0; i < this.cnt; i += 1) {
      this.data[i] = this.data[i + 1];
    }
    this.cnt -= 1;
  }

  // 시간 복잡도: O(1)
  deleteTail() {
   // this.data.pop()
    this.cnt -= 1;
  }

  // 시간 복잡도: O(1)
  countData() {
    return this.cnt;
  }

  printData() {
    let result = '';
    for (let i = 0; i < this.cnt; i += 1) {
      result += `${this.data[i]} `;
    }
    return result;
  }
}

const list = new List(100);
list.insertHead('A');
list.insertHead('B');
list.insertTail('C');
list.insertTail('D');
list.deleteHead();
list.deleteTail();

console.log(list.printData());
console.log(list.countData());

 

과거에 클래스라는 문법이 없었을 때는 생성자 함수를 이용하여 객체의 인스턴스를 생성했습니다.

하지만 생성자 함수를 활용하게 되면 생성자 함수에 해당하는 프로토타입과 인스턴스 계열의 프로토타입

2가지로 구분이 되어 코드를 설계하고 구현하기가 쉽지 않았습니다.

ES6에서 클래스라는 문법이 나오고 상당히 편리해졌습니다.

 

그래서 저는 객체 지향 프로그래밍의 Modularity (모듈화) 특성을 이용해서 클래스를 하나 만들고

그 안에 여러 연산 작업들에 대한 함수들을(메서드) 정의했습니다.

 

자료구조를 학습하실 때 ADT (Abstract Data Type) 이라는 개념을 많이 보게 됩니다.

직역하면 추상 자료형 이라는 뜻인데 전체적인 틀 (연산/기능 목록)만 작성하면서

각각의 연산에 대한 세부 구현은 하지 않고 메서드(함수)만 정의해 놓은 것입니다.

 

그래서 항상 코드를 짜실 때 하나 하나 필요한 기능(함수) 위주로 구현하셔도 좋지만,

전체적인 필요한 기능들을 먼저 ADT 라는 개념을 활용하여 쭉 함수 정의만 나열하고

세부 구현을 하나씩 들어가셔도 좋을 거라 생각합니다.

(사실 개발에 대한 본인 취향 차이입니다.)

 

우선 Array는 처음에 사이즈를 정해야 하므로 저는 new 라는 객체 생성 연산자를 이용하여

List 라는 클래스로부터 생성자 함수를 호출할 때 size를 매개값으로 넘겼습니다.

그렇게 되면 사이즈가 100 크기의 빈 배열이 하나 만들어지게 됩니다.

그리고 cnt 변수로도 생성자 함수 내에서 0으로 초기화 했습니다.

 

insertHead(value) 메서드에서는 우선 배열의 맨 앞 (head)에 요소 하나를 넣어야 하므로

기존에 있던 배열의 요소들은 뒤로 한 칸씩 다 밀어야 합니다. (Right-shift by 1)

그래서 맨 끝에 있던 요소부터 한 칸씩 뒤로 다 밀고 맨 앞의 자리를 하나 만들어서

그곳에 value를 넣고 cnt의 값을 하나 추가했습니다.

 

insertTail(value) 메서드에서는 cnt 변수로 선언 해놓은 값을 인덱스로 하여 맨 끝에 요소를 추가하면 됩니다.

이후 cnt를 하나 추가합니다.

 

deleteHead() 메서드는 맨 앞의 요소를 제거하면 자리가 비어있게 되므로 남은 요소들은

앞으로 한 칸씩 또 땡겨야 합니다. (전진) 그래서 앞에 있는 요소부터 한 칸씩 앞으로 땡겼습니다.

여기서 주의해야 할 것은 뒤쪽의 원소부터 앞으로 땡기게 되면 겹치게 되서 원하는 결과를 얻을 수 없습니다.

마찬가지로 insertHead(value) 할 때도 맨 뒤의 요소부터 뒤로 한 칸씩 밀어 놓아야 합니다.

앞쪽 요소부터 뒤로 밀게 된다면 그 다음 요소를 뒤로 밀때 이전 결과가 누적되서 겹치게 되어

원하는 결과를 얻을 수 없습니다.

 

deleteTail() 메서드는 맨 뒤의 cnt 변수만 하나 줄이면 됩니다.

(사실 pop() 를 사용하여 제거하고 이후 cnt를 1 빼면 되지만,

cnt 변수만 가지고도 잘 활용할 수 있어서 주석으로 처리 했습니다.)

 

printData() 메서드는 배열의 요소들을 한 칸씩 띄워쓰기 하면서 출력되도록 하기 위해 만들었습니다.

그래서 시간 복잡도가 O(n) 이 나와서 굳이 그럴 필요 없지만 출력되는 것을 편하게 보기 위함이었습니다.

 

다른 메서드들의 시간 복잡도는 주석으로 다 기입했습니다.

 

이와 같이 Array를 이용해서 List를 구현해보았습니다.

 

자료구조 배열의 기본적인 개념이라서 한번 숙지해두시면 좋을 것 같습니다.