链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

单链表的概念：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个单链表的结构图：

单链表的特点：

每个元素除了由元素本身的节点还有指向下一个元素的指针构成

从链表中添加或者删除元素不需要移动其他的元素

访问链表中间的一个元素，需要从表头开始迭代列表直到找到所需的元素

生活中单链表的案例：

生活中的单链表很典型也很常见。例如寻宝游戏，你有一条线索，这条线索是指向寻找下一条线索的地点的指针，你可以顺着这条链接去下一个地方，得到另一条指向下一处的线索，如果想得到列表中间的线索的唯一办法就是从起点(第一条线索)顺着列表寻找。另一个案例就是火车，还有其他的案例这里就不一一列举了。

单向链表的实现

• 初始化链表/节点
• 头部插入节点
• 搜索/遍历节点
• 删除节点

初始化链表中的节点

class LinkedListNode {
    constructor(value, next = null) {
        this.value = value;
        this.next = next; // 初始化为null
    }
}

初始化单向链表

class LinkedList {
    constructor() {
        // 初始空指针
        this.head = null;
    }
}

头部追加节点(append)

append(value) {
    // 新建节点
    const newNode = new LinkedListNode(value, this.head);
    // 将值赋予head 为了下次新建
    this.head = newNode;
 }

删除节点

delete(value) {
    // 如果不存在节点 return null
    if (!this.head) {
      return null;
    }
    // 如果删除的是第一个节点
    let deletedNode = null;

    // 如果删除的第一个元素
    while (this.head && this.head.value === value) {
      deletedNode = this.head;
      this.head = this.head.next;
    }
    // 非第一个节点,遍历查找
    let currentNode = this.head;
    if (currentNode !== null) {
      while (currentNode.next) {
        if (currentNode.next.value === value) {
          deletedNode = currentNode.next;
          currentNode.next = currentNode.next.next;
        } else {
          currentNode = currentNode.next;
        }
      }
    }
    return deletedNode;
  }

链接: https://fly63.com/article/detial/10552