第7章高阶链表结构

从本章开始，我们会学习一些高阶的数据结构，包括对之前几章所学数据结构的扩展和新的数据结构（堆），在第二阶段（高阶数据结构）的学习中，会使用Node.js 24大版本在终端直接运行TypeScript代码（无需使用ts-node），那么开始吧。

7.1 循环链表结构

在学习循环链表的过程中，会先简要了解什么是循环链表；其次通过重构单向链表来实现让循环链表继承，最后基于循环链表去实现对应的方法。

7.1.1 循环链表的概念与特性

在第3章，我们从零封装了一个普通单向链表结构，在普通单向链表结构的基础上，可以封装更灵活的两种链表结构：

（1）循环链表。

（2）双向链表。

循环链表（Circular LinkedList）是一种特殊的链表数据结构，是在普通链表的基础上，最后一个节点的下一个节点不再是 null，而是指向链表的第一个存储实际数据的节点。使链表形成了一个环，则链表能够被无限遍历。

只能沿一个固定方向读取数据的循环链表被称为单向循环链表，循环链表与双向链表的结合版本为双向循环链表。

注意：若头节点为哨兵节点，则头节点是第一个节点但不是第一个存储实际数据的节点。头节点的具体语义取决于具体的上下文和链表的设计，需要注意辨别。

这样，我们就可以在单向循环链表中从任意一个节点出发，不断地遍历下一个节点，直到回到起点。循环链表如图7-1所示。

图7-1 单向循环链表

单向循环链表有两种实现方式：

（1）从零实现单向循环链表，包括其中所有的属性与方法。

（2）继承之前封装的普通单向链表（LinkedList），通过继承只实现差异化的部分。

方式一的从零实现较为麻烦，方式二采用继承形式，抽象复用相同部分的代码。方式二是更简便也值得推荐的，所以我们采用方式二。

使用方式二之前，需要对之前封装的普通单向链表采取一定的重构，使其单向循环链表继承使用可以更为契合。

7.1.2 单向链表代码重构

首先是链表的声明部分不变，代码如下：

▼
ts
复制代码
interface IList<T> {
  // peek
  peek(): T | undefined
  // 判断是否为空
  isEmpty(): boolean
  // 元素的个数
  size(): number
}

interface ILinkedList<T> extends IList<T> {
  append(value: T): void
  traverse(): void
  insert(value: T, position: number): boolean
  removeAt(position: number): T | null
  get(positon: number): T | null
  update(value: T, position: number): boolean
  indexOf(value: T): number
  remove(value: T): T | null
}

export default ILinkedList

所需实现的单向循环链表继承自普通单向链表（基础搭建）如下：

▼
ts
复制代码
// 导入普通链表用于被继承。
// 单向循环链表：CircularLinkedList
// 普通链表：LinkedList
class CircularLinkedList<T> extends LinkedList<T> {

}

1. 单向链表添加tail属性

接下来，需要对普通单向链表进行一定程度的修改，例如在普通单向链表中的head与length属性皆为private（私有属性），私有属性只能在当前类中使用，当单向循环链表继承自普通单向链表时，单向循环链表无法获取使用来自普通单向链表的私有属性。

因此我们需要将属性修饰符private修改为protected（受保护属性），受保护的属性允许子类访问（不允许外界访问）。

▼
ts
复制代码
protected head: Node<T> | null = null
protected length: number = 0

在单向循环链表中，需要实现尾节点指向第一个存储实际数据的节点，则一旦添加新节点就需要重新获取一次当前尾节点的信息。由于获取尾节点的需求频率提高，所以我们需要在普通单向链表中增添获取尾节点信息的方法或者属性。

▼
ts
复制代码
// 新增属性: 总是指向链表的位置
protected tail: Node<T> | null = null

2. append()方法重构

当我们在追加新节点（假设为D节点）时，tail属性需要指向成为新的尾节点的D节点。同理的，其余操作涉及尾节点的变动都需要让tail属性指向新的尾节点，其余两个操作如下：

（1）删除当前尾节点，则tail属性指向尾节点的上一节点。

（2）节点插入到尾节点之后，则tail属性指向新的尾节点。

因此tail属性涉及append()追加节点，insert()插入节点以及removeAt()删除节点三个方法的重构。

追加节点有两种情况：

（1）当前链表没有第一个存储实际数据的节点，则追加的新节点作为头节点（该头节点不为哨兵节点）。

（2）当前链表已有存储实际数据的节点，则追加的节点需要在尾节点之后。

append()追加节点方法重构前的代码如下：

▼
ts
复制代码
// 追加节点
append(value: T) {
  // 1.根据value创建一个新节点
  const newNode = new Node(value)

  // 2.判断this.head是否为null
  if (!this.head) {
    this.head = newNode
  } else {
    let current = this.head
    while (current.next) {
      current = current.next
    }

    // current肯定是指向最后一个节点的
    current.next = newNode
  }
  this.length++
}

