JavaScriptでリンクリストを実装する方法

データ構造を学習している場合、リンクリストは知っておくべきデータ構造の1つです。それやJavaScriptでの実装方法を本当に理解していない場合は、この記事が役に立ちます。

この記事では、リンクリストとは何か、配列との違い、JavaScriptでの実装方法について説明します。始めましょう。

リンクリストとは何ですか?

リンクリストは、配列に似た線形データ構造です。ただし、配列とは異なり、要素は特定のメモリ位置またはインデックスに格納されません。むしろ、各要素は、そのリスト内の次のオブジェクトへのポインタまたはリンクを含む個別のオブジェクトです。

各要素(一般にノードと呼ばれます)には、保存されたデータと次のノードへのリンクの2つの項目が含まれています。データは、任意の有効なデータ型にすることができます。これは、次の図に示されています。

リンクリストの画像

リンクリストへのエントリポイントはヘッドと呼ばれます。ヘッドは、リンクリストの最初のノードへの参照です。リストの最後のノードがnullを指しています。リストが空の場合、ヘッドはnull参照です。

JavaScriptでは、リンクリストは次のようになります。

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

リンクリストの利点

  • データ構造全体を再編成することなく、ノードをリンクリストから簡単に削除または追加できます。これは、アレイよりも優れている点の1つです。

リンクリストのデメリット

  • リンクリストでは検索操作が遅くなります。配列とは異なり、データ要素へのランダムアクセスは許可されていません。ノードは、最初のノードから順番にアクセスされます。
  • ポインタが格納されているため、配列よりも多くのメモリを使用します。

リンクリストの種類

リンクリストには次の3つのタイプがあります。

  • 単一リンクリスト:各ノードには、次のノードへのポインターが1つだけ含まれています。これが私たちがこれまで話してきたことです。
  • 二重リンクリスト:各ノードには、次のノードへのポインターと前のノードへのポインターの2つのポインターが含まれています。
  • 循環リンクリスト:循環リンクリストは、最後のノードが最初のノードまたはその前の他のノードを指し、それによってループを形成するリンクリストのバリエーションです。

JavaScriptでのリストノードの実装

前述のように、リストノードには、データと次のノードへのポインタの2つの項目が含まれています。次のように、JavaScriptでリストノードを実装できます。

class ListNode { constructor(data) { this.data = data this.next = null } }

JavaScriptでのリンクリストの実装

以下のコードは、コンストラクターを使用したリンクリストクラスの実装を示しています。ヘッドノードが渡されない場合、ヘッドはnullに初期化されることに注意してください。

class LinkedList { constructor(head = null) { this.head = head } }

すべてを一緒に入れて

作成したクラスでリンクリストを作成しましょう。まず、我々は2つのリストのノードを作成し、node1そしてnode2、ノード2、ノード1からのポインタ。

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

次に、を使用してリンクリストを作成しますnode1

let list = new LinkedList(node1)

作成したリストのノードにアクセスしてみましょう。

console.log(list.head.next.data) //returns 5

いくつかのLinkedListメソッド

次に、リンクリストに4つのヘルパーメソッドを実装します。彼らです:

  1. サイズ()
  2. 晴れ()
  3. getLast()
  4. getFirst()

1. size()

このメソッドは、リンクリストに存在するノードの数を返します。

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. clear()

このメソッドはリストを空にします。

clear() { this.head = null; }

3. getLast()

このメソッドは、リンクリストの最後のノードを返します。

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst()

このメソッドは、リンクリストの最初のノードを返します。

getFirst() { return this.head; }

概要

この記事では、リンクリストとは何か、JavaScriptで実装する方法について説明しました。また、さまざまなタイプのリンクリストと、それらの全体的な長所と短所についても説明しました。

読んで楽しんでいただけたでしょうか。

新しい記事を公開したときに通知を受け取りたいですか?ここをクリック。