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

课程大纲

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

敬请期待并快乐编码??‍??