使用 JavaScript 创建链表 什么是链表？ 节点 NodeList

2025-05-24

使用 JavaScript 创建链接列表

什么是链表？

节点

节点列表

什么是链表？

单链表是一种数据结构，它表示一系列节点，每个节点都指向列表中的下一个节点。相反，双向链表的节点分别指向其前后元素。

与数组不同，链表不提供对列表中特定索引的恒定时间访问。因此，如果需要列表中的第三个元素，则必须迭代经过第一个和第二个节点才能到达它。

链表的一个好处是能够在恒定时间内从列表的开头和结尾添加和删除项目。

这些是技术面试中经常被问到的数据结构，所以让我们直接开始吧。

单链表可以是 LIFO（后进先出）或 FIFO（先进先出）。如果使用 LIFO 方法，则节点将从同一端添加和删除。如果使用 FIFO 方法，则节点将从一端添加，从另一端删除。

此外，链表可以进行排序。这意味着，每个节点添加到链表中时，都会被放置在相对于其他节点的适当位置。

节点

链表只是一系列节点，所以让我们从 Node 对象开始。

节点

一个节点有两条信息：

  • 指向列表中下一个项目的指针或引用（对于单链表）
  • 节点的值

对于我们的节点，我们只需创建一个函数，它接受一个值，并返回一个包含上述两个值的对象：指向下一个节点的指针和该节点的值。请注意，我们可以直接使用 ，value而不是value: value。这是因为变量名相同。您可以在此处了解更多关于对象属性简写的信息。

function Node(value) {
  return {
    value,
    next: null
  }
}
Enter fullscreen mode Exit fullscreen mode

节点列表

现在，让我们深入研究一下 NodeList 类。它就是一个节点列表。

节点列表

我们的节点列表将包含五种方法：

  • push(value)：将值推送到链接列表的末尾
  • pop()：弹出列表中的最后一个值
  • get(index)：返回给定索引中的项目
  • delete(index)：从给定索引中删除项目
  • isEmpty()：返回一个布尔值，指示列表是否为空
  • printList()：一种非链表原生的方法，它将打印出我们的列表；它主要用于调试目的

构造函数

我将使用 JavaScript 类语法，当然你也可以使用闭包来创建链表。所以，让我们先来设置一下构造函数。

我们的构造函数中需要三条信息：

  • head：对列表开头节点的引用
  • tail：对列表末尾节点的引用
  • 长度：列表中有多少个节点
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}
Enter fullscreen mode Exit fullscreen mode

为空

该isEmpty()方法是一个辅助函数，如果列表为空则返回 true。

isEmpty() {
  return this.length === 0;
}
Enter fullscreen mode Exit fullscreen mode

打印列表

此实用方法将打印列表中的节点。这仅用于调试目的。

printList () {
  const nodes = [];
  let current = this.head;
  while (current) {
    nodes.push(current.value);
    current = current.next;
  }
  return nodes.join(' -> ');
}
Enter fullscreen mode Exit fullscreen mode

推

我们的 push 方法需要在添加新节点之前检查列表是否为空。那么如何知道列表是否为空呢？有两种方法：

  • 我们的isEmpty()方法返回 true（列表的长度为零）
  • 头指针为空

对于这个例子，我们将检查 head 是否为空，尽管两种解决方案都可以。

如果列表中没有项目，我们可以简单地将头指针和尾指针都设置为新节点并更新列表的长度。

if (this.head === null) {
  this.head = node;
  this.tail = node;
  this.length++;
  return node;
}
Enter fullscreen mode Exit fullscreen mode

如果列表不为空，我们必须执行以下操作：

  • 设置tail.next为指向新节点
  • 设置tail为指向新节点
  • 增加列表长度

添加节点

以下是我们完成的推送方法：

push(value) {
  const node = Node(value);
  // The list is empty
  if (this.head === null) {
    this.head = node;
    this.tail = node;
    this.length++;
    return node;
  }
  this.tail.next = node;
  this.tail = node;
  this.length++;
}
Enter fullscreen mode Exit fullscreen mode

流行音乐

在删除列表中的最后一个项目之前，我们的 pop 方法需要检查以下两件事：

  • 检查列表是否为空
  • 检查列表中是否只有一个项目

我们可以使用我们的isEmpty方法来检查列表是否包含节点。

if (this.isEmpty()) {
  return null;
}
Enter fullscreen mode Exit fullscreen mode

我们如何知道列表中是否只有一个节点？如果 head 和 tail 指向同一个节点的话。但是在这种情况下我们需要做什么呢？移除唯一的节点意味着我们实际上在重置列表。

if (this.head === this.tail) {
  this.head = null;
  this.tail = null;
  this.length--;
  return nodeToRemove;
}
Enter fullscreen mode Exit fullscreen mode

如果列表中有多个元素，我们可以执行以下操作：

while there are nodes in the list
  if the next node in the list is the tail
    update tail to point to the current node
    set the current node to point to null
    decrement the length of the list
    return the previous tail element
Enter fullscreen mode Exit fullscreen mode

它看起来是这样的：

let currentNode = this.head;
let secondToLastNode;

// Start at the front and iterate until
// we find the second to last node
while (currentNode) {
  if (currentNode.next === this.tail) {
    // Move the pointer for the second to last node
    secondToLastNode = currentNode;
    break;
  }
  currentNode = currentNode.next;
}
// Pop off that node
secondToLastNode.next = null;
// Move the tail to the second to last node
this.tail = secondToLastNode;
this.length--;

