单向链表（Linked List）

1. 单向链表结构

单向链表是链表的一种，其特点是链表的连接方向是单向的，对链表的访问要通过头部开始，依序往下读取。

链表中的数据是以节点来表示的，一个单向链表由多个节点组成，一个节点被分成两部分：

• 第一个部分是保存关于节点的信息，称作数据域（data）
• 第二个部分是存储下一个节点的地址，称作指针域（next）

单向链表结构示意图

head 为头结点，不存放任何数据，它的作用是充当一个指向链表中真正存放数据的第一个节点

其中 DATA 为数据域，该内存存放的是数据；

NEXT 是地址域，数据类型为指针，该内存存放的是下一段内存的内存地址

最后的一个节点的指针域会指向 null

2. 链表常见操作

• append(element)：向链表尾部添加一个新的项

• insert(element, position)：向链表的特定位置插入一个新的项。

• remove(element)：从链表中移除一项。

• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。

• removeAt(position)：从链表的特定位置移除一项。

• isEmpty：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。

• size：返回链表包含的元素个数。与数组的 length 属性类似。

链表插入节点图示

3. 封装单向链表

封装示例

import { isEqual } from "./util.js";
class Linked {
  constructor(ele) {
    this.data = ele;
    this.next = null;
  }
}

class LinkedList {
  constructor(eles) {
    this.head = new Linked("HEAD");
    this.length = 0;
    if (Array.isArray(eles)) {
      eles.forEach((ele) => this.append(ele));
    }
  }

  /**
   * 返回链表包含的元素个数。与数组的length属性类似
   */
  get size() {
    return this.length;
  }

  /**
   * 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false
   */
  get isEmpty() {
    return !!!this.size;
  }

  /**
   * 向链表尾部添加一个新的项
   * @param ele {any}
   * @returns {Boolean}
   */
  append(ele) {
    const data = new Linked(ele);
    let currentEle = this.head;
    while (currentEle.next !== null) {
      currentEle = currentEle.next;
    }
    currentEle.next = data;
    this.length++;
    return true;
  }

  /**
   *
   * @param ele {any} 带插入元素
   * @param position {number} 插入位置(索引)
   * @returns {Boolean}
   */
  insert(ele, position = this.length) {
    if (position > this.size || !Number.isInteger(position)) {
      throw new Error(`位置${position}非法`);
    }
    // 若刚好插入到最后一个后面
    if (this.size === 0 || this.size === position) return this.append(ele);
    const data = new Linked(ele);
    let currentNode = this.head;
    let preNode = this.head;
    for (let index = 0; index < this.length; index++) {
      preNode = currentNode;
      currentNode = currentNode.next;
      if (index === position) break;
    }
    data.next = currentNode;
    preNode.next = data;
    this.length++;
    return true;
  }

  /**
   * 从链表中移除一项
   * @param ele {any} 要移除的元素
   * @returns {Boolean}
   */
  remove(ele) {
    if (this.isEmpty) return false;
    let currentEle = this.head;
    let preNode = this.head;
    let hasNode = false;
    for (let index = 0; index < this.length; index++) {
      preNode = currentEle;
      currentEle = currentEle.next;
      if (isEqual(ele, currentEle.data)) {
        hasNode = true;
        break;
      }
    }
    if (hasNode) {
      preNode.next = currentEle.next;
      this.length--;
    }
    return hasNode;
  }

  /**
   * 返回元素在链表中的索引。如果链表中没有该元素则返回-1
   * @param ele {any} 元素
   * @returns {Number}
   */
  indexOf(ele) {
    if (this.isEmpty) return -1;
    let currentEle = this.head;
    let preNode = this.head;
    let hasNode = false;
    for (let index = 0; index < this.length; index++) {
      preNode = currentEle;
      currentEle = currentEle.next;
      if (isEqual(ele, currentEle.data)) {
        hasNode = true;
        return index;
      }
    }
    if (!hasNode) return -1;
  }

  /**
   *从链表的特定位置移除一项
   * @param position {Number} 位置索引
   * @returns {Boolean}
   */
  removeAt(position) {
    if (typeof position !== "number") {
      throw new Error(`${position} should be a number`);
    }
    if (position < 0 || position > this.size || this.size <= 0) {
      return false;
    }
    let curNode = this.head;
    let preNode = this.head;
    let hasNode = false;
    for (let index = 0; index < this.length; index++) {
      preNode = curNode;
      curNode = curNode.next;
      if (index === position) {
        preNode.next = curNode.next;
        hasNode = true;
        this.length--;
        break;
      }
    }
    return hasNode;
  }
}

工具函数

// ./util.js

// 是否为对象类型
export function isObject(obj) {
  return typeof obj === "object" && obj !== null;
}
// 检测两个对象是否长的一样(地址)
export function isEqual(obj1, obj2) {
  if (!isObject(obj1) || !isObject(obj2)) return obj1 === obj2;
  if (obj1 === obj2) return true;
  let obj1Keys = Object.keys(obj1);
  let obj2Keys = Object.keys(obj2);
  if (obj1Keys.length !== obj2Keys.length) return false;
  for (let key in obj1) {
    const res = isEqual(obj1[key], obj2[key]);
    if (!res) return false;
  }
  return true;
}