线性数据结构

第一章：栈

一、是什么

栈（Stack）是线性的数据结构，也是最基本的数据结构。特点：

FILO：first in last out，先进后出，最先进入栈的元素必须等到所有后进入的元素出栈之后才能被移除。
LIFO：last in first out，后进先出，新元素总是被放到栈顶，元素的访问和移除也始终发生在栈顶。
栈的大小：栈的大小通常是动态的，它可以根据需要增长或缩小（取决于栈的实现，栈可以是基于数组或链表的）。

栈主要支持以下几种基本操作：

push：将一个元素添加到栈的顶端。
pop：移除并返回栈顶元素。
peek（或 top）：返回栈顶元素但不移除它。
isEmpty：检查栈是否为空。
size：返回栈中元素的数量。

应用场景：历史记录、撤销操作 ……

二、代码实现

1. 数组版

1）类型定义

因为每个数据结构都有一些相同的操作，所有把这些通用的操作抽取出来。

typescript

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

定义栈特有的操作。

typescript

import IList from "./IList"

// 定义栈的结构
interface IStack<T> extends IList<T> {
  push(element: T): void
  pop(): T | undefined
}

export default IStack

2）实现栈

typescript

import IStack from "./IStack"

// 封装一个栈: TypeScript => AnyScript
class ArrayStack<T> implements IStack<T> {
  // 定义一个数组/链表, 用于存储元素
  private data: T[] = []

  // 实现栈中相关的操作方法
  // push方法: 将一个元素压入到栈中
  push(...elements: T[]): void {
    this.data.push(...elements)
  }

  // pop方法: 将栈顶的元素弹出栈(返回出去, 并且从栈顶移除掉)
  pop(): T | undefined {
    return this.data.pop()
  }

  // peek方法: 看一眼栈顶元素, 但是不进行任何的操作
  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.data[this.data.length - 1]
  }

  // isEmpty: 判断栈是否为空
  isEmpty(): boolean {
    return this.data.length === 0
  }

  // 返回栈的数据个数
  size(): number {
    return this.data.length
  }
}

export default ArrayStack

2. 代码实现 - 链表

略。

三、思维训练

1. 十进制转二进制

typescript

import ArrayStack from "./ArrayStack"

function decimalToBinary(decimal: number): string {
  // 1.创建一个栈, 用于存放余数
  const stack = new ArrayStack<number>()

  // 2.使用循环: 
  // while: 不确定次数, 只知道循环结束跳转 
  // for: 知道循环的次数时
  while (decimal > 0) {
    const result = decimal % 2
    stack.push(result)

    decimal = Math.floor(decimal / 2)
  }

  // 3.所有的余数都已经放在stack中, 以此取出即可
  let binary = ''
  while (!stack.isEmpty()) {
    binary += stack.pop()
  }

  return binary
}

2. 有效的括号

typescript

import ArrayStack from "./ArrayStack"

function isValid(s: string): boolean {
  // 1.创建栈结构
  const stack: string[] = []

  // 2.遍历s中的所有的括号
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    switch (c) {
      case "(":
        stack.push(")")
        break
      case "{":
        stack.push("}")
        break
      case "[":
        stack.push("]")
        break
      default:
        if (c !== stack.pop()) return false
        break
    }
  }

  return stack.length === 0
}

第二章：队列

一、普通队列

1. 是什么

队列结构也是一种逻辑结构，它遵循先进先出（FIFO, First In First Out）的原则。队列中的元素总是从队列的前端（称为“队首”）被移除，而新的元素则被添加到队列的后端（称为“队尾”）。因此，第一个进入队列的元素会最先被移除，类似于排队等候的场景。

队列结构特点

先进先出（FIFO）：元素会按照顺序被处理，第一个进入队列的元素最先被移除。
队首和队尾：元素从队尾添加进入，从队首被移除。
动态大小。

队列的基本操作

队列的基本操作包括以下几种：

enqueue（入队）：添加一个元素到队尾。
dequeue（出队）：移除并返回队首的元素。
peek（或 front）：返回队首的元素，但是不移除。
back：返回队尾的元素，但是不移除。
isEmpty：是否为空。
size：返回队列中元素的数量。

应用场景：事件循环、动画队列、缓存系统 ……

2. 代码实现

1）数组版

[1] 类型定义

typescript

import IList from "./IList"

interface IQueue<T> extends IList<T> {
  // 入队方法
  enqueue(element: T): void
  // 出队方法
  dequeue(): T | undefined
}

export default IQueue

[2] 编写 ArrayQueue

typescript

import IQueue from "./IQueue"

class ArrayQueue<T> implements IQueue<T> {
  // 内部是通过数组(链表)保存
  private data: T[] = []

  enqueue(...elements: T[]): void {
    this.data.push(...elements)
  }

  dequeue(): T | undefined {
    return this.data.shift()
  }

  peek(): T | undefined {
    return this.isEmpty()? undefined : this.data[0]
  }

  back(): T | undefined {
    return this.isEmpty()? undefined : this.data[this.size() - 1];
  }

  isEmpty(): boolean {
    return this.data.length === 0
  }

  size(): number {
    return this.data.length
  }
}

export default ArrayQueue

2）链表版

略。

3. 思维训练

1）击鼓传花游戏

在这个游戏中，孩子们围成一个圆圈，把花尽快的传递给旁边的人。某一时刻传花停止，这个时候花在谁的手里，谁就退出圆圈。重复这个过程，直到只剩下一个孩子就是胜利者。

实现思路

使用 CircularQueue 来管理玩家：
- enqueue 添加所有玩家。
- dequeue 移除当前持有花朵的玩家。
- front 获取当前持有花朵的玩家。
模拟传递过程：每轮传递花朵 随机传递一段时间，循环出队并入队，模拟花朵在队列中的传递。
移除淘汰者：在传递停止时，当前持有花朵的玩家被淘汰（dequeue）。
循环直到队列中剩下一个玩家：最后一个玩家是胜利者。

javascript

const CircularQueue = require("./CircularQueue.js");

/**
 * 
 * @param {*} players 玩家列表
 * @param {*} minPass 最小传花次数
 * @param {*} maxPass 最大传花次数
 */
