双向链表

代码实现

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

class DoublyLinkedList {
  length = 0;
  // 存放头结点的引用
  head = null;
  // 存放尾结点的引用
  tail = null;

  // 双向链表的方法
  // append(data) 向尾部添加一个节点
  append(data) {
    // 1. 创建新的链表节点
    const newNode = new Node(data);

    // 追加元素
    if (this.length === 0) {
      // 如果链表为空的话
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 追加到链表尾部
      // 巧妙的一点是不用循环找链表的尾部节点，现在 tail 中有尾节点的引用
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    }
    // 长度增加
    this.length++;
  }

  // insert(position, data) 指定位置插入数据
  insert(position, data) {
    // 判断是否越界
    if (position < 0 || position > this.length) return false;

    // 创建新的链表节点
    const newNode = new Node(data);

    // 追加链表节点；共用一下几种情况：
    // 1. 空链表追加到头部
    // 2. 链表有数据追加到头部
    // 3. 追加到尾部
    // 4. 0----this.length 之间的追加
    if (position === 0) {
      // 追加到头部
      if (this.head === null) {
        // 链表无数据添加到头部
        this.head = newNode;
        this.tail = newNode;
      } else {
        // 链表有数据添加到头部
        newNode.next = this.head;
        this.head.previous = newNode;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 在链表尾部插入节点
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    } else {
      // 0 --- this.length 中间插入

      // 准备变量
      let targetIndex = 0; // 代表节点位置的索引
      let currentNode = this.head;
      let previousNode = null; // 代表上一个节点

      // 循环查找节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 插入
      previousNode.next = newNode;
      newNode.previous = previousNode;

      newNode.next = currentNode;
      currentNode.previous = newNode;
    }

    // 增加长度
    this.length++;
    return true;
  }

  // getData(position) 获取指定位置的链表节点
  getData(position = 0) {
    // 判断越界
    if (position < 0 || position >= this.length) return false;
    // 循环查找位置

    let targetIndex = 0; // 代表节点位置的索引
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    // 返回
    return currentNode.data;
  }

  // indexOf(data) 查找数据对应的index
  indexOf(data) {
    // 循环查找数据

    let targetIndex = 0;
    let currentNode = this.head;

    while (currentNode) {
      if (data === currentNode.data) {
        return targetIndex;
      }
      currentNode = currentNode.next;
      targetIndex++;
    }
    // 否则返回-1
    return -1;
  }

  // removeAt(position) 删除指定位置的节点
  removeAt(position) {
    // 判断是否越界
    if (position < 0 || position >= this.length) return false;
    let currentNode = this.head;

    // 根据不同的情况删除
    if (position === 0) {
      // 1. 删除头部的情况
      if (this.length === 1) {
        // 如果链表只有一个节点的情况
        this.head = null;
        this.tail = null;
      } else {
        // 如果链表有多个节点
        this.head = this.head.next;
        this.head.previous = null;
      }
    } else if (position === this.length) {
      // 删除链表最后的一个节点
      this.tail.previous.next = null;
      this.tail = this.tail.previous;
    } else {
      // 0-----this.length 的情况
      let targetIndex = 0;
      let previousNode = null;

      // 循环找到positions位置
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 删除
      previousNode.next = currentNode.next;
      currentNode.next.previous = previousNode;
    }
    // 长度递减
    this.length--;
    return currentNode.data;
  }

  // update(position, data) 修改指定位置的节点
  update(position, data) {
    // 判断边界
    if (position < 0 || position >= this.length) return false;

    // 循环找的位置
    let targetIndex = 0;
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    currentNode.data = data;
    return currentNode.data;
  }

  //remove(data) 删除指定 data 所在的节点（继承单向链表）

  remove(data) {
    return this.removeAt(this.indexOf(data));
  }

  // isEmpty() 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }
  // size() 获取链表的长度
  size() {
    return this.length;
  }
  // forwardToString() 链表数据从前往后以字符串形式返回
  forwardToString() {
    let currentNode = this.head;
    let result = "";

    // 遍历所有的节点，拼接为字符串，直到节点为 null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.next;
    }

    return result;
  }

  // backwardString() 链表数据从后往前以字符串形式返回
  backwardString() {
    let currentNode = this.tail;
    let result = "";

    // 遍历所有的节点，拼接为字符串，直到节点为 null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.previous;
    }

    return result;
  }
}

参考：https://juejin.cn/post/6893428188655910926#heading-3 (opens new window)