用JavaScript编写双向链表实现

以下是用 JavaScript 实现双向链表的基本代码：

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

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

  // 添加节点
  append(data) {
    const node = new Node(data);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.length++;
  }

  // 插入节点
  insert(position, data) {
    if (position < 0 || position > this.length) {
      return false;
    }

    const node = new Node(data);

    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      if (position === 0) {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
      } else if (position === this.length) {
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
      } else {
        let index = 0;
        let current = this.head;
        let previous = null;

        while (index++ < position) {
          previous = current;
          current = current.next;
        }

        previous.next = node;
        node.prev = previous;
        node.next = current;
        current.prev = node;
      }
    }

    this.length++;

    return true;
  }

  // 移除节点
  remove(data) {
    let current = this.head;

    while (current) {
      if (current.data === data) {
        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.length--;
        return true;
      }

      current = current.next;
    }

    return false;
  }

  // 获取节点索引
  indexOf(data) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.data === data) {
        return index;
      }

      current = current.next;
      index++;
    }

    return -1;
  }

  // 是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 大小
  size() {
    return this.length;
  }

  // 获取头节点
  getHead() {
    return this.head;
  }

  // 获取尾节点
  getTail() {
    return this.tail;
  }

  // 转换成字符串
  toString() {
    let current = this.head;
    let result = "";

    while (current) {
      result += current.data + " ";
      current = current.next;
    }

    return result.trim();
  }

  // 反转链表
  reverse() {
    let current = this.head;
    let temp = null;

    while (current) {
      temp = current.next;
      current.next = current.prev;
      current.prev = temp;
      current = temp;
    }

    temp = this.head;
    this.head = this.tail;
    this.tail = temp;

    return this;
  }
}

使用说明：

const dll = new DoublyLinkedList();

dll.append(1);
dll.append(2);
dll.append(3);
dll.append(4);

console.log(dll.toString()); // "1 2 3 4"

dll.insert(2, 5);

console.log(dll.toString()); // "1 2 5 3 4"

console.log(dll.getHead()); // Node { data: 1, next: Node, prev: null }

console.log(dll.getTail()); // Node { data: 4, next: null, prev: Node }

console.log(dll.indexOf(3)); // 3

dll.reverse();

console.log(dll.toString()); // "4 3 5 2 1"