首先将tail属性指向新的尾节点，关键代码如下：

▼
ts
复制代码
// 追加节点
append(value: T) {
  const newNode = new Node(value)
  if (!this.head) {
    this.head = newNode
    // tail属性指向新的尾节点
    this.tail = newNode
  } else {
    let current = this.head
    while (current.next) {
      current = current.next
    }
    // tail属性指向新的尾节点
    this.tail = newNode
    current.next = newNode
  }
  this.length++
}

由于可以直接获取到新的尾节点，则追加节点的第二种情况，无需每次都通过current指针遍历链表获取尾节点。则修改后代码如下：

▼
ts
复制代码
// 追加节点
append(value: T) {
  // 1.根据value创建一个新节点
  const newNode = new Node(value)

  // 2.判断this.head是否为null
  if (!this.head) {
    this.head = newNode
    this.tail = newNode
  } else {
    // 追加节点的第二种情况：追加的节点在当前尾节点之后
    this.tail!.next = newNode
    this.tail = newNode
  }
  this.length++
}

append()方法的两种追加节点的情况都意味着追加的节点成为新的尾节点，都需要将tail属性指向新的尾节点。则两个判断的this.tail = newNode（tail属性指向新的尾节点）可以合并处理。则步骤为：

（1）获取当前尾节点，在当前尾节点之后添加新节点。

（2）将追加的新节点设置为新的尾节点。

▼
ts
复制代码
// 追加节点
append(value: T) {
  const newNode = new Node(value)
  if (!this.head) {
    this.head = newNode
  } else {
    this.tail!.next = newNode
  }
  // 合并处理
  this.tail = newNode
  this.length++
}

3. insert()方法重构

insert()插入节点方法重构前的代码如下：

▼
ts
复制代码
// 插入方法:
insert(value: T, position: number): boolean {
  // 1.越界的判断
  if (position < 0 || position > this.size) return false

  // 2.根据value创建新的节点
  const newNode = new Node(value)

  // 3.判断是否需要插入头部
  if (position === 0) {
    newNode.next = this.head
    this.head = newNode
  } else {
    const previous = this.getNode(position - 1)
    newNode.next = previous!.next
    previous!.next = newNode
  }
  this.length++

  return true
}

将新节点插入到头部或者非尾节点的位置并不会影响tail属性指向尾节点。

需要考虑的是当新节点插入尾节点的时候，更新tail指向新节点。

▼
ts
复制代码
// 插入方法:
insert(value: T, position: number): boolean {
  if (position < 0 || position > this.length) return false
  const newNode = new Node(value)
  if (position === 0) {
    newNode.next = this.head
    this.head = newNode
  } else {
    const previous = this.getNode(position - 1)
    newNode.next = previous!.next
    previous!.next = newNode
	// 当新节点插入尾节点
    if (position === this.length) {
      this.tail = newNode
    }
  }
  this.length++
  return true
}

4. removeAt()方法重构

removeAt()删除节点方法重构前的代码如下：

▼
ts
复制代码
// 删除方法:
removeAt(position: number): T | null {
  // 1.越界的判断
  if (position < 0 || position >= this.size) return null

  // 2.判断是否是删除第一个节点
  let current = this.head
  if (position === 0) {
    this.head = current?.next ?? null
  } else {
    // 重构成如下代码
    const previous = this.getNode(position - 1)
    // 找到需要的节点
    previous!.next = previous?.next?.next ?? null
  }

  this.length--

  return current?.value ?? null
}

当删除到尾节点时，将tail属性指向尾节点的上一节点。当链表只有一个节点（存储数据的节点），即头节点与尾节点相同时，删除该节点则意味着链表无任何节点，尾节点也没有上一节点，需将tail属性置空。

▼
ts
复制代码
// 删除方法:
removeAt(position: number): T | null {
  if (position < 0 || position >= this.length) return null
  let current = this.head
  if (position === 0) {
    this.head = current?.next ?? null
    // 头节点与尾节点重合，删除该节点后，尾节点无上一节点，将tail属性置空。
    if (this.length === 1) {
      this.tail = null
    }
  } else {
    const previous = this.getNode(position - 1)
    current = previous!.next
    previous!.next = previous?.next?.next ?? null
	// 删除尾节点情况，将tail指向尾节点的上一节点
    if (position === this.length - 1) {
      this.tail = previous
    }
  }
  this.length--
  return current?.value ?? null
}

5. isTail()方法

接下来打算让循环链表继承自单向链表，还存在一些问题，例如遍历链表的traverse()方法，通过while去遍历，终止条件是current指针为空。但如果是循环链表的话，current通过.next不断的指向下一个，当指到尾节点后，接着会跳转到头节点，循环往复，从而陷入死循环。

