【TypeScript】LinkedListって何？簡単に実装してみた

LinkedListとは

LinkedList（双方向連結リスト）は、要素同士をリンク（参照）で繋いだ配列です。

双方向連結リストは要素の挿入や削除がリンクの付け替えだけで済むので、そういった処理はArrayより向いています。

一方、中央の要素を取得するにはリンクを辿っていかなければならず、そういった状況では遅くなってしまうらしいです。

参考

JavaScriptでは

JavaScriptにLinkedListは組み込まれていません。
そのため、使いたければライブラリを使うか自分で実装する必要があります。

この記事では、以下の目的でLinkedListクラスを実装してみます。

• 実装方法の勉強
• LinkedListとは何かの勉強
• 速度（パフォーマンス）や実用目的ではない

実装方針

• LinkedListクラスを実装する
• Iterator Helpersを使う
  • mapやforEachなどのメソッドの実装で使用
• LinkedListを反復可能（Iterable）として実装する
• TypeScriptで実装する

また、LinkedListの内部では、それぞれのノードを示すListNodeクラスを使用します。

LinkedListの詳細

LinkedListは型パラメータEを取ります。
これはリストの要素の型で、Arrayの型パラメータと似たような役割を持ちます。

今回実装するLinkedListのメソッド群はこちらです。

• constructor: コンストラクタ
  • 反復可能オブジェクトからLinkedListを作れるようにする
• push, pop, unshift, shift: 要素を追加/削除する
• map, filter, find, reduce, forEach: よく使いそうなやつ
  • Iterator Helpersの力を借りる

ListNodeについて

ListNodeは型パラメータEを取ります。
これはLinkedList<E>と同じものが入ります。

また、3つのプロパティを持ちます。
各プロパティの意味はこちらです。

• element: 保管したい要素、E型
• next: 次の要素へのリンク、ListNode<E>型
• next: 前の要素へのリンク、ListNode<E>型

これらはgetter / setterを使わずに実装します。

実装

このように実装してみました。

class ListNode<E> {
  constructor(
    public readonly element: E,
    public next: ListNode<E> | null,
    public prev: ListNode<E> | null,
  ){}
}

class LinkedList<E> implements Iterable<E, void, E> {
  private _head: ListNode<E> | null = null;
  private _last: ListNode<E> | null = null;

  /** ListNodeでループするほうのイテレーター */
  private *listNodeIterator(): Generator<ListNode<E>, void, ListNode<E>> {
    let currentNode = this._head
    while (true) {
      if(currentNode === null) return
      yield currentNode
      currentNode = currentNode.next
    }
  }

  /** headがnullなら更新する */
  private ifNullUpdateHead(element: ListNode<E>) {
    if(!this._head) this._head = element
  }

  /** lastがnullなら更新する */
  private ifNullUpdateLast(element: ListNode<E>) {
    if(!this._last) this._last = element
  }

  /** lastとheadの整合性チェック */
  private checkLastAndHead() {
    // prev / nextのチェック
    if (this._head) this._head.prev = null
    if (this._last) this._last.next = null
    // どちらかがnullならもう片方もnull
    if (this._head === null) this._last = null
    if (this._last === null) this._head = null
  }

  constructor(init?: Iterable<E>) {
    if(!init) return

    const first = Iterator.from(init).next()
    if(first.done) return
    this._head = new ListNode(first.value, null, null)
    this._last = this._head

    for (const elem of init) {
      const node: ListNode<E> = new ListNode(elem, null, this._last);
      this._last.next = node
      this._last = node
    }
  }

  /** elementでループするほうのイテレーター */
  [Symbol.iterator](): IteratorObject<E, void, E> {
    const iterator = this.listNodeIterator()
    return iterator.map(e => e.element)
  }

  /** 要素を最後に追加 */
  push(element: E) {
    const node = new ListNode(element, null, this._last)
    if(this._last) this._last.next = node
    this._last = node
    this.ifNullUpdateHead(node)
  }

  /** 要素を最初に追加 */
  unshift(element: E) {
    const node = new ListNode(element, this._head, null)
    if(this._head) this._head.prev = node
    this._head = node
    this.ifNullUpdateLast(node)
  }

  /** 最後の要素を削除して返す */
  pop(): E | void {
    if(!this._last) return void 0
    const old = this._last.element
    this._last = this._last.prev
    this.checkLastAndHead()
    return old
  }

  /** 最初の要素を削除して返す */
  shift() {
    if(!this._head) return void 0
    const old = this._head.element
    this._head = this._head.next
    this.checkLastAndHead()
    return old
  }
  
  forEach(func: (element: E, index: number) => void): void {
    const iterator = this[Symbol.iterator]()
    iterator.forEach(func)
  }

  map<T>(func: (value: E, index: number) => T): LinkedList<T> {
    const iterator = this[Symbol.iterator]()
    return new LinkedList<T>(iterator.map(func))
  }

  toArray(): E[] {
    return Array.from(this)
  }

  find(func: (value: E, index: number) => boolean): E | void {
    return this[Symbol.iterator]().find(func)
  }

  filter(func: (value: E, index: number) => boolean): LinkedList<E> {
    return new LinkedList<E>(this[Symbol.iterator]().filter(func))
  } 

  reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E): E;
  reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E, initialValue: E): E;
  reduce<U>(func: (previousValue: U, currentValue: E, currentIndex: number) => U, initialValue: U): U;
  reduce<T>(func: (a: T | E, b: E, c: number) => E, init?: T) {
    if(init) return this[Symbol.iterator]().reduce(func, init)
    return this[Symbol.iterator]().reduce(func)
  }
}

