单链表

/**
 * 单链表
 */
class SingleLinkedList {
  constructor() {
    this._head = new LNode(); // 头结点
    this._len = 0;
  }

  /**
   * 获取链表长度
   * @returns
   */
  length() {
    return this._len;
  }

  /**
   * 插入元素
   * @param {number} i 位序
   * @param {any} data 数据
   * @returns
   */
  insert(i, data) {
    if (i < 1) {
      return false;
    }

    let p = this._head; // 当前结点指针
    let j = 0; // 当前结点位序
    // 遍历链表，找到第i-1个结点
    while (p != null && j < i - 1) {
      p = p.next;
      j++;
    }

    // i值不合法，过界
    if (p === null) {
      return false;
    }

    return this.insertNextNode(p, data);
  }

  /**
   * 在指定结点后插入元素
   * @param {*} ref
   * @param {*} data
   * @returns
   */
  insertNextElement(ref, data) {
    const newNode = new Node(data);
    return this.insertNextNode(ref, newNode);
  }

  /**
   * 在指定结点后插入元素结点
   * @param {LNode} ref 参考结点
   * @param {*} target 数据结点
   * @returns
   */
  insertNextNode(ref, target) {
    if (ref === null) {
      return false;
    }

    target.next = p.next;
    p.next = target;
    this._len++;
    return true;
  }

  /**
   * 元素的前插操作
   * @param {LNode} ref 参考结点
   * @param {*} data 数据
   * @returns
   */
  insertPriorElement(ref, data) {
    const newNode = new LNode(data);
    return this.insertPriorNode(ref, newNode);
  }

  /**
   * 结点前插操作
   * @param {LNode} ref 参考结点
   * @param {LNode} target 插入结点
   * @returns
   */
  insertPriorNode(ref, target) {
    if (ref === null) {
      return false;
    }

    // 后插操作
    this.insertNextNode(ref, target);

    // 将结点数据呼唤，实现逻辑上的前插
    const tmp = target.data;
    target.data = ref.data;
    ref.data = tmp;

    return true;
  }

  /**
   * 删除位序所指结点
   * @param {number} i 位序
   * @returns
   */
  remove(i) {
    let p = this._head;
    let j = 0;

    while (p !== null && j < i - 1) {
      p = p.next;
      j++;
    }

    // 位序溢出
    if (p === null) {
      return false;
    }
    if (p.next === null) {
      return false;
    }

    let q = p.next;
    p.next = q.next;
    // free q
    q.next = null;
    this._len--;

    return q;
  }

  removeNode(node) {
    // 如果是最后一个结点（默认node存在列表的情况下）
    if (node.next === null) {
      this.remove(this.length());
    }
  }
}

/**
 * 链表结点
 */
class LNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}