写一个单向链数据结构的 js 实现并标注复杂度

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;  // Keep track of the list size
  }

  // Add a new node to the end of the list (append)
  // Time Complexity: O(n) - because in the worst case (no tail pointer), we need to traverse the whole list.
  append(data) {
    const newNode = new Node(data);

    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }


  // Add a new node to the beginning of the list (prepend)
  // Time Complexity: O(1) - constant time operation
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // Insert a new node at a specific index
  // Time Complexity: O(n) - in the worst case (inserting at the end or if index is out of bounds), we need to traverse the whole list.
  insertAt(data, index) {
    if (index < 0 || index > this.size) {
      return "Invalid Index"; // Or throw an error, depending on your needs
    }

    if (index === 0) {
      this.prepend(data);
      return;
    }

    const newNode = new Node(data);
    let current = this.head;
    let previous = null;
    let count = 0;

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

    newNode.next = current;
    previous.next = newNode;
    this.size++;
  }

  // Remove a node at a specific index
  // Time Complexity: O(n) - in the worst case (removing the last element), we need to traverse almost the whole list.
  removeAt(index) {
    if (index < 0 || index >= this.size) {
      return "Invalid Index"; // Or throw an error
    }

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

    let current = this.head;
    let previous = null;
    let count = 0;

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

    previous.next = current.next;
    this.size--;
  }


  // Get the value at a specific index
  // Time Complexity: O(n) - in the worst case (getting the last element), we need to traverse the whole list.
  get(index) {
    if (index < 0 || index >= this.size) {
      return "Invalid Index"; // Or throw an error
    }

    let current = this.head;
    let count = 0;
    while (count < index) {
      current = current.next;
      count++;
    }
    return current.data;
  }


  // Print the linked list
  // Time Complexity: O(n) - we need to traverse the whole list to print each element.
  printList() {
    let current = this.head;
    let str = "";
    while (current) {
      str += current.data + " ";
      current = current.next;
    }
    console.log(str);
  }

    // Get the size of the linked list
    // Time Complexity: O(1) - size is stored as a property
    getSize() {
        return this.size;
    }

}



// Example usage:
const ll = new LinkedList();
ll.append(10);
ll.prepend(5);
ll.append(15);
ll.insertAt(12, 2); // Insert 12 at index 2
ll.removeAt(1);    // Remove the element at index 1
ll.printList(); // Output: 5 12 15