2.3Demo-Classes and Generics

이번 포스트에선 Singly Linked List를 타입스크립트로 구현해보자. Singly Linked List에 대한 보다 자세한 설명은 해당 링크에 있지만, 간단히 요약하면 자신의 다음 노드에 대한 포인터를 가지고 있는 노드들로 구성된 리스트이다.

노드와 리스트 정의

우선 노드와 노드들로 이루어진 리스트 클래스를 정의해보자. 리스트는 루트 노드의 정보와 길이에 대한 정보가 필요하다. 루트 노드 정보가 있어야 해당 루트 노드에서 다음 노드에 대한 정보를 얻을 수 있을 것이며, 길이 정보가 없다면 총 길이를 세는 빠른 방법이 없기 때문에 단일 연결 리스트에선 총 길이 정보를 노드가 추가될때/제거될때 계산해 따로 저장한다.

typescript
class ListNode {}

class LinkedList {
  private root?: ListNode;
  private length = 0;
}

const list = new LinkedList();

add 메소드 추가

리스트에 새로운 노드를 추가하는 add라는 메소드를 만들어보자. 우선, 각 node는 next라는 속성을 가지고 있고 해당 속성이 다른 node를 가리켜야 리스트를 구성할 수 있을 것이다. 또, 각 node는 값을 가지고 있어야 한다.

이 값의 타입은 뭐가 되어야할까? 숫자가 될 수도 있고, 문자열이 될 수도 있지만, 리스트 자체는 똑같은 타입으로 유지하고자 한다. 이럴 때 쓸 수 있는 것이 Generic이다.

typescript
class ListNode<T> {
  next?: ListNode<T> // 마지막 노드의 경우 next가 없음

  constructor(public value: T){}
}

add 메소드는 LinkedList 클래스에 속해야 한다. 루트 노드가 없다면 새로 받은 값을 노드로 만들고 루트 노드로 만들면 되고, 루트 노드가 있다면 리스트의 맨 끝으로 간 뒤 새로 받은 값을 노드로 만들어 맨 끝 노드의 next 속성이 새 노드를 가리키게 하면 된다.

typescript
class LinkedList<T> {
  private root?: ListNode<T>;
  private length = 0;

  add(value: T){
    const node = new ListNode(value);
    if(!this.root){
      this.root = node;
    } else {
      let current = this.root;
      while (current.next){
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }
}

다만, 이렇게 while 루프를 만드는 것은 노드가 길어질수록 비효율적이다. 차라리 맨 마지막 노드에 대한 정보를 리스트에 저장해두는 것이 좋다. 이렇게 저장해둘 경우, 만약 새로운 노드가 추가되면 기존 tail의 next에 새 노드를 할당하고 리스트의 tail 노드가 새 노드를 가리키게 하는 식으로 효율적으로 add 메소드를 구현할 수 있다.

typescript
class LinkedList<T> {
  private root?: ListNode<T>;
  private tail?: ListNode<T>
  private length = 0;

  add(value: T){
    const node = new ListNode(value);
    if(!this.root || !this.tail){
      this.root = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
      }
    this.length++;
  }
}

데이터 접근하기

이렇게 만든 리스트의 데이터를 조회해보자. 간단한 메소드들을 추가할 수 있다.

typescript
class LinkedList<T>{
  // ...

  getNumberOfElements(){
    return this.length;
  };

  print(){
    let current = this.root;
    while(current){
      console.log(current.value);
      current = current.next;
    }
  }
}

const numberList = new LinkedList<number>();

numberList.add(10);
numberList.add(5);
numberList.add(3);

console.log(numberList.getNumberOfElements()) // 3
numberList.print(); // 10 5 3