0x000 概述

这篇文章是说链表，链表这种数据结构非常普遍，有时候我们根本就没有意识到用的是链表

0x001 啥是链表

链表就是用绳子连起来的酒瓶子，酒就是数据，每个酒瓶子都连着下一个酒瓶子。

链表一共有两个操作

• 插入：将一个新的节点插入链表
• 删除：将一个节点从链表中删除

0x001 初始化

链表不像数组、队列、栈一样需要容器，链表是通过一个数据引用另一个数据连接起来的，所以链表的初始化就是初始化第一个链表节点，这个链表作为特殊的开始节点，不作为数据。

function init() {    return {        data: 'start',        next: null    }}

0x002 插入节点

插入节点有两种情况

• 直接插到最后面：直接将最后一个节点的next指向新的节点
• 插到指定节点后面：找到这个节点，将新节点的next指向这个节点的next，并将这个节点的next指向新节点

function insert(node, newNode, data) {    while (node) {        if (data && node.data === data) {            if (node.next) {                newNode.next = node.next            }            node.next = newNode            return        }        if (!data && node.next === null) {            node.next = newNode            return        }        node = node.next    }}

0x003 删除节点

删除节点只需要断开next指向就行了

function delete_(node, data) {    let parent = node    node = node.next    while (node) {        if (node.data === data) {            if (parent) {                parent.next = node.next                return            } else {                return            }        }        parent = node        node = node.next    }    throw `not found node by data: ${data}`}

0x004 使用

let node = init() // {'data':'start','next':null}insert(node, {data: 2, next: null}) // {'data':'start','next':{'data':2,'next':null}}insert(node, {data: 3, next: null}) // {'data':'start','next':{'data':2,'next':{'data':3,'next':null}}}insert(node, {data: 4, next: null}, 2) // {'data':'start','next':{'data':2,'next':{'data':4,'next':{data: 3, next: null}}}}delete_(node, 2)  // {'data':'start','next'{'data':4,'next':{data: 3, next: null}}}

0x005 栗子：表单进度

这个栗子使用其他数据结构也可以实现，这里特意使用链表来实现就是为了演示而已

• 效果
  

• 视图

        
      
         
      
         
      
         填写下一项
        

• 源码

0x006 双向链表

在上面的视线中，使用next指向下一个节点，从方向上说，我们可以从父节点访问子节点，但是无法从子节点访问父节点，或者说，我只能从一个方向有序访问链表。在这基础上衍生出双向链表，双向链表就是在单向链表的基础上添加对上一个节点的引用

• 示意图

  

• 节点

  {    "data":"",    "prev":null,    "next":null}

• 插入

  newNdoe.prev=node.prev // 将新节点的 prev 指向当前节点的 prevnewNode.next=node // 将新节点的 next 点指向当前节点node.prev.next=newNode // 将新节点的 prev 的 next 指向新节点

• 删除

  node.prev.next=node.next // 将当前节点的 prev 的 next 指向当前节点的 nextnode.prev=null // 将当前节点的 prev 断开node.next.prev=node.prev// 将当前节点的 next 的 prev 指向当前节点的 prevnode.next=null // 将当前节点的 next 断开

0x007 环形链表

环形链表就是将收尾的节点也链接起来，如果是单项链表首尾连接，那就是单项环形链表，如果是双向链表首尾连接，那就是双向循环链表。代码没有太大的差别，就是在最后一个节点next指向第一个，第一个节点的prev指向最后一个，形成一个环装

• 图示

  

0x008 资源

• 源代码：[]