async function jiguchuanhua(players, minPass = 3, maxPass = 8) {

    // 创建一个循环队列
    let queue = new CircularQueue(players.length);
    // 让所有玩家入队
    for(let p of players) {
        queue.enqueue(p);
    }

    console.log("游戏开始！当前的玩家有：", queue.toString());

    // 开始游戏
    while(queue.size() > 1){
        // 继续传花
        // 每次传花的时间长短是不一样的，意味着传花的次数也是不一样的
        // 生成3～8之间的随机数
        let passCount = Math.floor(Math.random() * (maxPass - minPass + 1)) + minPass;
        console.log("传花次数：", passCount);

        // 开始传递 passCount 次传花
        for(let i = 0; i < passCount; i++) {
            await new Promise((resolve)=>setTimeout(resolve, 500));
            console.log("🎵 鼓声响起 🎵");
            // 当前持花者出队
            let currentHolder = queue.dequeue(); // 从队列的队首取出一个元素
            queue.enqueue(currentHolder); // 将取出的元素再次入队到队尾
            console.log(`🌹 ${currentHolder} 将花递给了 ${queue.front()} 🌹`);
        }

        // 从上面的 for 循环出来后，说明传花次数已经达到了 passCount
        // 选出淘汰者，淘汰者就是当前队首的人
        let eliminated = queue.dequeue();
        console.log(`🔴 ${eliminated} 被淘汰了 🔴`);

        // 显示当前队列的情况
        console.log(queue.toString());
    }

    // 如果代码来到这里，说明队列里面只剩下一个人了
    // 游戏结束
    let winner = queue.front(); // 从队列中将胜利者取出
    console.log("游戏结束，胜利者是：", winner);
}

const players = [
  "张三",
  "李四",
  "王五",
  "赵六",
  "孙七",
  "周八",
  "吴九",
  "郑十",
];

jiguchuanhua(players);

2）回文检查器

所谓回文，指的是：

正反都能读通的单词、词组、数或者一系列字符的序列，例如 madam 或者 racecar。

有不同的算法可以检查一个词组或字符串是否为回文。最简单的方式是将字符串反向排列并检查它与原来的字符是否相同。如果两者相同，那么它就是一个回文。我们也可以用栈来完成，但是利用数据结构来解决这个问题的话，那还是双端队列最简单、最合适。

代码实现

javascript

const Deque = require("./Deque.js");

function isPalindrome(str){
  // 防御性处理
  if(str === undefined || str === null || str.length === 0){
    return false;
  }

  // 判断该字符串是否是回文字符串
  const deque = new Deque(); // 先创建一个双端队列
  // 将字符串全部转为小写，并且去除了空格
  const lowerStr = str.toLocaleLowerCase().split(" ").join("");
  let isEuqal = true; // 假设是回文字符串
  let firstChar = null; // 存储前面的字符
  let lastChar = null; // 存储后面的字符
  // 将字符串的每一位入队
  for(let i = 0; i < lowerStr.length; i++){
    deque.addBack(lowerStr.charAt(i));
  }

  while(deque.size() > 1 && isEuqal){
    // 从双端队列的队首取一个字符
    firstChar = deque.removeFront();
    // 从双端队列的队尾取一个字符
    lastChar = deque.removeBack();
    if(firstChar !== lastChar){
      isEuqal = false;
    }
  }

  return isEuqal;
}

二、循环队列

1. 是什么

循环队列是一种利用固定大小的数组实现队列操作的数据结构，但它采用了“环形”思想，使得数组的末尾与开头相连，从而充分利用了所有存储空间。

普通队列与循环队列的差异

普通队列：使用数组来实现，随着元素不断出队，数组前面部分就空闲了（特别是像 Java、C++ 这一类有标准数组数据结构的语言）。当然，可以将后面的元素往前面移动，但是这里又涉及到了移动相关的操作。
循环队列：利用环形结构，队尾到达数组末尾之后，新的入队操作会自动写入到数组起始的位置。

循环队列特点

固定容量与环形结构
- 固定容量
- 环形思想：实际上都是通过模运算来计算新入队的元素的下标位置
指针管理：通常使用两个变量：
- 队头指针（front）：指向队列的第一个元素
- 元素计数（rear/count）：记录当前队列有多少个元素，方便后面做模运算
- 模运算，使得指针在数组边界“循环”，避免了普通队列中出队后前部空间无法再利用的问题。
高效操作

基本操作

队列的基本操作包括以下几种：

enqueue（入队）：添加一个元素到队尾
dequeue（出队）：移除并返回队首的元素
peek（或 front）：返回队首的元素，但是不移除
back：返回队尾的元素，但是不移除
isEmpty：是否为空
size：返回队列中元素的数量
isFull：是否存满

2. 实现思路

假设有一个大小为 5 的队列，我们依次给对队列执行以下操作：

1）普通队列

基于固定数组，未使用循环策略

入队操作：将元素 A、B、C 依次入队
```
[A, B, C, _, _]
```
1
出队操作：出队两次，把 A 和 B 出队
```
[_, _, C, _, _]
```
1
现在随着 A 和 B 的出队，前面两个位置就空出来了
再次入队操作：入队 D 和 E 元素
```
[_, _, C, D, E]
```
1
现在这个结构就没有办法再入队新元素，已经满了。除非将后面的元素全部往前面移动：
```
[C, D, E, _, _]
```
1

2）循环队列

同样大小为 5 的循环队列，进行相同的操作：

入队操作：将元素 A、B、C 依次入队
```
[A, B, C, _, _]
```
1
- frontIndex：0
- count：3
- maxSize：5
出队操作：出队两次，把 A 和 B 出队
```
[_, _, C, _, _]
```
1
这里就会更新队首指针：新队首指针 = (旧队首指针 + 1) % maxSize
- A 元素出队的时候：新队首指针 = (0 + 1) % 5 = 1
- B 元素出队的时候：新队首指针 = (1 + 1) % 5 = 2
再次入队操作：之后新元素入队，放入位置的计算公式 (队首指针 + count) % maxSize
- 新元素 D 入队：(2 + 1) % 5 = 3
```
[_, _, C, D, _]
```
  1
  - frontIndex：0
  - count : 2
- 新元素 E 入队：(2 + 2) % 5 = 4
```
[_, _, C, D, E]
```
  1
  - count：3
- 新元素 F 入队：(2 + 3) % 5 = 0
```
[F, _, C, D, E]
```
  1
  - count: 4
- 新元素 G 入队：(2 + 4) % 5 = 1
```
[F, G, C, D, E]
```
  1
  - count: 5

