ES6链表简介

过去一个月左右，我一直在LeetCode和Codewars等网站上练习编程题，发现涉及链表的问题非常流行。事实上，LeetCode上最热门的 25 道面试题中，有 6 道都以某种形式涉及到了链表。在本文中，我们将介绍单链表和双链表的基础知识，并探讨一个使用JavaScript ES6Class中常用关键字实现的简单示例。

什么是链表？

链表是一种线性数据结构，其中每个数据项（称为节点）都包含指向内存中另一个节点位置的引用。简单来说，链表中的每个元素都知道下一个元素的位置。链表比你想象的要常见得多：音乐应用在歌曲播放列表中使用链表，像Ticketmaster这样的网站使用链表来跟踪虚拟排队的顾客（你见过“您还有 5 分钟完成购买”的提示吗？）。

链表有两种形式——单链表和双链表。让我们来看一个图示和代码示例：

单链表

列表的开头节点称为头节点。其后的每个节点都只保留对下一个节点位置的引用。列表末尾的节点称为尾节点。它不包含对任何其他节点的引用。

ES6 允许我们使用class关键字来构建一个基本的单链表。

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

我们通过执行该操作来创建列表，const SLL = new SinglyLinkedList()该操作会创建一个 JavaScript 对象，该对象具有 head、tail 和可选的 length 属性。为了创建节点，通常需要编写另一个构造函数：

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

为了向链表中添加值，我们可以向 SinglyLinkedList 类添加一个实例方法。让我们创建一个 unshift 方法，该方法会将一个节点添加到链表的开头：

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}

请注意，要将一个节点添加到链表的开头，我们首先必须调用 `addNode()` 方法并new Node()传入一个值来创建该节点。这将创建一个继承自 ` Node`类的对象。接下来，如果创建的节点是链表的第一个节点，我们必须确保将头节点和尾节点都设置为新创建的节点。如果不是第一个节点，我们只需要更新头节点，将新节点的 `next` 属性指向原头节点的 `next` 属性。最后，我们递增 `count` 属性来跟踪链表中节点的总数，并可以选择返回更新后的链表（用 `removeNode()` 表示this）。与 JavaScript 数组不同，向链表开头添加节点的时间复杂度为常数 ( O(1) )，这体现了在需要向链表末尾添加节点时使用链表的主要优势之一。相比之下，数组的反向移动操作的时间复杂度为线性 (O(n))。

双向链表

注意看，头节点和尾节点之间的每个节点都会跟踪其前后位置的节点。我们只需要对之前的单链表代码做一些小的修改：

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.head.previous = node;
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}
//Node class constructor
class Node {
  constructor(val) {
    this.val = val;
    this.previous = null;
    this.next = null;
  }
}

请注意，在双向链表中进行反向移动时，我们必须先将原链表头的previous属性指向新节点，然后再将链表的头属性更新为新节点。虽然这看起来代码量稍大，但双向链表可以向前和向后遍历，而单向链表只能从头节点开始遍历。我们每天都在使用双向链表结构，例如在浏览器中使用前进和后退箭头键进行导航。

总结

这篇文章只是对这些数据结构的外观和功能进行了浅尝辄止的介绍。如果你想深入了解，我强烈建议你去看看Visualgo 制作的关于这些数据结构和其他方法的动画。当你准备好应对一些面试题时，可以尝试一下LeetCode排名前 100 的面试题中的以下题目：
1.将两个数字相加
；2.从列表末尾删除第 N 个节点；
3.合并两个已排序的列表；
4.合并 k 个已排序的列表；
5.交换节点对；
6.反转 k 个分组中的节点。