// Initialized to this.tail
return nodeToRemove;
Enter fullscreen mode Exit fullscreen mode

如果您难以想象这一点，让我们来看一下。

第 6-10 行：如果列表中的下一个节点是最后一个项目，则当前项目是新的“尾部”，因此我们需要保存它的引用。

if (currentNode.next === this.tail) {
  secondToLastNode = currentNode;
}
Enter fullscreen mode Exit fullscreen mode

列表

第 15 行：更新secondToLastNode指向 null。这是从列表中“弹出”最后一个元素的操作。

secondToLastNode.next = null;
Enter fullscreen mode Exit fullscreen mode

列表

第 16 行：更新tail为指向secondToLastNode。

this.tail = secondToLastNode;
Enter fullscreen mode Exit fullscreen mode

列表

第 17 行：减少列表的长度，因为我们刚刚删除了一个节点。

第 18 行：返回我们刚刚弹出的节点。

这是我们的完整 pop 方法：

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const nodeToRemove = this.tail;
  // There's only one node!
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--;
    return nodeToRemove;
  }

  let currentNode = this.head;
  let secondToLastNode;

  // Start at the front and iterate until
  // we find the second to last node
  while (currentNode) {
    if (currentNode.next === this.tail) {
      // Move the pointer for the second to last node
      secondToLastNode = currentNode;
      break;
    }
    currentNode = currentNode.next;
  }
  // Pop off that node
  secondToLastNode.next = null;
  // Move the tail to the second to last node
  this.tail = secondToLastNode;
  this.length--;

  // Initialized to this.tail
  return nodeToRemove;
}
Enter fullscreen mode Exit fullscreen mode

得到

我们的get方法必须检查三种情况：

  • 请求的索引超出了列表的范围
  • 列表为空
  • 我们请求第一个元素

如果请求的索引在列表中不存在，则返回 null。

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}
Enter fullscreen mode Exit fullscreen mode

如果列表为空，则返回 null。您可以合并这些 if 语句，但为了清晰起见，我将它们分开。

if (this.isEmpty()) {
  return null;
}
Enter fullscreen mode Exit fullscreen mode

如果我们请求第一个元素，则返回头部。

// We're at the head!
if (index === 0 )  {
  return this.head;
}
Enter fullscreen mode Exit fullscreen mode

否则，我们只需逐个遍历列表，直到找到我们要查找的索引。

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
Enter fullscreen mode Exit fullscreen mode

完整方法如下get(index)：

get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

if (this.isEmpty()) {
  return null;
}

// We're at the head!
if (index === 0 )  {
  return this.head;
}

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
}
Enter fullscreen mode Exit fullscreen mode

删除

我们的删除方法还必须考虑三种特殊用例：

  • 我们要删除的索引超出了列表的边界
  • 列表为空
  • 我们要删除头部

如果列表中不存在我们要删除的索引，则返回 null。

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}
Enter fullscreen mode Exit fullscreen mode

如果列表为空，则返回 null。您可以将此逻辑与判断索引是否超出列表边界的逻辑结合起来，但为了清晰起见，我将它们分开了。

if (this.isEmpty()) {
  return null;
}
Enter fullscreen mode Exit fullscreen mode

如果我们想删除头部，则设置head为列表中的下一个值，减少长度，并返回刚刚删除的值。

if (index === 0) {
  const nodeToDelete = this.head;
  this.head = this.head.next;
  this.length--;
  return nodeToDelete;
}
Enter fullscreen mode Exit fullscreen mode

如果这些布尔值都不为真，则删除节点的逻辑如下：

while the iterator isn't the index we're looking for
  increase the iterator
  move the previous and current pointers up by one
save the current value as the node to be deleted
update the previous node's pointer to point to the next node
if the next value is null
  set tail to the new last node
decrement list length
return the deleted node
Enter fullscreen mode Exit fullscreen mode

如果您需要帮助将其形象化，请参阅 Pop 部分中的图表。

delete 方法和 pop 方法的区别在于，pop 方法总是会删除列表中的最后一项。而 delete 方法可以删除 0 到列表长度之间的索引。

以下是完整的删除方法：

delete(index) {
   // Index is outside the bounds of the list
  if (index < 0 || index > this.length - 1) {
    return null;
  }

  if (this.isEmpty()) {
    return null;
  }

  if (index === 0) {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.length--;
    return nodeToDelete;
  }

  let current = this.head;
  let previous;
  let iterator = 0;

  while (iterator < index) {
    iterator++;
    previous = current;
    current = current.next;
  }
  const nodeToDelete = current;
  // Re-direct pointer to skip the element we're deleting
  previous.next = current.next;

  // We're at the end
  if(previous.next === null) {
    this.tail = previous;
  }

  this.length--;

  return nodeToDelete;
}
Enter fullscreen mode Exit fullscreen mode

如果您想试用该代码，请随意 fork 我的CodePen。

文章来源：https://dev.to/emmabostian/creating-linked-lists-with-javascript-391e
Devto 翻译
PREV
CSS 特殊性示例 1 示例 2 示例 3
NEXT
使用 JavaScript 方法创建图形可视化数据