▼
ts
复制代码
// 遍历链表的方法
traverse() {
  const values: T[] = []
  let current = this.head
  // 终止条件是current指针为空
  while (current) {
    values.push(current.value)
    current = current.next
  }
  console.log(values.join("->"))
}

因此为了兼容循环链表的情况，我们判断尾节点除了考虑单向链表，还需要考虑循环链表。所以需要一个新的判断当前节点是否为尾节点的isTail()方法。

判断单向链表的尾节点：current.next === null。

判断循环链表的尾节点：current.next === this.head。

单向链表与循环链表两种判断方式结合起来，代码显得较长，所以直接采用tail属性来判断。

▼
ts
复制代码
// 判断是否是最后一个节点
private isTail(node: Node<T>) {
  return this.tail === node
}

6. traverse()方法重构

接着需要依据新的判断尾节点的isTail()方法来重构所有涉及尾节点的2个方法：

（1）traverse()方法。

（2）indexOf()方法。

traverse()方法需要做出判断是否遍历到尾节点tail，是则将current指针置为null，退出循环；否则将current指针指向下一节点。

▼
ts
复制代码
while (current) {
  values.push(current.value)
  if (this.isTail(current)) { // 已经遍历最后一个节点
    current = null
  } else { // 不是最后一个节点
    current = current.next
  }
}

其次，循环链表遍历输出时，我们希望在输出尾节点后继续输出下一个头节点，从而形式一个完整的闭环。因此我们需要先判断处于循环链表的情况再输出头节点。输出内容来自values数组，所以获取头节点push到values数组的末端就行。

▼
ts
复制代码
// 循环链表
if (this.head && this.tail?.next === this.head) {
  values.push(this.head.value)
}

traverse()方法重构后的完整代码如下：

▼
ts
复制代码
// 遍历链表的方法
traverse() {
  const values: T[] = []
  
  let current = this.head
  while (current) {
    values.push(current.value)
    if (this.isTail(current)) { // 已经遍历最后一个节点
      current = null
    } else { // 不是最后一个节点
      current = current.next
    }
  }

  // 循环链表 需要同时满足两个条件
  if (this.head && this.tail?.next === this.head) {
    values.push(this.head.value)
  }
  
  console.log(values.join("->"))
}

traverse()方法在循环链表的效果如图7-2所示。既不会无限循环，也体现出ABCDA的遍历闭环效果。效果需要结合7.1.3小节的append()方法重构后来配合实现。

图7-2 traverse()方法在循环链表的效果

7. indexOf()方法重构

indexOf()方法重构前的代码如下：

▼
ts
复制代码
// 根据值, 获取对应位置的索引
indexOf(value: T): number {
  // 从第一个节点开始, 向后遍历
  let current = this.head
  let index = 0
  while (current) {
    if (current.value === value) {
      return index
    }
    current = current.next
    index++
  }
  return -1
}

可以看到重构前的indexOf()方法也是采用current指针不断遍历链表来查找是否有相等的值。但该做法一旦运用到循环链表中，就会失去终止条件，current.next会进入循环永无止境，因此需要利用tail属性添加新的终止条件。

终止条件为：当找到尾节点将current指针置空，退出循环。其余情况保持current对链表进行遍历寻找相等的值。

▼
ts
复制代码
// 根据值, 获取对应位置的索引
indexOf(value: T): number {
  // 从第一个节点开始, 向后遍历
  let current = this.head
  let index = 0
  while (current) {
    if (current.value === value) {
      return index
    }
    if (this.isTail(current)) {
      current = null
    } else {
      current = current.next
    }
    index++
  }
  return -1
}

在本次重构中，主要涉及新增tail受保护属性和isTail()方法，以及以下5个方法的重构：

（1）append()方法。

（2）traverse()方法。

（3）insert()方法。

（4）removeAt()方法

（5）indexOf()方法。

重构代码是一件较为繁琐的事情，一处变动就需要将涉及到变动的相关部分处处修改。因此在面对一个较大的项目时，提前构思好思路再写代码是更为节省精力的事情。

7.1.3 循环链表方法实现

在单向链表的基础上，循环链表有以下3个方法需要实现：

（1）append()方法。

（2）insert()方法。

（3）removeAt()方法。

循环链表由于尾节点指向头节点，因此涉及到头节点与尾节点的两种情况都需要注意，例如头节点变化，尾节点需要重新指向新的头节点。

循环链表的append()方法需要做出以下两步骤：

（1）将当前尾节点指向追加的新节点。

（2）将追加的新节点指向头节点。

实际只需要将追加的新节点指向头节点就可以了。当前尾节点会自动指向追加的新节点，即this.tail!.next = newNode部分。