通过循环队列这种计算方式，就不需要将后面的元素全部往前面移动，可以通过模运算计算出每次新元素应该入队的正确位置。

3）代码实现

javascript

class CircularQueue{
  constructor(maxSize = 10){
    this.maxSize = maxSize;
    this.queue = new Array(maxSize);
    // 队首指针
    this.frontIndex = 0;
    // 队列元素计数
    this.count = 0
  }

  // 一些辅助方法：size、isEmpty、isFull
  size(){
    return this.count;
  }
  isEmpty(){
    return this.count === 0;
  }
  isFull(){
    return this.count === this.maxSize;
  }

  // 新元素入队
  enqueue(item){
    if(this.isFull()){
      // 进入此分支，说明队列已满
      throw new Error("队列已满");
    }

    // 计算新元素应该存储的索引位置
    let index = (this.frontIndex + this.count) % this.maxSize;
    this.queue[index] = item;
    this.count++;
  }

  // 元素出队
  dequeue(){
    if(this.isEmpty()){
      return undefined;
    }
    let item = this.queue[this.frontIndex]; // 取出队首的元素
    this.queue[this.frontIndex] = undefined; // 清除当前队首元素
    this.frontIndex = (this.frontIndex + 1) % this.maxSize; // 更新存储队首位置的变量
    this.count--; // 更新个数
    return item;
  }

  // 获取队首的元素，但是不移除
  peek(){
    return this.isEmpty() ? undefined : this.queue[this.frontIndex];
  }

  // 获取队尾的元素，但是不移除
  // 队尾元素的索引计算公式：(frontIndex + count - 1) % maxSize
  back(){
    if(this.isEmpty()) return undefined;
    let index = (this.frontIndex + this.count - 1) % this.maxSize;
    return this.queue[index];
  }

  clear(){
    // 清空队列，全部还原
    this.queue = new Array(this.maxSize);
    this.frontIndex = 0;
    this.count = 0;
  }

  // 显示当前队列信息 (需要以元素正确的顺序显示)
  print(){
    // 1.当前数组里面的元素  2.元素的正确顺序
    console.log(this.queue);
    for(let i = 0; i < this.count; i++){
      // 计算正确的下标，然后打印出来
      let index = (this.frontIndex + i) % this.maxSize;
      console.log(this.queue[index] + " ");
    }
  }
}

三、双端队列

双端队列，英语为 double-ended queue，简称 deque。这是一种允许在两端（队列的前端和队列的后端）进行插入和删除操作的数据结构。它既能满足队列的先进先出（FIFO）原则，也能实现栈的后进先出（LIFO）操作，因此在实际应用中非常灵活。

现实生活中的例子

想象一个排队购票的场景 —— 通常我们从队尾进入队伍，但在某些情况下，例如一个刚买完票的人需要补充一些信息，可以重新回到队伍前面；又如队伍末尾的人如果赶时间，可以直接离开队伍。

双端队列常见方法

addFront(element)：该方法在双端队列的前端添加新的元素。
addBack(element)：该方法在双端队列后端添加新的元素。
removeFront()：该方法会从双端队列前端移除第一个元素。
removeBack()：该方法会从双端队列后端移除第一个元素。
peekFront()：该方法会返回双端队列前端的第一个元素。
peekBack()：该方法会返回双端队列后端的第一个元素。

代码实现

javascript

class Deque{
  constructor(){
    this.frontIndex = 0; // 指向队首元素的索引
    this.backIndex = 0; // 指向队尾元素的下一个可插入的位置
    this.items = {}; // 存储双端队列里面的所有元素
  }

