如何在 JavaScript 中实现单向链表

嗨？，欢迎回到链接列表的这个系列。在上一篇文章中，我们了解了链表的基础知识，包括它们的定义、术语、与数组的区别以及链表的类型。我承诺我们会更深入地研究链表的实现，所以让我们开始吧。

课程大纲

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（推特）

敬请期待并祝您编码愉快??‍??

以上是如何在 JavaScript 中实现单向链表的详细内容。更多信息请关注PHP中文网其他相关文章！