▼
ts
复制代码
append(value: T) {
  const newNode = new Node(value)
  if (!this.head) {
    this.head = newNode
  } else {
    this.tail!.next = newNode
  }
  this.tail = newNode
  this.length++

  // 将追加的新节点指向头节点
  this.tail!.next = this.head
}

由于直接在原有代码上新增，未修改原有部分。因此基于继承的原理，可以采用super关键字来调用父类的构造函数append()方法，然后在加上原有代码新增的部分。

▼
ts
复制代码
class CircularLinkedList<T> extends LinkedList<T> {
  // 重新实现的方法: append方法
  append(value: T): void {
    super.append(value)
    // 拿到最后一个节点next指向第一个节点
    this.tail!.next = this.head
  }
}

循环链表的insert()方法处理新节点插入尾节点之后的情况，需要做出以下两步骤：

（1）tail指向新的尾节点（新节点）。

（2）新的尾节点指向头节点。

由于在单向链表已经重构过insert方法，做到tail指向新的尾节点，因此循环链表在继承单向链表的基础上只需要再实现新的尾节点指向头节点即可。

▼
ts
复制代码
insert(value: T, position: number): boolean {
  if (position < 0 || position > this.length) return false
  const newNode = new Node(value)
  if (position === 0) {
    newNode.next = this.head
    this.head = newNode
  } else {
    const previous = this.getNode(position - 1)
    newNode.next = previous!.next
    previous!.next = newNode
	// 当新节点插入尾节点
    if (position === this.length) {
      this.tail = newNode
    }
  }
  this.length++
  return true
}

insert()方法在循环链表中的代码如下所示：

isSuccess插入数据是否成功依旧需要返回，在返回信息的基础上，插入位置为尾节点或者无节点的情况下，将新的尾节点（当前尾节点的下一节点）指向头节点。

▼
ts
复制代码
class CircularLinkedList<T> extends LinkedList<T> {
  insert(value: T, position: number): boolean {
    const isSuccess = super.insert(value, position)
    if (isSuccess && (position === this.length - 1 || position === 0)) {
      this.tail!.next = this.head
    }
    return isSuccess
  }
}

insert()方法将节点"小余"插入头节点如图7-3所示。根据traverse()方法打印的首尾效果，尾节点成功指向头节点。

图7-3 insert()方法插入头节点

循环链表的removeAt()方法在删除头节点或者尾节点时，需要进行处理：

（1）删除头节点：尾节点指向新的头节点。

（2）删除尾节点：新的尾节点指向头节点。

removeAt()方法需要考虑删除头节点的情况，分别处理tail属性的指向问题。而删除尾节点的情况已经在单向链表的代码重构中实现，因此只需要考虑删除头节点的情况。

删除头节点，需要满足3个前置条件：

（1）value有值，即removeAt()方法有正常删除节点。

（2）tail有值（循环链表有可能存在无节点情况），确保链表还有尾节点，空值检查，防止TypeScript报错。

（3）删除头节点以及头节点与尾节点重合的情况。

▼
ts
复制代码
removeAt(position: number): T | null {
  const value = super.removeAt(position)
  if (value && this.tail && (position === 0 && position === this.length)) {
    this.tail.next = this.head
  }
  return value
}

完整重构后的单向链表代码如下所示：

▼
ts
复制代码
class Node<T> {
  value: T
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

interface IList<T> {
  // peek
  peek(): T | undefined
  // 判断是否为空
  isEmpty(): boolean
  // 元素的个数
  size(): number
}

interface ILinkedList<T> extends IList<T> {
  append(value: T): void
  traverse(): void
  insert(value: T, position: number): boolean
  removeAt(position: number): T | null
  get(positon: number): T | null
  update(value: T, position: number): boolean
  indexOf(value: T): number
  remove(value: T): T | null
}

// 2.创建LinkedList的类
export default class LinkedList<T> implements ILinkedList<T> {
  protected head: Node<T> | null = null
  protected length: number = 0

  // 新增属性: 总是指向链表的位置
  protected tail: Node<T> | null = null

  size() {
    return this.length
  }

  peek(): T | undefined {
    return this.head?.value
  }

  // 封装私有方法
  // 根据position获取到当前的节点(不是节点的value, 而是获取节点)
  protected getNode(position: number): Node<T> | null {
    let index = 0
    let current = this.head
    while (index++ < position && current) {
      current = current.next
    }
    return current
  }

  // 判断是否是最后一个节点
  private isTail(node: Node<T>) {
    return this.tail === node
  }

  // 追加节点
  append(value: T) {
    // 1.根据value创建一个新节点
    const newNode = new Node(value)

    // 2.判断this.head是否为null
    if (!this.head) {
      this.head = newNode
    } else {
      this.tail!.next = newNode
    }
    this.tail = newNode

    // 3.size++
    this.length++
  }

