連結リストを学んだ

自分は、エンジニアを名乗りながらもアルゴリズムをほとんど知らずに生きてきました。もちろん文系の大学卒というのもひとつの理由だと思いますが、さすがにそろそろ真面目に勉強しようと思ったので、今回は基礎中の基礎である連結リストについて学びコードも書いたので記事にしました。

アルゴリズム図鑑

その前に自分は「アルゴリズム図鑑 絵で見てわかる26のアルゴリズム」という本でざっとどういうアルゴリズムがあるのか一通り把握しました。これは前編カラーで絵が分かりやすくてかなりオススメ！

連結リスト（リンクリスト）

別名リンクリスト、リンクトリストなどと呼ばれます。前後の要素にリンクを持つデータ構造のことであり、要素の値とリンクがセットになったものをNodeと呼びます。連結リストの一番最初のNodeへのリンクのことをheadと呼び、一番最後のNodeのことをtailと呼びます。よく似た構造に配列があり比較対称となります。

配列とリンクリストの違い

以下に特に大きな違いをまとめました。

• サイズ

  • 配列：宣言する際に指定する
  • 連結リスト：宣言時に指定はしないので制限することなく実行している最中に変更できる

• 要素へのアクセス

  • 配列：インデックス（添字）があり直接、ランダムにアクセスすることが可能
  • 連結リスト：最初の要素から順番にアクセスしていきます。ランダムなアクセスが苦手

• 要素の挿入、削除、検索

  • 配列：シフトが必要。遅い
  • 連結リスト：順番に処理する関係上簡単に素早くできる。

要は、用途によって使い分けてね。ということだとは思いますが、自分が今まで連結リストを実務で扱ったケースはありませんでした。。そんな連結リストには主に3つの種類があります。

単方向リスト

各要素が一つ後ろにリンクを持っているリストのこと。リンクはリスト上の次のNodeを指していて最後尾はNullになる。

双方向リスト

各要素が一つ後と前の要素へのリンクをもっているリストのこと。この場合は最初と最後のデータがNullとなる。

循環リスト

各要素が一つ後のリンクを持っており、最後の要素は、最初の要素へのリンクをもっている

実際に書いてみる

こちらに実際に書いたコードがあります。今回は、以下のような機能を追加しました。

• 要素の追加
• 要素の削除
• リストを逆にする
• 配列 ⇔ リスト変換
• 配列内での検索

最初に初期値を設定します。今回はクラスです。

export class LinkedListNode<T> {
  value: T;
  nextNode: LinkedListNode<T> | null;

  constructor(value: T, next = null) {
    this.value = value;
    this.nextNode = next;
  }
}

追加については特に難しいことはなく先程作ったクラスのインスタンスを生成後にheadとtailの値を確認してから次のリストに1つ移ります。その後引数を代入します。

 /**
   * 要素を追加
   *
   * @param {T} value
   * @return {*}
   * @memberof LinkedList
   */
  push(value: T) {
    const newNode = new LinkedListNode<T>(value);

    if (!this.head || !this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.nextNode = newNode;
      this.tail = newNode;
    }
    this.length += 1;

    return newNode;
  }

削除が少し頭を使いますが、まずリストに要素があるか確認する関数を作成して、要素がある場合は、現在のheadが新しいheadに移動しつつリスト自体のlengthを1つ減らします。 その後削除したい要素までwhile文を回して削除したい要素が見つかったらlengthを1つ減らします。

/**
   *  値を削除する
   *
   * @param {T} value
   * @return {*} 
   * @memberof LinkedList
   */
  deleteValue(value: T) {
    if (this.head?.value === value)
      return this.removeHead();

    let currentNode = this.head?.nextNode;
    let previousNode = this.head;

    while (currentNode) {
      if (currentNode.value === value) break;

      previousNode = currentNode;
      currentNode = currentNode.nextNode;
    }

    if (currentNode) {
      if (!previousNode) return
      previousNode.nextNode = currentNode?.nextNode;
      this.length--;
    }
  }

やってみて

他にも、リストの途中に要素を追加する、リストの中の要素検索などの機能も追加していきたいが、追加と削除を実装したことだけで連結リストがどういうものかはなんとなく理解できた。フロントエンドをやっていると連結リストを作ることってほとんどない（JavaScriptには配列があり便利すぎるから）ので実務で実装することはないと思うが、概念だけでも覚えておくと良いと思った。

次回

次は、キュー・スタックを手を動かしながら学ぶ予定です。