  // 先实现一些辅助方法：size、isEmpty、clear
  size(){
    return this.backIndex - this.frontIndex;
  }
  isEmpty(){
    return this.size() === 0;
  }
  clear(){
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  // 添加到前面
  addFront(item){
    // 1. 如果队列为空，那么添加到前端和后端的效果是一样的
    if(this.isEmpty()){
      this.addBack(item);
      return;
    }

    // 2. 如果队列非空，并且 frontIndex > 0
    // 我们可以在 frontIndex - 1 位置添加新的元素
    if(this.frontIndex > 0){
      this.frontIndex--;
      this.items[this.frontIndex] = item;
      return;
    }

    // 3. 如果 frontIndex === 0
    // 我们需要将所有的元素向后面移动，为索引为 0 的位置腾出空间
    for(let i = this.backIndex; i > 0; i--){
      this.items[i] = this.items[i - 1];
    }
    // 更新队尾的索引，因为所有元素都向后移动了
    // 所以 backIndex 需要更新
    this.backIndex++;
    this.frontIndex = 0;
    this.items[this.frontIndex] = item;
  }

  // 添加到后面
  addBack(item){
    this.items[this.backIndex] = item;
    this.backIndex++;
  }

  removeFront(){
    if(this.isEmpty()){
      return undefined;
    }
    // 取出队首的元素
    const result = this.items[this.frontIndex];
    // 需要删除这个元素
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return result;
  }

  removeBack(){
    if(this.isEmpty()){
      return undefined;
    }
    this.backIndex--; // 现在指向队尾元素
    // 取出队尾
    const result = this.items[this.backIndex];
    delete this.items[this.backIndex];
    return result;
  }

  peekFront(){
    if(this.isEmpty()){
      return undefined;
    }
    return this.items[this.frontIndex];
  }

  peekBack(){
    if(this.isEmpty()){
      return undefined;
    }
    return this.items[this.backIndex - 1];
  }

  // 返回队列的字符串表示
  toString(){
    if (this.isEmpty()) {
      return '';
    }
    // 先把队首元素作为字符串的起始
    let objString = `${this.items[this.frontIndex]}`;
    // 从队首下一位遍历到队尾
    for (let i = this.frontIndex + 1; i < this.backIndex; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

第三章：链表

在本科教材中，把链表与数组统称为线性表。因此线性表有顺序存储和链式存储之分。

一、是什么

链表与数组的区别

链表也是存储元素的集合，数组在内存中是一段连续的空间，但是链表在内存中是非连续的空间。

如何存储数据的？

链表是由一个一个节点组成。链表中每个节点是如何找到下一个节点的？

在链表中，每个节点就由两个部分组成：

存储具体值。
下一个节点的内存地址。

正因为这个特征，链表在查询、新增、删除方面刚好和数组相反。

数组
- 查找：速度很快，因为只需要偏移 xxx 个地址单位就可以获取值。
- 新增和删除：就比较慢，后面所有的元素涉及到后移或者前移。
链表
- 查找：比较麻烦，需要从头节点一个一个进行查找。
- 新增和删除：比较方便，直接修改节点的 next 值（内存地址的指向）就可以了。

并且数组和链表对应的是在内存中真实的存储数据的两种结构方式（物理结构）。

链表常见的形式

单项链表：每个节点包含下一个节点的地址。
双向链表：每个节点会包含上一个节点和下一个节点的地址。

二、单向链表

1. 是什么

单向链表（Singly Linked List）每个元素都包含 两个部分：数据部分 和 指向下一个元素的指针（通常称为 next）。链表的每个节点都包含数据并且指向下一个节点，这样形成了一个链式的结构，方便在任意位置进行插入和删除操作。

单向链表的特点

线性结构：数据元素是线性排列的，但与数组不同的是，链表的元素并不一定在内存中连续存储。
动态大小：链表的大小在运行时可以动态变化，元素的插入和删除不会像数组一样造成内存的重新分配。
插入和删除高效：在已知节点的情况下，插入和删除元素的时间复杂度为 O(1)，但如果要访问某个节点时，需要遍历链表。

2. 代码实现

1）基础框架搭建

javascript

// 首先需要一个节点
class Node {
  // 接收该节点要存储的数据
  constructor(data) {
    this.data = data; // 当前节点存储的数据
    this.next = null; // 下一个节点的地址
  }
}

// 单向链表类
class LinkedList{
  constructor(){
    this.head = null; // 链表的头节点
    this.size = 0; // 链表的长度
  }

  // 打印链表数据
  print(){
    // 无外乎就是遍历所有的节点，通过 next 就可以找到下一个节点
    let current = this.head; // 一开始从头节点开始
    let result = []; // 存放所有节点的值
    while(current){
      result.push(current.data);
      current = current.next;
    }
    // 出了 while 之后，说明遍历节点结束
    console.log(result.join(" -> ") + " -> null");
  }
}

module.exports = {
  Node, LinkedList
}

javascript

const { Node, LinkedList } = require('./LinkedList.js');
const ll = new LinkedList(); // 拿到一个链表的实例对象
// 有3个节点
const n1 = new Node(1);
const n2 = new Node(2);
const n3 = new Node(3);
n1.next = n2;
n2.next = n3;
ll.head = n1;

2）链表的新增

新增节点到最后

javascript

// 新增一个指定数据的节点
// 放到当前链表的最后
add(data){
  // 首先需要生成一个节点
  const newNode = new Node(data);
  // 需要判断新增的这个节点是不是头节点
  if(!this.head){
    // 如果进入此分支，说明当前的单向链表是空的
    // 当前这个节点应该是头节点
    this.head = newNode;
  } else {
    // 说明当前的单向链表不是空的
    // 将节点添加到最后
    let current = this.head;
    while(current.next){
      current = current.next;
    }
    // 退出上面 while 循环的时候，current 是最后一个节点
    current.next = newNode;
  }
  this.size++;
}

新增节点放到指定的位置

javascript

// 接收两个参数
// 1. 数据
// 2. 添加到哪个位置
addAt(data, index){
  // 安全性处理
  if(index < 0 || index > this.size){
    throw new Error("索引值无效");
  }

  const newNode = new Node(data); // 新创建一个节点
  let current = this.head; // 一开始 current 指向头节点
  let counter = 0; // 计数器，对链表节点进行计数，类似于数组的下标

  // 下面就是插入的操作。插入仍然是分为是否是头节点位置
  if(index === 0){
    // 在头部插入
    // 插入的新节点会成为新的头节点
    newNode.next = this.head;
    this.head = newNode; // 更新头节点的值
  } else {
    // 链表后面部分插入，需要遍历到指定的位置
    while(current){
      if(counter === index - 1){ // current 为 preNode
        // 做插入操作
        newNode.next = current.next;
        current.next = newNode;
        break;
      }
      current = current.next;
      counter++;
    }
  }
  this.size++;
}

3）链表的删除

删除指定数据的节点

javascript

// 接收1个参数
// 要删除的节点对应数据是什么
remove(data){
  let current = this.head; // 一开始指向头节点
  let previous = null; // 暂存上一个节点

  while(current !== null){
    if(current.data === data){
      // 说明当前的这个 current 所对应的节点是要删除的节点
      if(previous === null){
        // 说明删除的节点是头节点
        this.head = current.next;
      } else {
        // 不是头节点
        previous.next = current.next;
      }
      this.size--;
      return current.data;
    }
    previous = current; // 先暂存该节点
    current = current.next; // 跳入下一个节点
  }
}

删除指定位置的节点

javascript

// 接收1个参数，指定的位置
removeAt(index){
  if(index < 0 || index >= this.size){
    throw new Error("索引值无效");
  }
  let current = this.head; // 一开始指向头节点
  let previous = null; // 暂存上一个节点
  if(index === 0){
    // 说明要删除的是头节点
    this.head = current.next;
  } else {
    // 说明不是头节点，需要遍历到指定的位置
    for(let i = 0; i < index; i++){
      previous = current;
      current = current.next;
    }
    // 跳出 for 循环的时候，current 是当前要删除的这个节点
    // previous 是当前要删除的节点的前一个节点
    previous.next = current.next;
  }
  this.size--;
  return current.data;
}

4）链表的反转

[1] 循环

变量：当前所在节点、下一个节点、前一个节点

步骤：

保存 next 节点，防止丢失。
修改 current.next 节点为 previous 节点。
修改 previous 为 current。
修改 current 为 next。

javascript

reverse(){
  if(!this.head) return; // 如果是空链表，直接返回

  // 没有进入上面的 if，说明链表有东西，进行反转操作
  let current = this.head;
  let previous = null; // 保存上一个节点
  let next = null; // 保存下一个节点

  while(current !== null){
    // 进行反转操作
    next = current.next; // 将当前节点原本的下一个节点暂存
    current.next = previous;
    previous = current;
    current = next;
  }

  // 重置头节点
  this.head = previous;
}

/*
  1 --> 2 --> 3
  3 --> 2 --> 1 --> null
  current: null
  previous: 3
  next: null
  this.head = 3
*/

5）链表的置换

交换链表里面的两个节点

javascript

// 接收参数: 要交换的两个节点的下标，下标是从 0 开始
swap(index1, index2){
  if(index1 === index2) return false; // 如果索引相等，不需要交换
  if(index1 < 0 || index1 >= this.size || index2 < 0 || index2 >= this.size){
    throw new Error("索引无效");
  }

  // 代码走到这一步，说明索引是没有问题的
  // 开始进行交换
  let current = this.head; // 一开始指向头节点
  let counter = 0; // 计数器，靠它找到对应下标的节点
  let node1 = null; // 存储index1对应的节点
  let node2 = null; // 存储 index2 对应的节点

  // 这个while循环主要是寻找节点
  while(current !== null){
    if(counter === index1) node1 = current;
    if(counter === index2) node2 = current;
    if(node1 && node2) break; // 两个节点都找到了，就退出
    current = current.next;
    counter++;
  }

  if(node1 && node2){
    // 交换两个节点的数据
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }

  return false;
}

React 从 16 版本开始，引入了一个 Fiber 的架构，Fiber 就是一个节点，所有的 Fiber 节点就是使用单向链表连接起来的。

javascript

function FiberNode(tag, pendingProps, key, mode) {
  // ...
 
  // 周围的 Fiber Node 通过链表的形式进行关联
  this.return = null; // 指向父节点
  this.child = null; // 指向子节点
  this.sibling = null; // 指向兄弟节点
  this.index = 0;

  // ...
}

假设有如下的 html 结构：

html

<div>
  <p></p>
  <ul>
    <li></li>
    <li></li>
    <li></li>
  </ul>
</div>

对应的 Fiber 数链表结构如下图：

3. 附加

因为接下来的单向与双向循环列表需要频繁的操作尾节点，因此在前面代码的基础上添加一个 tail 指针，总是指向链表的最后一个节点。

typescript

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
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

三、双向链表

1. 是什么

双向链表：Doubly Linked List

包含两个方向：

一个是指向下一个节点的 next 指针
另一个是指向上一个节点的 pre 指针

双向链表特点：

每个节点包含 3 个部分
- value：或者叫做 data，具体的数据
- next：下一个节点的指针
- pre：上一个节点的指针
可以双向遍历
插入和删除操作更加的灵活
- 获取前一个节点的时候，不需要像单向链表一样不断的缓存前一个节点
- 直接通过 pre 属性就可以拿到上一个节点。
- 举例：假设要移除 current 这个节点
  javascript
```
current.prev.next = current.next;
current.next.prev = current.prev;
```
  1
  2
相比单向链表，需要更多的内存空间。因为每个节点多了一个 pre 的指针引用。
书写双链表的方法的时候，需要小心谨慎，因为需要同时维护两个指针。

2. 代码实现

1）Node 类型编写

typescript

// 普通链表中的 Node 节点类型
export class Node<T> {
  value: T // 当前节点存储的数据
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

// 双向链表中的 Node 节点类型
export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null = null // 上一个节点的指针
  next: DoublyNode<T> | null = null // 下一个节点的指针
}

2）基本结构搭建

typescript

class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | null = null // 双向链表的头节点
  protected tail: DoublyNode<T> | null = null // 双向链表的尾节点

  // 打印链表
  print() {
    let current = this.head; // current --> 头节点
    let result = []; // 存储节点内容
    while (current) {
      result.push(current.data);
      current = current.next; // 更新节点
    }
    // 退出上面的while，说明节点已经遍历完毕
    console.log(result.join(" <-> "));
  }
}

export {
  DoublyLinkedList,
};

typescript

// 测试文件
const { DoublyLinkedList, Node } = require("./DoublyLinkedList");

// 先创建3个节点
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);

// 接下来，将这3个节点串联成一个双向链表
node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;

// 创建一个 DoublyLinkedList 并将 node1 作为头节点
const dl = new DoublyLinkedList();
dl.head = node1;
dl.tail = node3;
dl.size = 3;

// 打印双向链表
dl.print();

3）新增节点

在链表尾部新增一个节点

typescript

// 接收一个参数
// 该参数为新的节点的数据
append(value: T): void {
  // 生成新的节点
  const newNode = new DoublyNode(value);

  if(!this.head){
    // 进入此分支，说明 this.head 为 null
    // this.head 为 null 说明是一个空链表
    // 当前就一个节点，头部也是它，尾部也是它
    // prev 属性为 null
    this.head = newNode;
    this.tail = newNode;
  } else {
    // 说明当前的双向链表是有节点
    this.tail!.next = newNode;
    // 不能将一个父类的对象, 赋值给一个子类的类型
    // 可以将一个子类的对象, 赋值给一个父类的类型(多态)
    newNode.prev = this.tail;
    this.tail = newNode;
  }

  // 无论上面进入哪个分支，都是添加
  // 长度会增长
  this.length++;
}

在链表首部新增一个节点

typescript

prepend(value: T): void {
  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++
}

在链表指定位置添加节点

typescript

// 接收两个参数
// 1. 要插入的下标
// 2. 新节点的数据
insert(value: T, position: number): boolean {
  if(position < 0 || position > this.length){
    throw new Error("索引值无效");
  }

  // 没有进入上面的if，说明索引没有问题，接下来开始根据索引进行插入操作
  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>;
    // 更新各个节点的指向
    newNode.prev = current.prev;
    newNode.next = current;
    current.prev!.next = newNode;
    current.prev = newNode;

    this.length++;
  }
  return true;
}

4）删除节点

删除指定数据节点

typescript

// 接收一个参数
// 要删除的数据节点对应的数据
remove(item){
  let current = this.head; // 一开始指向头节点
  while(current){
    // 这里面就需要去寻找对应数据的那个节点
    if(current.data === item){
      // 进入此分支，说明找到了要删除的节点
      if(current === this.head && current === this.tail){
        // 进入此分支，说明整个双向链表只有一个节点
        // 将头尾节点都置为空
        this.head = null;
        this.tail = null;
      } else if(current === this.head){
        // 说明当前要删除的节点是头节点
        this.head = this.head.next;
        this.head.prev = null;
      } else if(current === this.tail){
        // 说明要删除的节点为尾节点
        this.tail = this.tail.prev
        this.tail.next = null;
      } else {
        // 说明就是中间节点
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
      // 无论上面进入哪一个分支，都会删除一个节点
      this.size--;
      return true;
    }
    current = current.next;
  }
  return false;
}

删除指定索引节点

typescript

// 接收一个参数
// 要删除的节点所对应的索引值
removeAt(position: number): T | null {
  if(position < 0 || position >= this.length){
    throw new Error("索引值有误")
  }

  let current = this.head // 先记录头节点
  if(position === 0){
    // 进入此分支，说明删除的是头节点
    if(this.head === this.tail){
      // 说明当前的双链表只有一个节点
      this.head = null
      this.tail = null
    } else {
      this.head = this.head.next
      this.head!.prev = null
    }
  } else if (position === this.length - 1) { // 删除的是最后一个
    current = this.tail
    this.tail = this.tail!.prev
    this.tail!.next = null
  } else { // 删除的是中间的节点
    current = this.getNode(position) as DoublyNode<T>
    current.next!.prev = current.prev
    current.prev!.next = current.next
  }

  this.length--

  return current?.value ?? null
}

5）其他方法

反转链表

reverse(){
  if(!this.head) return; // 如果是空链表，直接返回
  
  let current = this.head; // 缓存头节点
  let prev = null; // 用于缓存上一个节点
  let next = null; // 用于缓存下一个节点
  
  while(current){
    next = current.next;
    current.next = prev;
    current.prev = next;
    prev = current;
    current = next;
  }
  
  // 更新头节点和尾节点
  this.tail = this.head; // 原来的头变成了尾巴
  this.head = prev; // 然后更新头节点
}

置换链表

接收两个下标值，将对应下标值的节点的内容进行交换

// 接收2个参数
// 是两个下标值
swap(index1, index2){
  if(index1 === index2) return false; // 如果索引相等，不需要交换
  if(index1 < 0 || index1 >= this.size || index2 < 0 || index2 >= this.size){
    throw new Error("索引值有错误");
  }
  
  let current = this.head; // 记录头节点
  let counter = 0; //计数器，用于记录索引的，类似于数组的下标
  let node1 = null;
  let node2 = null;
  
  while(current){
    if(counter === index1) node1 = current;
    if(counter === index2) node2 = current;
    if(node1 && node2) break; // 两个节点都找到了，跳出循环
    current = current.next;
    counter++;
  }
  
  // 找到了两个节点，接下来进行交换操作
  if(node1 && node2){
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }
  
  return false;
}

查看长度与是否为空

length(){
  return this.size;
}
isEmpty(){
  return this.size === 0;
}

遍历链表

允许用户传递一个回调函数，然后对该双向链表所有的节点都应用该回调函数。

类似于数组的 foreach 方法：

const arr = [1, 2, 3];
arr.forEach((item, index) => {
  console.log(item, index);
});
// 接收一个参数
// 该参数是一个回调函数
forEach(fn){
  // 遍历整个链表，将所有的节点扔给这个回调函数
  let current = this.head;
  while(current){
    fn(current);
    current = current.next;
  }
}

查看节点索引

1000 --> 0
100 --> 7
// 接收一个参数
// 要查找的节点的数据是什么
find(item){
  let current = this.head;
  let counter = 0;
  while(current){
    if(current.data === item){
      // 说明找到了
      return counter;
    }
    current = current.next;
    counter++;
  }
  // 代码走到这儿，说明没有进入过 while 里面的 if
  // 说明没有找到
  return -1;
}

四、单向循环链表

循环链表：

单向循环链表
双向循环链表

单向循环链表是由单链表进化而来的，算是单链表的“儿子”或者称之为分支，所以单链表的那一套结构对于单向循环链表来说完全适用，结构并无较大改变。二者所不同的地方只是在尾结点，所以我们只需要在尾结点和与尾结点相关的操作上下功夫就行了。

需要重构的方法

add方法

// 新增一个指定数据的节点
// 放到当前链表的最后
add(data) {
  // 首先需要生成一个节点
  const newNode = new Node(data);
  // 需要判断新增的这个节点是不是头节点
  if (!this.head) {
    // 如果进入此分支，说明当前的单向链表是空的
    // 当前这个节点应该是头节点
    this.head = newNode;
    // 这里还需要一个操作，新增的这个节点会变成尾节点，这个尾节点需要指向头部
    newNode.next = this.head;
  } else {
    // 说明当前的单向链表不是空的
    // 将节点添加到最后
    let current = this.head;
    while (current.next !== this.head) {
      current = current.next;
    }
    // 退出上面 while 循环的时候，current 是最后一个节点
    current.next = newNode;
    newNode.next = this.head;
  }
  this.size++;
}

print方法

// 打印链表数据
print() {
  // 无外乎就是遍历所有的节点，通过 next 就可以找到下一个节点
  let current = this.head; // 一开始从头节点开始
 	let result = ""; // 存储整个链表拼接出来的结果
  if(this.head){
    do{
      result += `${current.data} -> `;
      current = current.next;
    }while(current !== this.head)
  }
  result += "null";
  console.log(result);
}

addAt方法

addAt(data, index){
    // 安全性处理
    if (index < 0 || index > this.size) {
      throw new Error("索引值无效");
    }
  
  	const newNode = new Node(data);
  	
  	if(!this.head){
      // 说明是空链表
      newNode.next = newNode; // 形成循环
      this.head = newNode;
    } else if(index === 0){
      // 在头部插入，而且链表不为空
      // 需要找到最后一个节点，并且让最后一个节点指向当前的新节点（因为新节点成为了新的头部）
      let last = this.head;
      // 找到最后一个节点
      while(last.next !== this.head){
        last = last.next;
      }
      newNode.next = this.head;
      this.head = newNode;
      last.next = this.head;
    } else {
      // 在链表的中间或者尾部插入
      let current = this.head;
      let counter = 0; // 计数器
      while(counter < index - 1){
        current = current.next;
        counter++;
      }
      // 出了while循环之后，说明找到了插入的位置
      newNode.next = current.next;
      current.next = newNode;
    }
  	this.size++;
}

remove方法

remove(data){
  // 链表为空就返回 null
  if(!this.head) return null;
  
  let current = this.head;
  let previous = null;
  
  do{
    if(current.data === data){
      // 说明找到了要删除的节点
      // 在删除的时候分为两种情况，看删除的节点是不是头节点
      if(previous === null){
        // 说明当前要删除的节点是头节点
        // 这里又要分成两种情况
        // 1. 只有一个头节点
        // 2. 超过一个节点
        if(current.next === this.head){
          // 说明只有一个节点
          this.head = null;
        } else {
          // 说明不止一个节点
          // 找到最后一个节点，让它指向当前要删除的节点的下一个节点
          let last = this.head;
          while(last.next !== this.head){
            last = last.next;
          }
          this.head = current.next;
          last.next = this.head;
        }
      } else {
        // 说明当前要删除的节点不是头节点
        previous.next = current.next;
      }
      this.size--;
      return current.data;
    } 
    // 继续往下找
    previous = current;
    current = current.next;
  } while(current !== this.head);
}

removeAt方法

removeAt(index){
     if (index < 0 || index >= this.size) {
        throw new Error("索引值无效");
     }
  
  	if(!this.head) return null;
  
  	let current = this.head; // 从头节点出发，寻找要删除的节点
  	let previous = null; // 暂存上一个节点
  
  	if(index === 0){
      // 说明要删除的是头节点
      // 需要判断是否只有一个节点
      if(current.next === this.head){
        this.head = null;
      } else {
        let last = this.head;
        // 寻找最后一个节点
        while(last.next !== this.head){
          last = last.next;
        }
        this.head = current.next; // 之前头节点的下一个成为新的头
        last.next = this.head;
      }
    } else {
      // 删除的不是头节点
      
      // 这个 for 是在遍历到指定的删除位置
      for(let i = 0; i < index; i++){
        previous = current;
        current = current.next;
      }
      
      previous.next = null;
      previous.next = current.next;
      current.next = null;
    }
  
  	this.size--;
  	return current.data;
}

reverse方法

reverse(){
  // 如果链表为空，或者链表只有一个节点，反转并无意义
  if(!this.head || this.head.next === this.head) return;
  
  let current = this.head;
  let previous = null; // 记录前一个节点
  let next = null; // 记录后一个节点
  
  do{
    // 进行反转操作
    next = current.next; // 将当前节点原本的下一个节点暂存
    current.next = previous;
    previous = current;
    current = next;
  }while(current !== this.head);
  
  // this.head是最后一个节点，previous是头节点
  // 因为是循环链表，需要让最后一个节点指向头节点
  this.head.next = previous;
  this.head = previous; // 重置头节点的值
}

swap方法

// 接收参数
// 要交换的两个节点的下标，下标是从 0 开始
swap(index1, index2) {
  if (index1 === index2) return false; // 如果索引相等，不需要交换
  if (
    index1 < 0 ||
    index1 >= this.size ||
    index2 < 0 ||
    index2 >= this.size
  ) {
    throw new Error("索引无效");
  }

  // 代码走到这一步，说明索引是没有问题的
  // 开始进行交换
  let current = this.head; // 一开始指向头节点
  let counter = 0; // 计数器，靠它找到对应下标的节点
  let node1 = null; // 存储index1对应的节点
  let node2 = null; // 存储 index2 对应的节点

  // 这个while循环主要是寻找节点
  do {
    if (counter === index1) node1 = current;
    if (counter === index2) node2 = current;
    if (node1 && node2) break; // 两个节点都找到了，就退出
    current = current.next;
    counter++;
  } while (current !== this.head);

  if (node1 && node2) {
    // 交换两个节点的数据
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }

  return false;
}

五、双向循环链表

对比普通的双向链表，双向循环链表的尾节点的 next 指向头节点，头节点的 prev 指向尾节点。

add方法

add(item) {
  // 生成新的节点
  const newNode = new Node(item);

  // 判断是否为空链表
  if (!this.head) {
   	// 原本是空链表
    newNode.next = newNode;
    newNode.prev = newNode;
    this.head = newNode;
    this.tail = newNode;
  } else {
    // 说明当前的双向链表是有节点
    newNode.prev = this.tail;
    this.tail.next = newNode;
    
    newNode.next = this.head; // newNode作为最后一个节点，要指向回头节点
    this.head.prev = newNode;
    
    this.tail = newNode;
  }

  // 无论上面进入哪个分支，都是添加
  // 长度会增长
  this.size++;
}

print方法

print(){
  if(!this.head) return; // 如果链表为空，直接返回
  
  let current = this.head; // current --> 头节点
  let result = []; // 存储节点的内容
  
  do{
    result.push(current.data);
    current = current.next;
  }while(current !== this.head);
  
  console.log(result.join("<->"));
}

addAt方法

// 接收两个参数
// 1. 要插入的下标
// 2. 新节点的数据
addAt(index, item) {
  if (index < 0 || index > this.size) {
    throw new Error("索引值无效");
  }

  // 创建新的节点
  const newNode = new Node(item);

  // 没有进入上面的if，说明索引没有问题，接下来开始根据索引进行插入操作
  if (index === 0) {
    if(!this.head){
      // 链表为空，直接插入
      newNode.next = newNode;
      newNode.prev = newNode;
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 说明链表不为空，插入到头部，之前的头部节点就会成为新节点的 next
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head.prev = newNode;
      this.tail.next = newNode;
      this.head = newNode;
    }
  } else if (index === this.size) {
    // 进入此分支，说明是要插入到尾部
    this.add(item);
  } else {
    // 插入到中间
    // 这里会涉及到需要找到具体的位置
    let current = this.head;
    let counter = 0; // 计数器，用于标注节点的个数，起到一个类似于数组下标的作用
    while (current) {
      if (counter === index) {
        // 更新各个节点的指向
        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;
        break;
      }
      // 不停的更新节点
      current = current.next;
      counter++;
    }
  }
  this.size++;
}

remove方法

// 接收一个参数
// 要删除的数据节点对应的数据
remove(item) {
  let current = this.head; // 一开始指向头节点
  
  if(!this.head) return false; // 如果链表为空，直接返回
  
  do{
    // 这里面就需要去寻找对应数据的那个节点
    if (current.data === item) {
      // 进入此分支，说明找到了要删除的节点
      if (current === this.head && current === this.tail) {
        // 进入此分支，说明整个双向链表只有一个节点
        // 将头尾节点都置为空
        this.head = null;
        this.tail = null;
      } else if (current === this.head) {
        // 说明当前要删除的节点是头节点
        this.head = this.head.next;
        this.head.prev = this.tail;
        this.tail.next = this.head;
      } else if (current === this.tail) {
        // 说明要删除的节点为尾节点
        this.tail = this.tail.prev;
        this.tail.next = this.head;
        this.head.prev = this.tail;
      } else {
        // 说明就是中间节点
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
      // 无论上面进入哪一个分支，都会删除一个节点
      this.size--;
      return true;
    }
    current = current.next; // 更新节点
  } while(current !== this.head);
  
  return false;
}

removeAt方法

// 接收一个参数
// 要删除的节点所对应的索引值
removeAt(index) {
  if (index < 0 || index >= this.size) {
    throw new Error("索引值有误");
  }

  let current = this.head; // 先记录头节点
  let counter = 0; // 计数器，对下标进行计数
  
  if (index === 0) {
    // 进入此分支，说明删除的是头节点
    if (this.head === this.tail) {
      // 说明当前的双链表只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = this.tail;
      this.tail.next = this.head;
    }
  } else {
    // 说明删除的是后面的节点
    do{
      if (counter === index) {
        // 找到要删除的节点的时候，会进入该分支
        if (current === this.tail) {
          // 说明要删除的节点是尾节点
          this.tail = current.prev; // 更新尾节点
          this.tail.next = this.head;
          this.head.prev = this.tail;
        } else {
          // 说明就是中间的节点
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
        break;
      }
      // 不断的更新节点
      current = current.next;
      counter++;
    } while(current !== this.head);
  }
  this.size--;
}

reverse方法

reverse() {
  if (!this.head) return; // 如果是空链表，直接返回

  let current = this.head; // 缓存头节点
  let prev = null; // 用于缓存上一个节点
  let next = null; // 用于缓存下一个节点

  do{
    next = current.next;
    current.next = prev;
    current.prev = next;
    prev = current;
    current = next;
  }while(current !== this.head);

  // 更新头节点和尾节点
  this.tail = this.head; // 原来的头变成了尾巴
  this.head = prev; // 然后更新头节点
  this.tail.next = this.head; // 更新尾节点的next指向新的头节点，保持循环结构
  this.head.prev = this.tail; // 更新头节点的prev指向新的尾节点，保持循环结构
}

swap方法

// 接收2个参数
// 是两个下标值
swap(index1, index2) {
  if (index1 === index2) return false; // 如果索引相等，不需要交换
  if (
    index1 < 0 ||
    index1 >= this.size ||
    index2 < 0 ||
    index2 >= this.size
  ) {
    throw new Error("索引值有错误");
  }

  let current = this.head; // 记录头节点
  let counter = 0; //计数器，用于记录索引的，类似于数组的下标
  let node1 = null;
  let node2 = null;

  do{
    if (counter === index1) node1 = current;
    if (counter === index2) node2 = current;
    if (node1 && node2) break; // 两个节点都找到了，跳出循环
    current = current.next;
    counter++;
  }while(current !== this.head);
  
  // 找到了两个节点，接下来进行交换操作
  if (node1 && node2) {
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }

  return false;
}

forEach方法

// 接收一个参数
// 该参数是一个回调函数
forEach(fn) {
  // 遍历整个链表，将所有的节点扔给这个回调函数
  let current = this.head;
  do{
    fn(current);
    current = current.next;
   }while(current !== this.head);
}

find方法

// 接收一个参数
// 要查找的节点的数据是什么
find(item) {
  let current = this.head;
  let counter = 0;
  
  do{
    if (current.data === item) {
      // 说明找到了
      return counter;
    }
    current = current.next;
    counter++;
   }while(current !== this.head);
  
  // 代码走到这儿，说明没有进入过 while 里面的 if
  // 说明没有找到
  return -1;
}

最后总结一下：

无论是单向循环链表，还是双向循环链表，在重构方法的时候，主要就是 2 个地方：

循环：因为循环链表不会有 null 的情况，因此跳出循环的条件不能为判断当前节点是否null
头尾节点的处理：要始终保证尾节点的next指向头节点，头节点的prev指向尾节点

线性数据结构 ​

第一章：栈 ​

一、是什么 ​

二、代码实现 ​

1. 数组版 ​

1）类型定义 ​

2）实现栈 ​

2. 代码实现 - 链表 ​

三、思维训练 ​

1. 十进制转二进制 ​

2. 有效的括号 ​

第二章：队列 ​

一、普通队列 ​

1. 是什么 ​

2. 代码实现 ​

1）数组版 ​

[1] 类型定义 ​

[2] 编写 ArrayQueue ​

2）链表版 ​

3. 思维训练 ​

1）击鼓传花游戏 ​

2）回文检查器 ​

二、循环队列 ​

1. 是什么 ​

2. 实现思路 ​

1）普通队列 ​

2）循环队列 ​

3）代码实现 ​

三、双端队列 ​

第三章：链表 ​

一、是什么 ​

二、单向链表 ​

1. 是什么 ​

2. 代码实现 ​

1）基础框架搭建 ​

2）链表的新增 ​

3）链表的删除 ​

4）链表的反转 ​

[1] 循环 ​

5）链表的置换 ​

3. 附加 ​

三、双向链表 ​

1. 是什么 ​

2. 代码实现 ​

1）Node 类型编写 ​

2）基本结构搭建 ​

3）新增节点 ​

4）删除节点 ​

5）其他方法 ​

四、单向循环链表 ​

五、双向循环链表 ​

线性数据结构

第一章：栈

一、是什么

二、代码实现

1. 数组版

1）类型定义

2）实现栈

2. 代码实现 - 链表

三、思维训练

1. 十进制转二进制

2. 有效的括号

第二章：队列

一、普通队列

1. 是什么

2. 代码实现

1）数组版

[1] 类型定义

[2] 编写 ArrayQueue

2）链表版

3. 思维训练

1）击鼓传花游戏

2）回文检查器

二、循环队列

1. 是什么

2. 实现思路

1）普通队列

2）循环队列

3）代码实现

三、双端队列

第三章：链表

一、是什么

二、单向链表

1. 是什么

2. 代码实现

1）基础框架搭建

2）链表的新增

3）链表的删除

4）链表的反转

[1] 循环

5）链表的置换

3. 附加

三、双向链表

1. 是什么

2. 代码实现

1）Node 类型编写

2）基本结构搭建

3）新增节点

4）删除节点

5）其他方法

四、单向循环链表

五、双向循环链表