  // 遍历链表的方法
  traverse() {
    const values: T[] = []

    let current = this.head
    while (current) {
      values.push(current.value)
      if (this.isTail(current)) { // 已经遍历最后一个接地那
        current = null
      } else { // 不是最后一个节点
        current = current.next
      }
    }

    // 循环链表
    if (this.head && this.tail?.next === this.head) {
      values.push(this.head.value)
    }

    console.log(values.join("->"))
  }

  // 插入方法:
  insert(value: T, position: number): boolean {
    // 1.越界的判断
    if (position < 0 || position > this.length) return false

    // 2.根据value创建新的节点
    const newNode = new Node(value)

    // 3.判断是否需要插入头部
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else {
      const previous = this.getNode(position - 1)
      newNode.next = previous!.next
      previous!.next = newNode

      if (position === this.length) {
        this.tail = newNode
      }
    }
    this.length++

    return true
  }

  // 删除方法:
  removeAt(position: number): T | null {
    // 1.越界的判断
    if (position < 0 || position >= this.length) return null

    // 2.判断是否是删除第一个节点
    let current = this.head
    if (position === 0) {
      this.head = current?.next ?? null

      if (this.length === 1) {
        this.tail = null
      }
    } else {
      const previous = this.getNode(position - 1)
      current = previous!.next
      previous!.next = previous?.next?.next ?? null

      if (position === this.length - 1) {
        this.tail = previous
      }
    }

    this.length--

    return current?.value ?? null
  }

  // 获取方法:
  get(position: number): T | null {
    // 越界问题
    if (position < 0 || position >= this.length) return null

    // 2.查找元素, 并且范围元素
    return this.getNode(position)?.value ?? null
  }

  // 更新方法:
  update(value: T, position: number): boolean {
    if (position < 0 || position >= this.length) return false
    // 获取对应位置的节点, 直接更新即可
    const currentNode = this.getNode(position)
    currentNode!.value = value
    return true
  }

  // 根据值, 获取对应位置的索引
  indexOf(value: T): number {
    // 从第一个节点开始, 向后遍历
    let current = this.head
    let index = 0
    while (current) {
      if (current.value === value) {
        return index
      }

      if (this.isTail(current)) {
        current = null
      } else {
        current = current.next
      }

      index++
    }

    return -1
  }

  // 删除方法: 根据value删除节点
  remove(value: T): T | null {
    const index = this.indexOf(value)
    return this.removeAt(index)
  }

  // 判读单链表是否为空的方法
  isEmpty() {
    return this.length === 0
  }
}

export { }

继承自重构后单向链表的循环链表如下：

▼
ts
复制代码
import LinkedList from "./LinkedList.ts";

class CircularLinkedList<T> extends LinkedList<T> {
  // 重新实现的方法: append方法
  append(value: T): void {
    super.append(value)
    // 拿到最后一个节点next指向第一个节点
    this.tail!.next = this.head
  }
  traverse(): void {
    super.traverse()
  }
  insert(value: T, position: number): boolean {
    const isSuccess = super.insert(value, position)
    if (isSuccess && (position === this.length - 1 || position === 0)) {
      this.tail!.next = this.head
    }
    return isSuccess
  }
  removeAt(position: number): T | null {
    const value = super.removeAt(position)
    if (value && this.tail && (position === 0 && position === this.length)) {
      this.tail.next = this.head
    }
    return value
  }
}

const cLinkedList = new CircularLinkedList<string>()
cLinkedList.append('A')
cLinkedList.append('B')
cLinkedList.append('C')
cLinkedList.append('D')
cLinkedList.insert('小余', 0)
cLinkedList.traverse()

7.2 双向链表结构

7.2.1 双向链表的概念与特性

双向链表是一种链式存储结构，其每个节点除了包含数据域（data）外，还包含两个指针域：一个指向前驱节点的指针（prev），另一个指向后继节点的指针（next）。这种结构使得链表中的节点可以双向连接，即从头节点开始可以顺序遍历到尾节点，从尾节点开始也可以逆向遍历到头节点。与单向链表相比，双向链表在结构上更加对称，头节点的前驱指针和尾节点的后继指针通常指向空（null），以此标识链表的边界。

尽管双向链表在插入和删除节点时需要同时维护前驱和后继四个指针关系，实现复杂度稍高，且因多占用一个指针空间而具有更高的内存开销，但其在双向遍历、任意位置节点的高效访问以及操作灵活性上的优势，使得这些代价在实际应用中往往是可接受的。因此，双向链表特别适用于需要频繁双向查找、后退操作或复杂结构管理的场景，如浏览器的历史记录管理、双向队列（Deque）的实现等。

循环链表如图7-4所示。

图7-4 循环链表

7.2.2 双向链表节点封装

相对于单向链表的节点，双向链表的节点多一个指向前驱节点的指针（prev），因此需要对目前已有节点做一个封装。

单向链表的节点封装如下：

▼
ts
复制代码
export class Node<T> {
  value: T
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

由于单向链表使用的节点与双向链表有所冲突，所以我们不能直接在原有节点上直接修改。双向链表可以选择继承原有节点，在原有基础上去新增prev指针和重写next指针（接收的需要是双向链表的节点）。

双向链表的节点封装如下：

▼
ts
复制代码
export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null = null
  next: DoublyNode<T> | null = null
}
// 使用
const DNode = new DoublyNode('小余')
DNode.prev?.prev
DNode.next?.next

7.2.3 双向链表方法实现

基于双向链表的节点去创建链表如下：

原有单向链表一共3个受保护属性：head，length以及tail。其中head与tail属性的类型涉及到节点类型，需要重写为双向链表的节点。

▼
ts
复制代码
class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | null = null
  protected tail: DoublyNode<T> | null = null
}
const dLinkedList = new DoublyLinkedList<string>()

