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

Jan 13 2023

連結リストは配列に非常によく似たデータ構造ですが、データが 1 つのメモリ位置に格納されないという点が異なります。JavaScript では、連結リストの各要素 (ノード) は、連結リストの次の要素を指す次の要素 (ノード) を指すオブジェクトであり、最後の要素が何も指さない (連結リストの終わり) まで続きます。 .

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

図的には、リンクされたリストを次のように表示するのが最適です。

これは次のようにも見ることができます。

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

ミュージックプレーヤー — ミュージックプレーヤーの曲は、前後の曲にリンクされています。そのため、リストの最初または最後から曲を再生できます。
画像ビューア — 前と次の画像がリンクされており、次と前のボタンでアクセスできます。
Web ブラウザの前のページと次のページ — リンクされたリストとしてリンクされているため、戻るボタンと次のボタンを押すことで、Web ブラウザで検索された前のページと次のページにアクセスできます。

連結リストには、単方向連結リスト、双方向連結リスト、および循環連結リストの 3 つの主要な種類があります。この学習の目的で、単一リンクリストを実装します。

前述のように、リンクリストは、相互にポイントする要素 (ノード) の単なる組み合わせです。リンクリストの基本単位はノードです。ノードには、次のように実装されたデータと次のノードへのポインタが格納されます。

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

リンクされたリストからのノードの削除は、そのポインターを削除することによって実装されます。これは、ノード (削除される) を指している前のノードがノード (削除される) をスキップするように作成されるため、次のノードを指すことを意味します。

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

これが、リンクされたリストとその実装を理解するのに役立つことを願っています.

さらに詳しい説明が必要な場合は、LinkedIn で私に連絡してください。https://www.linkedin.com/in/joshua-ajagbe/または、[email protected] までメールでお問い合わせください。

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

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