push / unshift

pushはリストの最後に要素を追加するメソッドです。
やっていることはこちらです。

1. 追加するノードを作成
2. 今の_last.nextを作成したもので置き換える
3. _lastを作成したもので置き換える
4. 整合性チェック

unshiftはこれの先頭に要素を追加する版です。
_last.nextではなく_head.prevを置き換えています。

pop / shift

popはリストの最後の要素を削除し、その要素を返すメソッドです。
やっていることはこちらです。

1. もしthis._lastがなかったらreturn
2. this._lastを最後から2番目の要素（this._last.prev）で置き換える
3. 整合性チェック

shiftはこれの最初の要素を削除する版です。
shiftでは2でthis._headをthis._head.nextに置き換えています。

[Symbol.iterator]

LinkedListを反復可能（Iterable）にするメソッドです。
また、mapやコンストラクタなどの実装で使っています。

といってもここでやっていることは少なく、ベースとなるイテレーターを作っているのはlistNodeIteratorメソッドです。

listNodeIterator

ListNodeを順番に返すイテレーターを返すメソッドです。
このメソッドはジェネレーター関数で実装しています。

/** ListNodeでループするほうのイテレーター */
private *listNodeIterator(): Generator<ListNode<E>, void, ListNode<E>> {
  let currentNode = this._head
  while (true) {
    if(currentNode === null) return
    yield currentNode
    currentNode = currentNode.next
  }
}

ここでは、this._headから始まり、ListNodeのnextを順番に辿ってyieldしています。

---

[Symbol.iterator]ではこのlistNodeIteratorの呼び出しをmapしています。
マッピング関数ではListNodeをListNode.elementにしています。

[Symbol.iterator](): IteratorObject<E, void, E> {
  const iterator = this.listNodeIterator()
  return iterator.map(e => e.element)
}

なお、mapメソッドは正規イテレーターを返すので、[Symbol.iterator]()の戻り値も正規イテレーターとなります。

コンストラクタ

コンストラクタでは反復可能オブジェクト（Iterable）を受け取り、それを元にLinkedListを構築しています。

実装はこちらです。

constructor(init?: Iterable<E>) {
  if(!init) return

  const first = Iterator.from(init).next()
  if(first.done) return
  this._head = new ListNode(first.value, null, null)
  this._last = this._head

  for (const elem of init) {
    const node: ListNode<E> = new ListNode(elem, null, this._last);
    this._last.next = node
    this._last = node
  }
}

やっていることは大まかにこのような感じになっています。

1. （initがなかったらreturn）
2. 最初の要素（this.head）を設定
3. イテレーターが新しい値を返さなくなるまでループ
   1. イテレーターのnextメソッドを呼び出す
   2. result.valueを使ってListNodeを作成
   3. this._lastを更新

反復可能であることのメリット

反復可能オブジェクトにはこんなものがあります。

• Array
• 正規イテレーター
• ジェネレーター
• LinkedList <- 重要

先ほども説明した通り、ここではLinkedListを反復可能として実装しています。
つまり、LinkedListのコンストラクタにLinkedListを入れられます。

const baseArray = [1, 3, 5]
const baseList = new LinkedList(baseArray) // 配列は反復可能なのでOK

// LinkedListは反復可能なのでOK
const list = new LinkedList(baseList)

これだけで簡単にシャローコピーできるというメリットがあるのです。

forEach / map / filter / etc

正規イテレーターはイテレーターでありながら反復可能です。
そのため、正規イテレーターを返すメソッドの呼び出し結果を、そのままLinkedListのコンストラクタに入れられます。

const list = new LinkedList([1, 2, 4])

// 正規イテレーター
const iterator = list[Symbol.iterator]()

// mapは正規イテレーターを返す
const mapped = iterator.map(x => x ** 2) // 1, 4, 16
const list2 = new LinkedList(mapped) // OK

これを利用して、それぞれのメソッドをサクッと実装していきます。

forEach

実装方法はこんな感じです。

1. this[Symbol.iterator]()を呼び出して正規イテレーターを取得
2. 正規イテレーターのforEachメソッドを呼び出す

forEach(func: (element: E, index: number) => void): void {
  const iterator = this[Symbol.iterator]()
  iterator.forEach(func)
}

他のメソッドもこんな感じで実装します。

map

map<T>(func: (value: E, index: number) => T): LinkedList<T> {
  const iterator = this[Symbol.iterator]()
  return new LinkedList<T>(iterator.map(func))
}

filter

filter(func: (value: E, index: number) => boolean): LinkedList<E> {
  return new LinkedList<E>(this[Symbol.iterator]().filter(func))
} 

find

find(func: (value: E, index: number) => boolean): E | void {
  return this[Symbol.iterator]().find(func)
}

reduce

reduceは型のオーバーロードを書く必要があるので、少し面倒です。
といっても配列のreduceメソッドの型定義とほぼ同じなので、そこまで大変ではありません。

reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E): E;
reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E, initialValue: E): E;
reduce<U>(func: (previousValue: U, currentValue: E, currentIndex: number) => U, initialValue: U): U;
reduce<T>(func: (a: T | E, b: E, c: number) => E, init?: T) {
  if(init) return this[Symbol.iterator]().reduce(func, init)
  return this[Symbol.iterator]().reduce(func)
}

参考