完成双向链表的基础创建后，因为双向链表中添加、删除方法的实现和单向链表有较大的区别，所以我们可以对其方法进行重新实现，主要为以下5个方法：

（1）append()方法：在尾部追加元素。

（2）prepend()方法：在头部添加元素。

（3）postTraverse()方法：从尾部遍历所有节点。

（4）insert()方法：根据索引插入元素。

（5）removeAt()方法：根据索引删除元素。

那么接下来我们就一个个实现以上这5个方法，其他方法都是可以继承的。由于ILinkedList父类的append()等方法中采用的是单向链表的节点，并不好调整，因此以下这5个方法都不采用继承+补充的方式。

1. append()方法

双向链表的append()方法需要考虑以下3种情况：

（1）追加第一个节点：双向链表无任何节点，head与tail暂时都指向null。需将两指针同时指向追加的第一个节点。

（2）追加其余节点：head节点指向头节点无需变动，tail节点的next指向新增的节点，新增节点的prev指向tail节点。

▼
ts
复制代码
append(value: T) {
  const newNode = new DoublyNode(value)
  if (!this.head) {
    this.head = newNode
    this.tail = newNode
  } else {
    this.tail!.next = newNode
    // 不能将父类对象赋值给子类，但可以将一个子类的对象，赋值给一个父类的类型（多态）
    // newNode.prev = this.tail
    // this.tail!.next!.prev = this.tail
    newNode.prev = this.tail
  }
  this.tail = newNode
  this.length++
}

在将新增节点的prev指向tail节点时，采用newNode.prev会有更直观的体现，但基于多态的原因会报错，如果想用这种写法。需要将newNode的类型定义重写在子类中，即head和tail在DoublyLinkedList类定义为DoublyNode类型。在一开始初始化双向链表时解决了该问题。

双向链表-append()方法效果如图7-5所示。

图7-5 双向链表-append()方法

2. prepend()方法

prepend()方法是用于在头部追加节点（追加的节点作为新的头节点），与append()方法在实现上有所相似。需要拆分成以下两点：

（1）当双向链表没有任何节点时。

prepend()与append()方法的做法一致，head与tail同时指向追加的节点。

（2）当双向链表存在一定节点时。

追加节点的next指向头节点，头节点的prev指向追加节点，最后将追加节点置为新的头节点。prepend()方法如图7-6所示。

图7-6 双向链表-prepend()方法

▼
ts
复制代码
prepend(value: T) {
    const newNode = new DoublyNode(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      // 追加节点的next指向头节点
      newNode.next = this.head
      // 头节点的prev指向追加节点
      this.head.prev = newNode
      // 追加节点置为新的头节点
      this.head = newNode
    }
    this.length++
  }

3. postTraverse()方法

我们在单向链表中有实现traverse()遍历方法，在双向链表中可以实现postTraverse()反向遍历方法（从尾节点遍历到头节点），反向遍历方法只有双向链表满足实行条件。

postTraverse()方法需要以下3步骤：

（1）获取链表的尾节点。

（2）根据链表的current指针和节点的prev向前遍历并输出。

（2）当遍历完头节点，退出遍历。

▼
ts
复制代码
postTraverse() {
    const values: T[] = []
    // 获取链表的尾节点
    let current = this.tail
    // 当节点值等于头节点时，退出遍历
    while (current) {
      values.push(current.value)
      // 根据链表的current指针和节点的prev向前遍历并输出
      current = current.prev
    }

    console.log(values.join("->"))
  }

4. insert()方法

双向链表的insert()方法-根据索引插入节点，需要分情况讨论：

（1）插入的位置是头节点。

（2）插入的位置是尾节点。

（3）插入的位置是其余节点。

