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

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

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

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

[参考](https://www.ios-net.co.jp/blog/20230705-1204/)

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

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

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

## 実装方針

- `LinkedList`クラスを実装する
- [Iterator Helpers](https://qiita.com/access3151fq/items/1b485e2c8cba133bc482)を使う
    - `map`や`forEach`などのメソッドの実装で使用
- `LinkedList`を[反復可能](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Iteration_protocols)（`Iterable`）として実装する
- TypeScriptで実装する

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

```mermaid
classDiagram

class ListNode {
  element: E
  next: ListNode&lt;E&gt;
  prev: ListNode&lt;E&gt;
}

class LinkedList {
  -head: ListNode&lt;E&gt;
  -last: ListNode&lt;E&gt;
  いろんなメソッド()
}

LinkedList o-- 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を使わずに実装します。


# 実装

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

```ts
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. 追加するノードを作成
1. 今の`_last.next`を作成したもので置き換える
1. `_last`を作成したもので置き換える
1. 整合性チェック

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

## `pop` / `shift`

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

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

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

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

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

### `listNodeIterator`
`ListNode`を順番に返すイテレーターを返すメソッドです。
このメソッドは[ジェネレーター関数](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Statements/function*)で実装しています。

```ts
/** 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`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Iterator/map)しています。
マッピング関数では`ListNode`を`ListNode.element`にしています。

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

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

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

実装はこちらです。

```ts
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`）
1. 最初の要素（`this.head`）を設定
1. イテレーターが新しい値を返さなくなるまでループ
   1. イテレーターの`next`メソッドを呼び出す
   1. `result.value`を使って`ListNode`を作成
   1. `this._last`を更新

### 反復可能であることのメリット
反復可能オブジェクトにはこんなものがあります。

- `Array`
- [正規イテレーター](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Iterator#正規イテレーター)
- ジェネレーター
- `LinkedList` <- 重要

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

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

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

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

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

```js
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]()`を呼び出して正規イテレーターを取得
1. 正規イテレーターの`forEach`メソッドを呼び出す

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

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

### `map`

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

### `filter`

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


### `find`

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

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

```ts
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)
}
```


# 参考

https://nompor.com/2018/05/19/post-3790/

https://paulownia.hatenablog.com/entry/2013/09/20/000413

https://www.ios-net.co.jp/blog/20230705-1204/