用javascript实现双向链表

双向链表（doubly linked list）是一种链式数据结构，每个节点包含两个指针，一个指向前面的节点，一个指向后面的节点。它可以在每个节点之间进行双向遍历。以下是用javascript实现双向链表的示例代码：

// 双向链表节点类
class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

// 双向链表类
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // 在链表尾部添加节点
  append(data) {
    const newNode = new Node(data);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // 在链表任意位置插入节点
  insert(position, data) {
    if (position < 0 || position > this.length) {
      return false;
    }
    const newNode = new Node(data);
    if (position === 0) {
      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
    } else if (position === this.length) {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      let current = this.head;
      let index = 0;
      while (index < position) {
        current = current.next;
        index++;
      }
      newNode.prev = current.prev;
      newNode.next = current;
      current.prev.next = newNode;
      current.prev = newNode;
    }
    this.length++;
    return true;
  }

  // 删除链表任意位置的节点
  removeAt(position) {
    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 {
        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 {
      let index = 0;
      while (index < position) {
        current = current.next;
        index++;
      }
      current.prev.next = current.next;
      current.next.prev = current.prev;
    }
    this.length--;
    return current.data;
  }

  // 查找链表中的节点
  indexOf(data) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  // 删除链表中的节点
  remove(data) {
    const index = this.indexOf(data);
    return this.removeAt(index);
  }

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

  // 获取链表长度
  size() {
    return this.length;
  }

  // 打印链表元素
  toString() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.data + ' ';
      current = current.next;
    }
    return result.trim();
  }
}

以上代码实现了双向链表的常用操作，包括在链表尾部添加节点、在链表任意位置插入节点、删除链表任意位置的节点、查找链表中的节点、删除链表中的节点、判断链表是否为空、获取链表长度和打印链表元素等。可以通过以下示例代码来测试双向链表的功能：

const dll = new DoublyLinkedList();
dll.append(1);
dll.append(2);
dll.append(3);
console.log(dll.toString()); // 1 2 3
dll.insert(1, 4);
console.log(dll.toString()); // 1 4 2 3
dll.removeAt(2);
console.log(dll.toString()); // 1 4 3
dll.remove(4);
console.log(dll.toString()); // 1 3
console.log(dll.isEmpty()); // false
console.log(dll.size()); // 2