当插入的位置是头节点时，可以直接调用prepend()方法；当插入的位置是尾节点时，可以调用append()方法；当插入的位置是其余节点，需要建立插入节点和前驱节点与后继节点的双向联系。

边界判断：当双向链表没有任何节点或者插入位置超出已有链表长度范围时，直接返回false。

插入的位置是其余节点时，我们需要做以下3步操作：

（1）获取插入位置的原先节点A以及插入位置前一个位置的节点B。

（2）插入节点的prev指向节点B，节点B的next指向插入节点。

（3）插入节点的next指向节点A，节点A的prev指向插入节点。

插入节点过程如图7-7所示。

图7-7 双向链表-prepend()方法

由于获取节点位置的getNode()方法是私有方法，需要将其修改为受保护方法。getNode()方法内部所采用的节点类型是单向链表的节点，所以需要将该方法类型断言为DoublyNode。

▼
ts
复制代码
// 根据索引插入元素
insert(value: T, position: number): boolean {
  if (position < 0 && position > this.length) return false

  if (position === 0) { // 插入的位置是头节点
    this.prepend(value)
  } else if (position === this.length) { // 插入的位置是尾节点
    this.append(value)
  } else { // 插入的位置是其余节点
    const newNode = new DoublyNode(value)
    // 获取插入位置的原先节点A
    const current = this.getNode(position) as DoublyNode<T>
    // 获取插入位置前一个位置的节点B，并将节点B的next指向插入节点
    current.prev!.next = newNode
    // 插入节点的next指向节点A
    newNode.next = current
    // 插入节点的prev指向节点B
    newNode.prev = current.prev
    // 节点A的prev指向插入节点（放到最后）
    current.prev = newNode
    // 放在其余节点的内部情况，因为prepend()和append()方法内部都有length++
    this.length++
  }

  return true
}

以上通过记录节点A（插入位置的原先节点）的方式来完成全部操作，整体连贯性更强，但这样操作就需要注意前后顺序，以免在改变指向的过程中，提前将指向节点B修改（current.prev = newNode）。除了该做法，还可以使用getNode()方法同时获取节点B，在代码层面上的可读性会更强，操作也不需要顾及前后顺序。

5. removeAt()方法

双向链表的removeAt()方法-根据索引删除节点，也分情况讨论：

（1）删除的是头节点。

（2）删除的是尾节点。

（3）删除的是其他节点。

删除头节点，双向链表有可能只有头节点，需要将this.head和this.tail都置空，其他情况（双向链表节点数量大于1）需要this.head指向新的头节点，然后将新的头节点的prev置空（新的头节点是双向链表原来的第二个节点，其prev指向原来的头节点）；

删除尾节点，需要this.tail指向新的尾节点，将新的尾节点的next置空（新的尾节点是双向链表原来的倒二个节点，其next指向原来的尾节点）；

删除其他节点，需要目标节点的前驱节点与后继节点完成双向对接。

最后需要与insert()方法一样，做好边界判断。

removeAt()方法的越界判断如下：

▼
ts
复制代码
removeAt(position: number): T | null {
    if (position < 0 || position >= this.length) return null
    return null
  }

删除节点三种情况的代码如下：

▼
ts
复制代码
// 根据索引删除元素
removeAt(position: number): T | null {
  if (position < 0 || position >= this.length) return null

  let current = this.head
  if (position === 0) { // 删除的是头节点
    if (this.length === 1) { // 双向链表只有头节点
      this.head = null
      this.tail = null
    } else { // 双向链表节点数量超过1
      this.head = this.head!.next // 指向新的头节点
      this.head!.prev = null // 新的头节点prev置空
    }
  } else if (position === this.length - 1) { // 删除的是尾节点
    current = this.tail
    this.tail = this.tail!.prev // tail指向新尾节点
    this.tail!.next = null // 新尾节点的next置空
  } else { // 删除的是其他节点
    current = this.getNode(position) as DoublyNode<T> // 获取删除节点位置
    current.next!.prev = current.prev // 删除节点的前一节点与后一节点对接
    current.prev!.next = current.next // 删除节点的后一节点与前一节点对接
  }

  this.length--

  return current?.value ?? null
}

删除节点有一处地方很有意思，删除的是双向链表的头节点（链表节点数量超过1），只将新头节点的prev置空。那么删除目标（原来的头节点）的next还存在指向，不置空吗？并不需要，因为此时已经没有节点指向原来的头节点了，它处于不可达状态，已经满足垃圾回收的条件。无需再将next置空，removeAt()方法只将新头节点的prev置空如图7-8所示。后续删除尾节点也是同样的原理。

图7-8 双向链表-removeAt()方法

由于最后需要返回删除的节点值，因此在删除节点之前，需要通过current将删除的节点记录下来，而current的默认值是头节点，因此头节点无需额外记录。

