Typescript로 구현한 Linked list

타입스크립트 숙련도를 높이기 위해 자료구조/알고리즘을 구현하고 있습니다. 더 좋은 방법 또는 틀린 부분을 알려주시면 진심으로 감사드립니다!!

Linked list(이하, 링크드 리스트)는 대표적인 자료구조이며 다른 알고리즘(스택, 큐,...)에도 유용하게 활용되는 자료구조이다. 배열처럼 고정된 크기가 아닌 동적인 크기를 가지며 배열에 비해서 삽입/삭제에  큰 연산이 필요 없지만 탐색의 경우  \(O(N)\) 시간 복잡도를 가지는 알고리즘이다. 크기를 알 수 없고,  탐색보단 삽입 삭제가 자주 일어나는 경우 유용한 알고리즘이다.

class LinkedListNode<T> {
  val: T;
  next: LinkedListNode<T> | null;
  prev: LinkedListNode<T> | null;

  constructor(val: T) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

링크드 리스트는 단방향 링크드 리스트와 양방향 링크드 리스트가 있는데, 차이는 연결이 단방향으로 이뤄졌는가, 양방향으로 이뤄졌는가에 차이가 있다. 추가적으로 꼬리 노드가 머리 노드를(또는 꼬리 노드와 머리 노드가 연결된 경우) 원형 링크드 리스트라고 해서 순환하는 링크드 리스트로 구현될 수 있다. 원형 링크드 리스트는 라운드 로빈 스케쥴링처럼 단방향으로 순환하는 구조에 유용한다.

위 코드는 링크드 리스트를  이루는 노드의 나타내며 값(val), 다음, 이전 노드(next, prev)를 가리키는 포인터로 구성된다. 생성된 시점에선 next, prev는 어떤 노드를 가리킬지 정해지지 않았으므로 null로 초기화된다.

  pushBack(value: T): void {
    if (!this.head) {
      this.init(value);
      return;
    }
    const newNode = new LinkedListNode<T>(value);
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }

링크드 리스트의 대표적인 행위는 삽입과 삭제 그리고 탐색인데 먼저 삽입을 살펴보면 아래에서 4줄이 핵심이라 할 수 있다.

• 삽입할 새 노드를 생성한다.
• 마지막 노드(tail)의 다음에 새 노드를 연결한다.
• 연결된 새 노드의 prev에 직전의 마지막 노드를 연결한다.
• 마지막 노드(tail)를 추가된 새 노드가 되도록 갱신한다.

여기서 알 수 있듯 링크드 리스트는 양 끝쪽에 새로운 노드를 추가하는데 \(O(1)\)의 시간 복잡도를 가지고 삽입 또한 삽입할 위치의 노드로 이동하는 것 외에는 별다른 복사 연산이 필요 없다.

  popBack(): T {
    if (!this.head) {
      throw new Error("Empty list");
    }
    const result = this.tail.val;
    this.tail.prev.next = null;
    this.tail = this.tail.prev;
    return result;
  }

다음으로 핵심적인 기능인 pop은 head, tail이 가리키는 값을 가져오며 제거하는 작업을 수행한다. 물론 중간에 있는 노드의 값을 가지고 오거나, 삭제하는 방법도 쉽게 구현할 수 있다. 노드를 제거할 땐 단순히 tail을 옮기는 거뿐만 아니라 제거될 노드와 연결된 지점을 제거할 필요가 있다. 이 경우 밑에서 3번째 줄이 그 역할을 하는데 이렇게 제거해주면 이후 자바스크립트의 GC가 제거된 노드에 도달할 수 없다고 판단되면 메모리 해체가 이뤄지게 된다.

---

class LinkedListNode<T> {
  val: T;
  next: LinkedListNode<T> | null;
  prev: LinkedListNode<T> | null;

  constructor(val: T) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

interface List<T> {
  get(index: number): T;
  size(): number;
}

interface MutableList<T> extends List<T> {
  pushBack(value: T): void;
  pushFront(value: T): void;
  popBack(): T;
  popFront(): T;
}

class LinkedList<T> implements MutableList<T> {
  private head: LinkedListNode<T>;
  private tail: LinkedListNode<T>;

  private constructor() {}

  static list<T>(): List<T> {
    return new LinkedList<T>();
  }

  static mutableList<T>(): MutableList<T> {
    return new LinkedList<T>();
  }

  private init(value: T) {
    this.head = new LinkedListNode<T>(value);
    this.tail = this.head;
  }

  pushFront(value: T): void {
    if (!this.head) {
      this.init(value);
      return;
    }
    const newNode = new LinkedListNode<T>(value);
    this.head.prev = newNode;
    newNode.next = this.head;
    this.head = newNode;
  }

  pushBack(value: T): void {
    if (!this.head) {
      this.init(value);
      return;
    }
    const newNode = new LinkedListNode<T>(value);
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }

  popBack(): T {
    if (!this.head) {
      throw new Error("Empty list");
    }
    const result = this.tail.val;
    this.tail.prev.next = null;
    this.tail = this.tail.prev;
    return result;
  }

  popFront(): T {
    if (!this.head) {
      throw new Error("Empty list");
    }
    const result = this.head.val;
    this.head.next.prev = null;
    this.head = this.head.next;
    return result;
  }

  get(index: number): T {
    if (!this.head) {
      throw new Error("Empty list");
    }
    let p = index;
    let cur = this.head;
    while (p-- && cur.next) {
      cur = cur.next;
    }
    return cur.val;
  }

  size(): number {
    let size = 0;
    let cur = this.head;
    while (cur?.next != null) {
      cur = cur.next;
      size++;
    }
    return size;
  }
}