こんにちは、リンク リストのこのシリーズへようこそ。前回の記事では、リンク リストの定義、用語、配列との違い、リンク リストの種類など、リンク リストの基本について学びました。リンク リストの実装についてさらに深く掘り下げると約束したので、始めましょう。

コース概要

1. 導入
2. 単一リンクリストの実装
   • 新しいノードの作成
   • 先頭に挿入
   • 最後に挿入
   • ノードの削除
   • ノードを検索
   • リストを調べる
3. 結論

導入

前の記事で学んだように、リンク リストはプログラミングの世界における基本的なデータ構造です。これらはノードで構成され、各ノードにはデータと、シーケンス内の次のノード (単一リンク リストの場合) または次と前のノードの両方 (二重リンク リストの場合) への参照 (またはリンク) が含まれます。配列とは異なり、リンク リストは連続したメモリ位置に要素を格納しないため、効率的な挿入と削除が可能です。

リンク リストの概念を理解することは、データ構造とアルゴリズムを習得するために非常に重要です。この記事では、単一リンク リストの基本から始めて、リンク リストの実装について詳しく説明します。

単一リンクリストの実装

単一リンク リストは最も単純なタイプのリンク リストで、各ノードがシーケンス内の次のノードを指します。下の画像のように。

さて、単一リンクリストの基本操作の実装を開始します。しましょうか？

新しいノードの作成

新しい Node クラスを作成することから始めましょう。 Node クラスには、ノードのデータを受け取るコンストラクターと、最初に null に設定される次のポインターが含まれます。

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

この新しく作成された Node クラス (リンク リスト内のノードを表す) は、以下のように視覚化できます。

次に進む前に、リンク リストの操作を保持する SinglyLinkedList クラスの新しいインスタンスを作成しましょう。

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

先頭に挿入

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

説明: 先頭に挿入することは、新しい人が先頭の列に加わるようなものです。彼らは新しい一人称となり、以前の一人称にリンクします。

最後に挿入

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

説明: 最後に挿入することは、行の最後に誰かが参加するのと同じです。最後まで歩いて最後の人を見つけ、その人を新しい人にリンクする必要があります。

ノードの削除

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

説明: ノードの削除は、列の途中にいる誰かが退席を決意するようなものです。私たちはその人を見つけて、その前の人と後の人を結びつけます。

ノードを検索する

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

説明: ノードの検索は、列内の特定の人を見つけようとするのと似ています。私たちは先頭から始めて、見つけるか最後尾に到達するまで、各人に質問します。

リストをたどる

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

説明: トラバースは、ラインを歩いて各人に挨拶するようなものです。私たちは先頭からスタートして、最後まで進み続けます。

結論

この記事では、リンク リストの基本的な操作と、それを JavaScript で実装する方法について学びました。次の記事では、二重リンクリストについて学びます。

リンクされたリストをマスターするには練習が必要であることを覚えておいてください。引き続き問題を解決し、さまざまなシナリオでこれらのデータ構造を実装します。

常に最新情報を入手してつながりを保つ

このシリーズのどの部分も見逃さないようにし、ソフトウェア開発 (Web、サーバー、モバイル、またはスクレイピング / オートメーション)、データ構造とアルゴリズム、その他のエキサイティングな技術に関するより詳細なディスカッションのために私に連絡してください。トピックについては、フォローしてください:

• GitHub
• リンク済み
• X (Twitter)

引き続きコーディングをお楽しみください ?‍??