6. 其他方法

双向链表的其余方法可以直接继承单向链表的方法，测试代码如下：

▼
ts
复制代码
console.log('------------ 测试get ------------')
console.log(dLinkedList.get(0))
console.log(dLinkedList.get(1))
console.log(dLinkedList.get(2))

console.log('------------ 测试update ------------')
dLinkedList.update("why", 1)
dLinkedList.update("xiaoyu", 2)
dLinkedList.traverse()


console.log('------------ 测试indexOf ------------')
console.log(dLinkedList.indexOf("cba"))
console.log(dLinkedList.indexOf("why"))
console.log(dLinkedList.indexOf("xiaoyu"))
console.log(dLinkedList.indexOf("james"))


console.log('------------ 测试remove ------------')
dLinkedList.remove("why")
dLinkedList.remove("cba")
dLinkedList.remove("xiaoyu")
dLinkedList.traverse()
console.log(dLinkedList.isEmpty())
console.log(dLinkedList.size())

完整的双向链表代码如下：

▼
ts
复制代码
// 根据自己实际情况导入
import LinkedList, { DoublyNode } from "./LinkedList.ts";

class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | null = null
  protected tail: DoublyNode<T> | null = null

  append(value: T) {
    const newNode = new DoublyNode(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail!.next = newNode
      newNode.prev = this.tail
    }
    this.tail = newNode
    this.length++
  }
  prepend(value: T) {
    const newNode = new DoublyNode(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.next = this.head
      this.head.prev = newNode
      this.head = newNode
    }
    this.length++
  }
  postTraverse() {
    let current = this.tail
    const values = []
    while (current) {
      values.push(current.value)
      current = current.prev
    }
    console.log(values.join("->"))
  }
  insert(value: T, position: number): boolean {
    if (position === 0) {
      this.prepend(value)
    } else if (position === this.length) {
      this.append(value)
    } else {
      const newNode = new DoublyNode(value)
      const current = this.getNode(position) as DoublyNode<T>

      current.prev!.next = newNode
      newNode.next = current
      newNode.prev = current.prev
      current.prev = newNode

      this.length++
    }
    return true
  }
  removeAt(position: number): T | null {
    if (position < 0 || position >= this.length) return null

    let current = this.head
    if (position === 0) { // 删除的是头节点
      if (this.length === 1) { // 双向链表只有头节点
        this.head = null
        this.tail = null
      } else { // 双向链表节点数量超过1
        this.head = this.head!.next // 指向新的头节点
        this.head!.prev = null // 新的头节点prev置空
      }
    } else if (position === this.length - 1) { // 删除的是尾节点
      current = this.tail
      this.tail = this.tail!.prev // tail指向新尾节点
      this.tail!.next = null // 新尾节点的next置空
    } else { // 删除的是其他节点
      current = this.getNode(position) as DoublyNode<T> // 获取删除节点位置
      current.next!.prev = current.prev // 删除节点的前一节点与后一节点对接
      current.prev!.next = current.next // 删除节点的后一节点与前一节点对接
    }

    this.length--

    return current?.value ?? null
  }
}
const dLinkedList = new DoublyLinkedList<string>()

链表的学习到这里就结束了，在7.1小节学习了循环链表的概念，重构了单向链表的代码，在7.2小节利用重构后的代码，进一步实现双向链表以及对应与单向链表有所差异化的方法实现。接下来我们会开始学习堆结构。

7.1 循环链表结构

7.1.1 循环链表的概念与特性

7.1.2 单向链表代码重构

1. 单向链表添加tail属性

2. append()方法重构

3. insert()方法重构

4. removeAt()方法重构

5. isTail()方法

6. traverse()方法重构

7. indexOf()方法重构

7.1.3 循环链表方法实现

7.2 双向链表结构

7.2.1 双向链表的概念与特性

7.2.2 双向链表节点封装

7.2.3 双向链表方法实现

1. append()方法

2. prepend()方法

3. postTraverse()方法

4. insert()方法

5. removeAt()方法

6. 其他方法

目录

目录

第7章 高阶链表结构

7.1 循环链表结构

7.1.1 循环链表的概念与特性

7.1.2 单向链表代码重构

1. 单向链表添加tail属性

2. append()方法重构

3. insert()方法重构

4. removeAt()方法重构

5. isTail()方法

6. traverse()方法重构

7. indexOf()方法重构

7.1.3 循环链表方法实现

7.2 双向链表结构

7.2.1 双向链表的概念与特性

7.2.2 双向链表节点封装

7.2.3 双向链表方法实现

1. append()方法

2. prepend()方法

3. postTraverse()方法

4. insert()方法

5. removeAt()方法

6. 其他方法

目录

目录

第7章高阶链表结构