JS（リンクリスト）のデータ構造を深く理解する

関連する推奨事項: 「JavaScript ビデオ チュートリアル 」

JS には構築されていないため、JS 初心者にとって、リンク リストを理解するのは難しい作業になる可能性があります。リンクされたリストが提供されます。 JS のような高級言語では、このデータ構造を最初から実装する必要があり、このデータ構造がどのように機能するかに慣れていないと、実装部分がさらに難しくなります。

この記事では、リンク リストをデータベースに保存する方法、リンク リストの追加と削除、リンク リストの検索と逆順などの操作を実装する方法について説明します。リンク リストを実装する前に、配列やオブジェクトと比較したリンク リストの利点を理解しておく必要があります。

配列内の要素はインデックス番号と順序に従ってデータベースに保存されることがわかっています。

配列を使用する場合先頭または特定のインデックスで要素を追加/削除するような操作は、他のすべての要素のインデックスを移動する必要があるため、パフォーマンスが低下する可能性があります。この理由は、配列の番号付きインデックスの性質が原因です。

オブジェクトを使用すると、上記の問題を解決できます。オブジェクト内では、 要素の格納場所はランダムな であるため、先頭または特定のインデックスで要素を追加/削除するなどの操作を実行するときに、要素のインデックスを移動する必要はありません。

##オブジェクト内の要素の追加と削除は高速ですが、上の図からわかるように、操作を反復する場合、オブジェクトは最適な選択ではありません。オブジェクトはランダムな場所に保存されます。したがって、反復操作には時間がかかる場合があります。これが、

Linked List

が導入される理由です。 それでは、リンク リストとは何ですか?

名前自体から、何らかの形でリンク リストであることがわかります。では、それはどのようにリンクされ、リストには何が含まれているのでしょうか?

リンク リストは、データとポインター

という 2 つの属性を持つノードで構成されます。 ノード内のポインタは、リスト内の次のノードを指します。リンクされたリストの最初のノードは

head

と呼ばれます。よりよく理解するために、リンク リストを説明する図を見てみましょう。

上の図からわかるように、各ノードには次のものがあります。 2 つの属性、

data

と pointer。ポインタはリスト内の次のノードを指し、最後のノードのポインタは null を指します。上の図は 単一リンク リスト ? です。 リンク リストとオブジェクトの間には大きな違いがあります。リンクされたリストでは、各ノードは

pointer

(ポインター) を介して次のノードに接続されます。したがって、リンク リストの各ノード間には接続がありますが、オブジェクトでは、キーと値のペアは相互に接続せずにランダムに格納されます。 次に、整数を格納するリンク リストを実装します。 JS は組み込みのリンク リストのサポートを提供していないため、オブジェクトとクラスを使用してリンク リストを実装します?

class Node {
  constructor (value) {
    this.value = value
    this.next = null
  }
}

class LinkedList {
  constructor () {
    this.head = null
    this.tail = this.head
    this.length = 0
  }
  append (value) {
  }

  prepend (value) {

  }

  insert (value, index) {

  }

  lookup (index) {

  }

  remove (index) {

  }

  reverse () {
    
  }
}

