Vertieftes Verständnis der Datenstruktur in JS (Linked-list)

Verwandte Empfehlungen: „Javascript-Video-Tutorial“

Für JS-Anfänger kann das Verständnis verknüpfter Listen eine schwierige Aufgabe sein, da JS keine integrierte verknüpfte Liste bereitstellt. In einer Hochsprache wie JS müssen wir diese Datenstruktur von Grund auf implementieren. Wenn Sie nicht mit der Funktionsweise dieser Datenstruktur vertraut sind, wird der Implementierungsteil schwieriger.

In diesem Artikel besprechen wir, wie man verknüpfte Listen in einer Datenbank speichert und Vorgänge wie das Hinzufügen und Löschen verknüpfter Listen, das Suchen und das Umkehren verknüpfter Listen implementiert. Bevor Sie eine verknüpfte Liste implementieren, müssen Sie die Vorteile einer verknüpften Liste im Vergleich zu Arrays und Objekten kennen.

Wir wissen, dass Elemente in einem Array mit Indexnummern und Reihenfolge in der Datenbank gespeichert werden:

Bei der Arbeit mit Arrays können Vorgänge wie das Hinzufügen/Entfernen von Elementen am Anfang oder an einem bestimmten Index eine Leistung darstellen Das Problem ist gering, da wir den Index aller anderen Elemente verschieben müssen. Der Grund dafür liegt in der nummerierten Indizierung von Arrays.

Die Verwendung von Objekten kann die oben genannten Probleme lösen. Da in einem Objekt der Elementspeicherort zufällig ist, besteht keine Notwendigkeit, den Index des Elements zu verschieben, wenn Vorgänge wie das Hinzufügen/Entfernen eines Elements am Anfang oder an einem bestimmten Index ausgeführt werden:

Obwohl das Hinzufügen und Entfernen von Elementen zu Objekten schnell geht, sind Objekte, wie Sie im obigen Bild sehen können, nicht die beste Wahl für die Iteration von Vorgängen, da ihre Elemente an zufälligen Orten gespeichert werden. Daher können iterative Vorgänge lange dauern. Aus diesem Grund wird die verknüpfte Liste eingeführt.

Was ist also eine verknüpfte Liste?

Sie können am Namen selbst erkennen, dass es sich in gewisser Weise um eine verknüpfte Liste handelt. Wie ist es also verknüpft und was enthält die Liste?

Eine verknüpfte Liste besteht aus Knoten mit zwei Attributen: Daten und Zeiger.

Der Zeiger innerhalb des Knotens zeigt auf den nächsten Knoten in der Liste. Der erste Knoten in der verknüpften Liste heißt head. Zum besseren Verständnis werfen wir einen Blick auf das Diagramm, das die verknüpfte Liste beschreibt: head。 为了更好地理解，让我们看一下描述链表图示：

从上图可以看出，每个节点都有两个属性，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 () {
    
  }
}

在上面的代码中，我们创建了两个类，一个用于来链表本身，一个是节点本身。 如我们所讨论的，每个节点将具有两个属性，一个值和一个指针(对应 next 字段)。

LinkedList类包含三个属性，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 都指向同一个对象，这一点很重要，要记住。

接着，我们再向链表添加两个值：

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

现在，head 不指向null，所以我们进入append函数的else

🎜🎜🎜🎜Wie aus der obigen Abbildung ersichtlich ist, verfügt jeder Knoten über zwei Attribute: data und pointer . Der Zeiger zeigt auf den nächsten Knoten in der Liste und der Zeiger des letzten Knotens zeigt auf null. Das Bild oben ist eine 🎜einfach verknüpfte Liste🎜?. 🎜🎜Es gibt einen großen Unterschied zwischen verknüpften Listen und Objekten. In einer verknüpften Liste ist jeder Knoten über einen 🎜Zeiger🎜 (Zeiger) mit dem nächsten Knoten verbunden. Wir haben also eine Verbindung zwischen jedem Knoten der verknüpften Liste, während in einem Objekt die Schlüssel-Wert-Paare zufällig und ohne Verbindung zueinander gespeichert werden. 🎜🎜Als nächstes implementieren wir eine verknüpfte Liste zum Speichern von Ganzzahlen. Da JS keine integrierte Unterstützung für verknüpfte Listen bietet, werden wir Objekte und Klassen verwenden, um verknüpfte Listen zu implementieren? nodes🎜 selbst. Wie wir besprochen haben, verfügt jeder Knoten über zwei Eigenschaften, einen Wert und einen Zeiger (entsprechend dem Feld next). Die 🎜🎜🎜LinkedList🎜-Klasse enthält drei Attribute, head (Anfangswert ist null), die zum Speichern des tail des letzten verwendet werden Knoten der verknüpften Liste (zeigt auch auf null) und das Attribut length, das zum Speichern der Länge der verknüpften Liste verwendet wird. Als nächstes implementieren wir die Methode in?. 🎜

append (Werte der Reihe nach hinzufügen)

🎜Diese Funktion fügt einen Knoten am Ende der verknüpften Liste hinzu. Um diese Funktion zu implementieren, müssen wir einige der Operationen verstehen, die sie ausführen muss: 🎜🎜🎜🎜🎜🎜Aus dem obigen Bild können wir die Funktion append wie folgt implementieren: 🎜

this.tail.next = node

🎜Einfaches Paar append Erklären Sie die Methode?: 🎜

this.head.next = node;

🎜 Überprüfen Sie, ob head auf null zeigt. Zu diesem Zeitpunkt zeigt head auf null Also erstellen wir ein neues Objekt und weisen das neue Objekt head und tail zu:🎜

this.tail = node

🎜Jetzt head code> und <code>tail zeigen alle auf dasselbe Objekt. Dies ist wichtig zu beachten. 🎜🎜Als nächstes fügen wir der verknüpften Liste zwei weitere Werte hinzu: 🎜<pre class="brush:js;toolbar:false;">head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}} tail : {value: 4, next: null} length:3</pre>🎜Jetzt zeigt <code>head nicht auf null, also geben wir den append ein Funktion else Zweig: 🎜

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

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

Das obige ist der detaillierte Inhalt vonVertieftes Verständnis der Datenstruktur in JS (Linked-list). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!