使用 JS 实现单链表

实现单链表中的节点应该具有两个属性：ele 和 next。ele 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。文本主要实现一个单链表。

要在链表类中实现这些功能

push(ele): 向链表尾部添加一个新元素
insert(ele, index): 向链表的特定位置插入一个新元素
removeAt(index): 根据特定位置，从链表中移除元素
remove(ele): 根据元素值，从链表中移除元素
getNodeAt(index): 通用方法，返回链表中特定位置的元素
getIndexOf(ele): 返回元素在链表中的索引
isEmpty(): 判断链表是否为空
getHead(): 获取链表第一个元素
toString(): 返回表示整个链表的字符串
getSize(): 返回链表包含的元素个数

实现

1. 首先定义两个公共方法

/**
 * 创建节点
 * 表示我们想要添加到链表中的项
 */
class CreateNode {
  constructor(ele) {
    this.ele = ele; // 要加入链表元素的值
    // 当一个 Node 实例被创建时，它的 next 指针总是 undefined, 因为我们知道它会是链表的最后一项（push）
    this.next = undefined; // 指向链表中下一个元素的指针
  }
}
/**
 * 比较链表中的元素是否相等
 */
function defaultEquals(a, b) {
  return a === b;
}

2. 下面就是链表的核心实现啦

**
 * 创建链表
 * 1. head 头指针
 * 2. 最后一个节点的next始终指向 undefined 或 null
 * 3. 始终只有第一个元素的引用，没有index，需要循环访问列表
 */
class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0; // 链表中元素数量，链表的长度
    this.head = undefined; // 第一个元素的引用
    this.equalsFn = equalsFn;
  }
  /**
   * 向链表尾部添加一个新元素
   */
  push(ele) {
    const node = new CreateNode(ele); // CreateNode {ele:123,next:undefined}
    // 定义一个当前指针
    let current;
    if (this.head === undefined || this.head === null) {
      // 链表为空，添加的是第一个元素
      this.head = node;
    } else {
      // 链表不为空，向其追加元素
      // 因为我们始终只有第一个元素的引用，因此需要循环访问列表，直到找到最后一项
      current = this.head;
      while (current.next !== undefined && current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
  }
  /**
   * 根据特定位置，从链表中移除元素
   * @param {*} index
   * @returns 返回移除的元素，未找到返回undefined
   */
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head;
      // 移除第一项
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getNodeAt(index - 1);
        current = previous.next;
        // 将previous与current的下一项链接起来，跳过current，从而移除它
        // 当前节点就会被丢弃在计算机内存中，等着被垃圾回收器清除
        previous.next = current.next;
      }
      this.count--;
      return current.ele;
    }
    return undefined;
  }

  /**
   * 返回链表中特定位置的元素(通用)
   * @param {*} index
   * @returns 节点元素
   */
  getNodeAt(index) {
    // 检查越界值
    if (index >= 0 && index <= this.count) {
      // 定义一个当前指针
      let current = this.head;
      // 遍历节点，直到目标位置
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
      return current;
    }
    return undefined;
  }
  /**
   * 向链表的特定位置插入一个新元素
   * @param {*} ele
   * @param {*} index
   * @returns true或false
   */
  insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      let newNode = new CreateNode(ele);
      if (index === 0) {
        // 注意需要中间变量current
        const current = this.head;
        newNode.next = current;
        this.head = newNode;
        // 注意直接这么写是错的
        // newNode.next = this.head
        // this.head = newNode;
      } else {
        // 也需要中间变量current
        const previous = this.getNodeAt(index - 1);
        const current = previous.next;
        previous.next = newNode;
        newNode.next = current;
      }
      this.count++;
      return true;
    }
    return false;
  }
  /**
   * 返回元素在链表中的索引
   * @param {*} ele
   * @returns 返回元素的位置，否则返回-1
   */
  getIndexOf(ele) {
    let current = this.head;
    if (current !== undefined && current !== null) {
      for (let i = 0; i < this.count; i++) {
        // 此处ele可能不是简单数据类型。如果元素是一个复杂对象的话，允许开发者向 LinkedClass 中传入自定义的函数来判断元素是否相等
        if (this.equalsFn(ele, current.ele)) {
          return i;
        } else {
          current = current.next;
        }
      }
      return -1;
    } else {
      return -1;
    }
  }

  /**
   * 根据元素值，从链表中移除元素
   * @param {*} ele
   * @returns 返回移除的元素，未找到返回undefined
   */
  remove(ele) {
    const index = this.getIndexOf(ele);
    return this.removeAt(index);
  }
  /**
   * 判断链表是否为空
   * @returns true/false
   */
  isEmpty() {
    return this.getSize() === 0;
  }
  /**
   * 返回链表包含的元素个数，与数组的 length 属性类似
   * @returns number
   */
  getSize() {
    return this.count;
  }
  /**
   * 获取链表第一个元素
   * 因为head 变量是 LinkedList 类的私有变量
   * @returns
   */
  getHead() {
    return this.head;
  }
  /**
   * 返回表示整个链表的字符串
   * 由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
   * @returns str
   */
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.head.ele}`;
    let current = this.head.next;
    for (let i = 1; i < this.getSize() && current != null; i++) {
      objString = `${objString},${current.ele}`;
      current = current.next;
    }
    return objString;
  }
}

// 创建一个链表实例，并添加一些数据
let link = new LinkedList();
link.push(100);
link.push(200);
link.push(300);
link.push(400);
// 打印看一下效果，如下面。
console.log(link); // 可以看出是一个嵌套的树状结构，链表的最后一个节点指向undefined/null

// 继续操作，可以正确获取想要的效果。
link.removeAt(1); // 200
link.insert(200, 1); // true
link.getIndexOf(200); // 1
link.toString(); // "100,200,300,400"

说明

使用变量引用我们需要控制的节点非常重要，这样就不会丢失节点之间的链接。如果我们可以只使用一个变量(previous)，但那样会很难控制节点之间的链接。因此，最好声明一个额外的变量来帮助我们处理这些引用。如例子中的中间变量 current!
通过指针的改变，未使用的变量会被自动回收。理解 JavaScript 垃圾回收器如何工作。