上記のコードでは、2 つのクラス (1 つは

リンク リスト##) を作成しました。 # 自体、1 つは

ノード 自体です。すでに説明したように、各ノードには value と pointer (next フィールドに対応) という 2 つのプロパティがあります。 LinkedList

クラスには 3 つの属性

head (初期値は null) が含まれており、これは最後の ## を格納するために使用されます。 #tail (null も指します) およびリンク リストの長さを保存するために使用される length 属性。次に、内部にメソッドを実装してみましょう。 append (値を順番に追加)この関数は、リンクされたリストの末尾にノードを追加します。この関数を実装するには、関数が実行する必要がある操作のいくつかを理解する必要があります。

上の図から、これを実装できます。次の方法で append 関数:

  append (value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
  }

append メソッドを簡単に説明しますか?:

const linkedList1 = new LinkedList()
linkedList1.append(2)

head がポイントしているかどうかを確認します

null

に、この時点で head は null を指しているため、新しいオブジェクトを作成し、その新しいオブジェクトを head と # に割り当てます。 ##tail :

let node = new Node(2)
this.head = newNode
this.tail = newNode

さて、head と tail

は両方とも同じオブジェクトを指します。これは覚えておくことが重要です。

次に、さらに 2 つの値をリンク リストに追加します。

linkedList1.append(3)
linkedList1.append(4)

さて、head

は

null

を指していないため、

append 関数の else ブランチを入力します:

this.tail.next = node

由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是JS 中对象的工作方式。在JavaScript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于

this.head.next = node;

下一行：

this.tail = node

现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。

执行三次append之后，linkedList1 的结构应该是这样的：

head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3

从上面的代码中我们可以看到，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。

我们来看下一个函数 ?

prepend (将值添加到链表的开头)

为了实现此函数，我们使用Node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。 接下来，我们将新节点分配给链表的head：

与append函数一样，这个函数的复杂度也是O(1)。

  prepend (value) {
  const node = new Node(value)

  node.next = this.head
  this.head = node
  this.length++
}

就像append函数一样，此函数的复杂度也为O(1)。

insert (在特定索引处添加值)

在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。 insert 函数接受两个参数，值和索引:

let linkedList2 = new LinkedList()
linkedList2.append(23)
linkedList2.append(89)
linkedList2.append(12)
linkedList2.append(3)

linkedList2.insert(45,2)

第1步：

遍历链表，直到到达index-1位置:

第2步：

将索引为1的节点的指针（在本例中为89）分配给新节点（在本例中为45）：

第3步：

将新节点(45)的 next 指向给下一个节点(12)

这就是执行插入操作的方式。 通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。 在代码中实现：

insert (value, index) {
  if (index >= this.length) {
  this.append(value)
}

  const node = new Node(value)

  const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
  prevNode.next = node
  node.next = nextNode

  this.length++
}

简单分析一下上面的函数：

如果index的值大于或等于length属性，则将操作移交给append函数。 对于 else 分支，我们使用 Node 类创建一个新节点，接下来观察一个新函数getPrevNextNodes() ，通过该函数我们可以接收prevNode和nextNode的值。 getPrevNextNodes函数的实现如下：

 getPrevNextNodes(index){
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while(count < index - 1){
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

通过遍历链表返回在index-1位置和index位置的节点，并将prevNode的next属性指向新节点，并将新节点的next属性指向nextNode。

链表的插入操作的复杂度为 O(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。 尽管复杂度为O(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。

remove (删除特定索引处的元素)

实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getPrevNextNodes函数获取prevNode和nextNode值时，我们必须在remove中执行以下操作：

remove(index){
  let {previousNode,currentNode} = this.getNodes(index)
  previousNode.next = currentNode.next
  this.length--
}

删除操作的复杂度也为 O(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。

reverse (反转链表)

虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。

为了反转链表，我们需要跟踪三个节点，previousNode，currentNode和nextNode。

考虑下面的链表:

let linkedList2 = new LinkedList()
linkedList2.append(67)
linkedList2.append(32)
linkedList2.append(44)

第一步：

开始，previousNode的值为null，而currentNode的值为head：

第二步：

接下来，我们将nextNode分配给currentNode.next：

第三步：

接下来，我们将currentNode.next属性指向previousNode：

第三步：

现在，我们将previousNode移至currentNode，将currentNode移至nextNode：

这个过程从步骤2重复操作，一直到currentNode 等于 null。

reverse (){
  let previousNode = null
  let currentNode = this.head

  while(currentNode !== null) {
    let nextNode = currentNode.next
    currentNode.next = previousNode
    previousNode = currentNode
    currentNode = nextNode
  }

  this.head = previousNode
}

就像我们看到的一样，直到currentNode === null，我们一直在遍历和移动这些值。 最后，我们将previousNode值分配给head。

反向运算的复杂度为O(n)。

查找 (查找特定索引的值)

这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是O(n)。

lookup(index){
    let counter = 0;
    let currentNode = this.head;
    while(counter < index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }

好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。

总结

链表为我们提供了快速的append（末尾添加元素）和prepend（开头添加元素）操作。 尽管链表中的插入操作的复杂度为O(n)，但比数组的插入操作要快得多。 使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。

在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。

原文地址：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/

作者：Vivek Bisht 

译文地址：https://segmentfault.com/a/1190000024565634

更多编程相关知识，请访问：编程教学！！

以上がJS（リンクリスト）のデータ構造を深く理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。