Javascript 中 LinkedList 的实现

1. 什么是 LinkedList

LinkedList是一种常见的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。相比于数组，它具有更灵活的插入和删除操作，但是访问单个节点的时间复杂度较高。

在Javascript中，可以使用对象的引用来实现LinkedList。例如，下面是一个简单的LinkedList的实现：

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 = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
  // 在链表指定位置插入一个节点
  insert(position, value) {
    if (position < 0 || position > this.length) {
      return false;
    }
    const newNode = new Node(value);
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
      if (!this.tail) {
        this.tail = newNode;
      }
    } else if (position === this.length) {
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      let currentNode = this.head;
      let previousNode = null;
      let index = 0;
      while (index < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
        index++;
      }
      previousNode.next = newNode;
      newNode.next = currentNode;
    }
    this.length++;
    return true;
  }
  // 根据位置删除一个节点
  removeAt(position) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    let currentNode = this.head;
    let previousNode = null;
    let index = 0;
    if (position === 0) {
      this.head = currentNode.next;
      if (this.length === 1) {
        this.tail = null;
      }
    } else if (position === this.length - 1) {
      while (currentNode.next) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = null;
      this.tail = previousNode;
    } else {
      while (index < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
        index++;
      }
      previousNode.next = currentNode.next;
    }
    this.length--;
    return currentNode.value;
  }
  // 查找一个节点的位置
  indexOf(value) {
    let currentNode = this.head;
    let index = 0;
    while (currentNode) {
      if (currentNode.value === value) {
        return index;
      }
      currentNode = currentNode.next;
      index++;
    }
    return -1;
  }
  // 根据值删除一个节点
  remove(value) {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }
  // 将链表转换为字符串
  toString() {
    let currentNode = this.head;
    let string = '';
    while (currentNode) {
      string += currentNode.value;
      if (currentNode.next) {
        string += ' -> ';
      }
      currentNode = currentNode.next;
    }
    return string;
  }
  // 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }
  // 返回链表的长度
  size() {
    return this.length;
  }
}
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insert(1, 'a');
list.remove(2);
console.log(list.toString()); // 1 -> a -> 3

2. LinkedList 的优点

2.1 灵活的插入和删除操作

LinkedList具有非常灵活的插入和删除操作，因为只需要改变节点之间的指针即可。相比之下，数组的插入和删除操作则需要移动大量的元素，因此时间复杂度较高。

2.2 动态内存分配

LinkedList可以动态地分配内存，因为每个节点只需要在它被添加到链表中时创建，而在它被删除后则可以立刻释放内存。相比之下，数组却需要预先分配一定大小的内存空间。

3. LinkedList 的缺点

3.1 访问元素需要遍历

因为LinkedList的节点不必在内存中连续存放，因此访问单个节点的时间复杂度为O(n)。相比之下，数组可以在O(1)的时间内访问单个元素。

3.2 空间开销大

相比于数组，LinkedList需要额外的指针来指向下一个节点，因此需要更多的内存空间。

4. 使用 LinkedList 的场景

4.1 需要频繁地插入和删除元素

如果需要频繁地向一个集合中插入和删除元素，LinkedList可以极大地简化代码实现。

4.2 需要处理大型数据集合

如果需要处理的数据集合非常大，LinkedList可以动态分配内存，避免浪费过多的内存空间。

5. 小结

LinkedList是一种常见的数据结构，具有灵活的插入和删除操作以及动态内存分配的优点。不过，它的访问时间复杂度较高，同时也需要更多的内存空间。