• 数据结构之数组
• 数据结构之队列
• 数据结构之栈
• 数据结构之链表
• 数据结构之树
• 数据结构之图

链表是用来存储多个数据的一种结构。链表由节点构成，每个节点是数据 + 指针的构成方式。与数组不同，链表在内存里并不是连续放置的，是由指针指向下一个引用地址。这种结构的好处是增删元素不需要大量移动其他元素，只需要断开插入位置的连接，重新拼接新数据节点即可。但也有缺点，就是不能像数组一样通过下标直接定位到一个元素，而是要遍历链表，一节一节地去找到目标元素

和火车的结构类似，链表的每个节点就是一个车厢，每个车厢能连接起来

实现一个链表类

链表类有以下实例方法

1. append(value) > 向链表尾部追加一个节点
2. insert(position, value) > 链表特定位置插入节点
3. removeAt(position) > 移除链表某个位置的节点
4. getNode(position) > 获取某个节点
5. size() > 查看链表的长度
6. getHead() > 返回头节点
7. toString() > 输出链表每个节点的值

还需要一个静态方法

1. createNode(value) > 生成一个节点

class LinkedList {
  #length = 0
  #head = null
  /**
   * 链表类
   * @param {String | Number} value 元素
   */
  constructor(value) {
    this.#head = LinkedList.createNode(value)
    this.#length++
  }

  /**
   * 在链表尾部追加一个节点
   * @param {String | Number} value 节点的值
   */
  append(value) {}

  /**
   * 在链表的指定位置插入元素
   * @param {Number} position 位置下标
   * @param {String | Number} value 插入的元素
   */
  insert(position, value) {}

  /**
   * 根据元素的位置，从链表中删除元素
   * @param {Number} position
   */
  removeAt(position) {}

  /**
   * 将链表转成字符串输出
   */
  toString() {}

  /**
   * 查找目标元素
   * @param {Number} position 目标元素位置
   */
  getNode(position) {}

  /**
   * 查看链表长度
   */
  size() {}

  /**
   * 生成一个 node 节点
   * @param {String | Number} value 节点的值
   */
  static createNode(value = null) {}
}

生成一个节点

链表的核心就是节点。链表是由一个个节点拼接而成的，每个节点有自身的值，以及指向下一个节点地址的指针。节点很简单，本质上就是一个对象，这个对象有两个属性：一是自身的值，二是指针。

const node1 = {
  value: '',
  next: node2
}

const node2 = {
  value: '',
  next: node3
}

const node3 = {
  value: '',
  next: null
}

链表的类提供一个静态方法，能生成一个 node 节点的实例

class LinkedList {
  // ...

  /**
   * 生成一个 node 节点
   * @param {String | Number} value 节点的值
   */
  static createNode(value = null) {
    function Node(val) {
      this.value = val
      this.next = null
    }
    const node = new Node(value)
    return node
  }

  // ...
}

向链表追加节点

操作任何数据结构，无非都围绕着增删改查。对链表来说，增有两种实现方式：第一种是在尾部追加一个最新的节点，第二种是将节点插入到链表的指定位置。我们先从第一种开始说起。

要向链表追加节点，只要遍历到最后一个节点，让最后一个节点的指针指向新节点即可。但如果当前链表是空的，那么只需要让头节点为新插入的节点即可

class LinkedList {
  // ...

  /**
   * 在链表尾部追加一个节点
   * @param {String | Number} value 节点的值
   */
  append(value) {
    // 初始化一个节点
    const node = LinkedList.createNode(value)
    // 初始化指针，指向头节点
    let currentNode = this.#head
    // 如果是空的链表，头节点为新节点
    if (this.#head === null) {
      this.#head = node
    } else {
      // 遍历整个链表，找到最后一个节点
      while (currentNode.next) currentNode = currentNode.next
      // 修改指针，指向新节点
      currentNode.next = node
    }
    // 更新链表长度
    this.#length++
    return this.#head
  }

  // ...
}

在链表特定位置插入节点

在特定位置插入节点，需要做以下 3 步：

1. 找到目标位置的前一个节点 A 和目标位置节点 B
2. 将新节点的指针指向 B
3. 将 A 的指针指向新节点

class LinkedList {
  // ...

  /**
   * 在链表的指定位置插入节点
   * @param {Number} position 位置下标
   * @param {String | Number} value 插入的元素
   */
  insert(position, value) {
    // 判断临界条件
    if (position < 0 || position > this.#length) return false
    let node = LinkedList.createNode(value)
    // 如果插入的位置是第一个节点
    if (position === 0) {
      node.next = this.#head
      this.#head = node
    } else {
      // 如果插入的位置非第一个节点
      let index = 0
      let currentNode = this.#head
      // 找到目标节点的前一个节点 A 和目标节点 B
      // currentNode 即 A，currentNode.next 即 B
      while (index++ < position - 1) currentNode = currentNode.next
      // 将新节点的指针指向目标节点 B
      node.next = currentNode.next
      // 将 A 节点的指针指向新节点
      currentNode.next = node
    }
    this.#length++
    return true
  }

  // ...
}

移除链表某个位置的节点

移除链表的某个节点有两种情况：

1. 移除的是头节点，只需要让当前头节点的下一个节点成为头节点即可
2. 移除的不是头节点，找到需要移除的节点的前一个节点 A，让节点 A 的指针绕过下一个节点，直接指向下下个节点

class LinkedList {
  // ...

  /**
   * 根据元素的位置，从链表中删除节点
   * @param {Number} position
   */
  removeAt(position) {
    // 不在链表长度内 return null
    if (position < 0 || position > this.#length - 1) return null
    let removeNode
    // 移除第一个节点
    if (position === 0) {
      removeNode = this.#head.value
      this.#head = this.#head.next
    } else {
      // 移除非第一个节点
      let index = 0
      let currentNode = this.#head
      while (index++ < position - 1) currentNode = currentNode.next
      removeNode = currentNode.next.value
      // 指针绕过需要被删除的节点
      currentNode.next = currentNode.next.next
    }
    this.#length--
    return removeNode
  }

  // ...
}

获取某个节点

从头节点开始遍历，直到找到元素或者返回 null

class LinkedList {
  // ...

  /**
   * 查找目标节点
   * @param {Number} position 目标元素位置
   */
  getNode(position) {
    if (position < 0 || position > this.#length - 1) return null
    let currentNode = this.#head
    while (position--) currentNode = currentNode.next
    return currentNode.value
  }

  // ...
}

查看链表的长度

返回私有属性 length 即可

class LinkedList {
  // ...

  /**
   * 查看链表长度
   */
  size() {
    return this.#length
  }

  // ...
}

返回头节点

返回私有属性 head 即可

class LinkedList {
  // ...

  /**
   * 返回头节点
   */
  getHead() {
    return this.#head
  }

  // ...
}

输出链表每个节点的值

遍历整个链表，把每个节点的 value 串起来即可。如果链表为空，返回空字符串

class LinkedList {
  // ...

  /**
   * 将链表转成字符串输出
   */
  toString() {
    if (this.#head === null) return ''
    let currentNode = this.#head
    let string = ''
    while (currentNode) {
      string += currentNode.value + (currentNode.next ? ',' : '')
      currentNode = currentNode.next
    }
    return string
  }

  // ...
}

双向链表与循环链表

双向链表的每个节点除了有指向下一个节点的next指针之外，还有指向上一个节点的prev指针。除了头节点之外，还有尾节点。

循环链表的尾节点不再指向空，而是指向头节点