链表

前言

要存储多个元素，数组（或列表）可能是最常用的数据结构。每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的 [] 语法来访问其元素。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（JavaScript 有来自 Array 类的方法可以帮我们做这些事，但背后的情况同样如此。）

一、链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构。

image.png
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}
function defaultEquals(a, b) {
  return a === b;
}

class LinkedList {
  constructor() {
    this.count = 0;
    this.head = undefined;
    this.equalsFn = defaultEquals
  }
  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next != null) {
        current = current.next
      }
      current.next = node;
    }
    this.count++
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next
      }
      this.count--
      return current.next
    }
    return undefined
  }
  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node !== null; i++) {
        node = node.next;
      }
      return node
    }
    return undefined
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        const current = previous.next
        previous.next = node;
        node.next = current
      }
      this.count++
      return true
    }
    return false
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count && current !== 0; i++) {
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next
    }
    return -1
  }
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index)
  }
  size() {
    return this.count
  }
  isEmpty() {
    return this.size() === 0;
  }
  getHead() {
    return this.head;
  }
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current !== null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString
  }
}