链表的定义

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的，由一系列节点组成。
每个节点包含两部分：1.存储数据元素的数据域；2.存储下一个节点地址的指针域。3.最后一个节点的指针域指向null。

• data 表示节点存放的数据
• next 表示下一个节点指向的内存空间

链表节点

代码表示：

// 链表节点
function LinkedNode(node) {
    this.val = node;
    this.next = null;
}

// val表示该节点上存储的值
// next表示该节点的下一个节点
// 一般的单向链表的尾节点指向null

创建链表

一般链表的第一个节点为hed，用来表示这是一个链表存储，在创建链表的时候将链表的第一个节点默认设置为head。

// 创建链表
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    // 若链表节点为数值，则创建时为this.head = new LinkedNode(521);
}

链表长度

为了方便链表操作，可以记录链表长度，在操作链表时要对长度进行相应的加减。

// 链表长度
function LinkedList(){
    this.head = new LinkedNode('head');   // 头节点
    this.length = 0; // 链表的默认长度为0
}

遍历链表

根据next指针遍历下去，直到为null。

// 遍历链表
let current = head;
while(current){
    console.log(current.val)
    current = current.next;
}

插入节点

向链表中间插入一个元素，可以如下图所示：

插入节点的步骤：

• 存储插入位置的前一个节点
• 存储插入位置的后一个节点
• 将插入位置的前一个节点的 next 指向插入节点
• 将插入节点的 next 指向前面存储的 next 节点

  let current = head;
  while(current < position>){
      previous = current;
      current = current.next;
  }
  previous.next = node;
  node.next = current;

  如果在头节点进行插入操作的时候，会实现previousNode节点为undefined，不适合上述方式。解放方式可以是在头节点前面添加一个虚拟头节点，保证插入行为一致。

删除节点

链表任意位置删除节点，如下图操作：

删除节点的步骤：

• 获取删除节点的前一个结点
• 获取删除节点的后一个结点
• 将前一个结点的next指向后一个结点
• 将删除节点的next指向为null

  while(current != node){
      previous = current;
      current = current.next;
      nextNode = current.next;
  }
  previous.next = nextNode;

应用场景

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等。
当缓存空间被占满时，我们可能会使用LRU最近最常使用策略去清除，实现LRU算法的是数据结构是链表，思路如下：

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头部开始顺序遍历链表

• 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据的对应结点，并将其从原来的位置删除，并插入到链表头部
• 如果此数据没在缓存链表中
• • 如果此时缓存未满，可直接在链表头部插入新节点存储此数据
• • 如果此时缓存已满，则删除链表尾部节点，再在链表头部插入新节点

由于链表插入删除效率极高，达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候，都可以使用链表