用JavaScript实现单向链表结构及其时间复杂度

以下是单向链表的 JavaScript 实现：

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

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

  // 在链表末尾添加一个节点
  append(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  // 在链表任意位置插入一个节点
  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.append(value);
    if (index === 0) {
      this.head = new Node(value, this.head);
      this.length++;
      return true;
    }

    const prevNode = this.getNodeByIndex(index - 1);
    const newNode = new Node(value);
    newNode.next = prevNode.next;
    prevNode.next = newNode;

    this.length++;
    return true;
  }

  // 删除指定位置的节点
  remove(index) {
    if (index < 0 || index >= this.length) return false;

    if (index === 0) {
      this.head = this.head.next;
      this.length--;
      return true;
    }

    const prevNode = this.getNodeByIndex(index - 1);
    prevNode.next = prevNode.next.next;

    if (index === this.length - 1) this.tail = prevNode;

    this.length--;
    return true;
  }

  // 查找指定位置的节点
  getNodeByIndex(index) {
    if (index < 0 || index >= this.length) return null;

    let currentNode = this.head;
    let currentIndex = 0;
    while (currentIndex < index) {
      currentNode = currentNode.next;
      currentIndex++;
    }

    return currentNode;
  }

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

  // 转化为数组
  toArray() {
    const arr = [];
    let currentNode = this.head;
    while (currentNode) {
      arr.push(currentNode.value);
      currentNode = currentNode.next;
    }
    return arr;
  }

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

    while (currentNode) {
      const nextNode = currentNode.next;

      if (!nextNode) {
        this.head = currentNode;
      }

      currentNode.next = prevNode;
      prevNode = currentNode;
      currentNode = nextNode;
    }

    this.tail = this.getNodeByIndex(0);
  }
}

操作的时间复杂度如下：

• 在链表末尾添加一个节点（append）：O(1)
• 在链表任意位置插入一个节点（insert）：O(n)
• 删除指定位置的节点（remove）：O(n)
• 查找指定位置的节点（getNodeByIndex）：O(n)
• 获取链表的长度（getLength）：O(1)
• 转化为数组（toArray）：O(n)
• 反转链表（reverse）：O(n)
  注意，在 insert 和 remove 操作中，因为必须从头查找到指定位置上的节点，所以时间复杂度为 O(n)。而在其他几个操作中，都不需要遍历整个链表，因此时间复杂度是 O(1)。