前端进阶之从零到一实现单向 & 双向链表

徐小夕
• 阅读 1609

前言

前端工程师对于算法和数据结构这块的知识的掌握程度，是进阶高级工程师的非常重要的标志之一，为了总结一下数据结构和算法方面的知识，笔者今天继续把链表这一块的知识补上，也作为自己知识体系的一个梳理，笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章，如果感兴趣或者想进阶高级的朋友们可以参考学习一下： JavaScript 中的二叉树以及二叉搜索树的实现及应用.

你将收获

  • 链表的概念和应用
  • 原生javascript实现一条单向链表
  • 原生javascript实现一条个双单向链表
  • 链表和数组的对比及优缺点

正文

1. 链表的概念和应用

链表是一种线性表数据结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

以上概念用图表示为以下结构： 前端进阶之从零到一实现单向 & 双向链表 链表是非连续的，所以说从底层存储结构上看，它不需要一整块连续的存储空间，而是通过“指针”将一组零散的数据单元串联起来成为一个整体。链表也有几种不同的类型：单向链表，双向链表，循环链表。上图就是一种单向链表。由其定义不难发现双向链表无非就是每个节点加上了前后节点的指针引用，如下图所示： 前端进阶之从零到一实现单向 & 双向链表 那什么是循环链表呢？循环链表本质上是一种特殊的单向链表，唯一的区别就在于它的尾结点指向了链表的头结点，这样首尾相连，形成了一个环，所以叫做循环链表。 如下图所示： 前端进阶之从零到一实现单向 & 双向链表 当然我们还可以扩展出双向循环链表，这里就不一一举例了。总之链表结构在计算机底层语言中应用的比较多，当我们在用高级语言做编程时可能不会察觉，比如我们用javascript敲js的时候，其实我们在深入了解链表之后我们就会发现链表有很多应用场景，比如LRU 缓存淘汰，最近消息推送等。

举个更接地气的，当我们在用PS画图时软件提供了一个动作面板，可以记录用户之前的操作记录，并批量执行动作，或者当我们在使用编辑器时的回退撤销功能等，用链表结构来存储状态信息还是比较方便的。

最近比较火的react hooks API，其结构也是一个链表型的数据结构，所以学习链表还是非常有帮助的。读到这里可能还是有点懵，接下来我们先用js实现一个链表，这样有助于理解链表的本质，后面笔者会总结一下链表和数组的对比以及优劣势，方便大家对链表有一个更加直观的认识。

2.原生javascript实现一条单向链表

在上面一节介绍的链表结构中大家可能对链表有了初步的认识，因为javascript中没有链表的数据结构，为了模拟链表结构，我们可以通过js面向对象的方式实现一个链表结构及其API，具体设计如下： 前端进阶之从零到一实现单向 & 双向链表 有了以上需求点之后，这个链表才是基本可用的链表，那么我们一步步来实现它把。

2.1 定义链表结构

为了实现链表以及链表的操作，首先我们需要先定义链表的基本结构，第一步就是定义节点的数据结构。我们知道一个节点会有自己的值以及指向下一个节点的引用，所以可以这样定义节点：

let Node = function(el) {
      this.el = el;
      this.next = null;
 }

接下来我们定义一下链表的基本骨架：

// 单向链表, 每一个元素都有一个存储元素自身的节点和一个指向下一个元素引用的节点组成
function linkedList() {
  let Node = function(el) {
      this.el = el;
      this.next = null;
  }
  let length = 0
  let head = null  // 用来存储第一个元素的引用

  // 尾部添加元素
  this.append = (el) => {};  
  //插入元素
  this.insert = (pos, el) => {};  
  // 移除指定位置的元素
  this.removeAt = (pos) => {};  
  // 移除指定节点
  this.remove = (el) => {};    
  // 查询节点所在位置
  this.indexOf = (el) => {};  
  // 判断链表是否为空
  this.isEmpty = () => {};  
  // 返回链表长度
  this.size = () => {};  
  // 将链表转化为数组返回
  this.toArray = () => {}; 
}

由以上代码我们可以知道链表的初始长度为0，头部元素为null，接下来我们实现添加节点的功能。

2.2 实现添加节点

追加节点的时候首先需要知道头部节点是否存在，如果不存在直接赋值，存在的话则从头部开始遍历，直到找到下一个节点为空的节点，再赋值，并将链表长度+1，代码如下：

// 尾部添加元素
this.append = (el) => {
    let node = new Node(el),
        current;
    if(!head) {
      head = node
    }else {
      current = head;
      while(current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++
};

2.3 实现插入节点

实现插入节点逻辑首先我们要考虑边界条件，如果插入的位置在头部或者比尾部位置还大，我们就没必要从头遍历一遍处理了，这样可以提高性能，所以我们可以这样处理：

//插入元素
this.insert = (pos, el) => {
    if(pos >=0 && pos <= length) {
      let node = new Node(el),
          previousNode = null,
          current = head,
          curIdx = 0;
      if(pos === 0) {
        node.next = current;
        head = node;
      }else {
        while(curIdx++ < pos) {
          previousNode = current;
          current = current.next;
        }
        node.next = current;
        previousNode.next = node;
        length++;
        return true
      }
    }else {
      return false
    }
};

2.4 根据节点的值查询节点位置

根据节点的值查询节点位置实现起来比较简单，我们只要从头开始遍历，然后找到对应的值之后记录一下索引即可：

// 查询节点所在位置
this.indexOf = (el) => {
    let idx = -1,
        curIdx = -1,
        current = head;
    while(current) {
      idx++
      if(current.el === el) {
        curIdx = idx
        break;
      }
      current = current.next;
    }
    return curIdx
};

这里我们之所以要用idx和curIdx两个变量来处理，是因为如果用户传入的值不在链表里，那么idx的值就会有问题，所以用curIdx来保证准确性。

2.5 移除指定位置的节点

移除指定位置的节点也需要判断一下边界条件，可插入节点类似，但要注意移除之后一定要将链表长度-1，代码如下：

 // 移除指定位置的元素
this.removeAt = (pos) => {
    // 检测边界条件
    if(pos >=0 && pos < length) {
      let previousNode = null,
               current = head,
               curIdx = 0;
      if(pos === 0) {
        // 如果pos为第一个元素
        head = current.next
      }else {
        while(curIdx++ < pos) {
          previousNode = current;
          current = current.next;
        }
        previousNode.next = current.next;
      }
      length --;
      return current.el
    }else {
      return null
    }
};

2.6 移除指定节点

移除指定节点实现非常简单，我们只需要利用之前实现好的查找节点先找到节点的位置，然后在用实现过的removeAt即可，代码如下：

  // 移除指定节点
this.remove = (el) => {
  let idx = this.indexOf(el);
  this.removeAt(idx);
};

2.7 获取节点长度

这里比较简单，直接上代码：

// 返回链表长度
this.size = () => {
  return length
};

2.8 判断链表是否为空

判断链表是否为空我们只需要判断长度是否为零即可：

// 返回链表长度
this.size = () => {
  return length
};

2.9 打印节点

打印节点实现方式有很多，大家可以按照自己喜欢的格式打印，这里笔者直接将其打印为数组格式输出，代码如下：

// 将链表转化为数组返回
this.toArray = () => {
    let current = head,
        results = [];
    while(current) {
      results.push(current.el);
      current = current.next;
    }
    return results
};

这样，我们的单向链表就实现了，那么我们可以这么使用：

let link = new linkedList()
// 添加节点
link.append(1)
link.append(2)
// 查找节点
link.indexOf(2)
// ...

3.原生javascript实现一条个双单向链表

有了单向链表的实现基础，实现双向链表也很简单了，我们无非要关注的是双向链表的节点创建，这里笔者实现一个例子供大家参考：

let Node = function(el) {
      this.el = el;
      this.previous = null;
      this.next = null;
 }
let length = 0
let head = null  // 用来存储头部元素的引用
let tail = null  // 用来存储尾部元素的引用

由代码可知我们在节点中会有上一个节点的引用以及下一个节点的引用，同时这里笔者添加了头部节点和尾部节点方便大家操作。 大家可以根据自己的需求实现双向链表的功能，这里笔者提供一份自己实现的代码，可以参考交流一下：

// 双向链表, 每一个元素都有一个存储元素自身的节点和指向上一个元素引用以及下一个元素引用的节点组成
function doubleLinkedList() {
  let Node = function(el) {
      this.el = el;
      this.previous = null;
      this.next = null;
  }
  let length = 0
  let head = null  // 用来存储头部元素的引用
  let tail = null  // 用来存储尾部元素的引用

  // 尾部添加元素
  this.append = (el) => {
    let node = new Node(el)
    if(!head) {
      head = node
    }else {
      tail.next = node;
      node.previous = tail;
    }
    tail = node;
    length++
  };  
  // 插入元素
  this.insert = (pos, el) => {
    if(pos >=0 && pos < length) {
      let node = new Node(el);
      if(pos === length - 1) {
        // 在尾部插入
        node.previous = tail.previous;
        node.next = tail;
        tail.previous = node;
        length++;
        return true
      }
      let current = head,
          i = 0;
      while(i < pos) {
        current = current.next;
        i++
      }
      node.next = current;
      node.previous = current.previous;
      current.previous.next = node;
      current.previous = node;
      length ++;
      return true    
    }else {
      throw new RangeError(`插入范围有误`)
    }
  };  
  // 移除指定位置的元素
  this.removeAt = (pos) => {
    // 检测边界条件
    if(pos < 0 || pos >= length) {
      throw new RangeError(`删除范围有误`)
    }else {
      if(length) {
        if(pos === length - 1) {
          // 如果删除节点位置为尾节点,直接删除,节省查找时间
          let previous = tail.previous;
          previous.next = null;
          length --;
          return tail.el
        }else {
          let current = head,
              previous = null,
              next = null,
              i = 0;
          while(i < pos) {
            current = current.next
            i++
          }
          previous = current.previous;
          next = current.next;
          previous.next = next;
          length --;
          return current.el
        }
      }else {
        return null
      }
    }
  };  
  // 移除指定节点
  this.remove = (el) => {
    let idx = this.indexOf(el);
    this.removeAt(idx);
  };
  // 查询指定位置的链表元素
  this.get = (index) => {
    if(index < 0 || index >= length) {
      return undefined
    }else {
      if(length) {
        if(index === length - 1) {
          return tail.el
        }
        let current = head,
            i = 0;
        while(i < index) {
          current = current.next
          i++
        }
        return current.el
      }else {
        return undefined
      }
    }
  }
  // 查询节点所在位置
  this.indexOf = (el) => {
    let idx = -1,
        current = head,
        curIdx = -1;
    while(current) {
      idx++
      if(current.el === el) {
        curIdx = idx;
        break;
      }
      current = current.next;
    }
    return curIdx
  };  
  // 判断链表是否为空
  this.isEmpty = () => {
    return length === 0
  };  
  // 返回链表长度
  this.size = () => {
    return length
  };  
  // 将链表转化为数组返回
  this.toArray = () => {
    let current = head,
        results = [];
    while(current) {
      results.push(current.el);
      current = current.next;
    }
    return results
  }; 
}

4.链表和数组的对比及优缺点

实现完链表之后我们会对链表有更深入的认知，接下来我们进一步分析链表的优缺点。 笔者将从3个维度来带大家分析链表的性能情况：

  • 插入删除性能
  • 查询性能
  • 内存占用

我们先看看插入和删除的过程： 前端进阶之从零到一实现单向 & 双向链表 前端进阶之从零到一实现单向 & 双向链表 由上图可以发现，链表的插入、删除数据效率非常高，只需要考虑相邻结点的指针变化，因为不需要移动其他节点，时间复杂度是 O(1)。

再来看看查询过程： 前端进阶之从零到一实现单向 & 双向链表 我们对链表进行每一次查询时，都需要从链表的头部开始找起，一步步遍历到目标节点，这个过程效率是非常低的，时间复杂度是 O(n)。这方面我们使用数组的话效率会更高一点。

我们再看看内存占用。链表的内存消耗比较大，因为每个结点除了要存储数据本身，还要储存前后结点的地址。但是好处是可以动态分配内存。

另一方面，对于数组来说，也存在一些缺点，比如数组必须占用整块、连续的内存空间，如果声明的数组数据量过大，可能会导致“内存不足”。其次就是数组一旦需要扩容，会重新申请连续的内存空间，并且需要把上一次的数组数据全部copy到新的内存空间中。

综上所述，当我们的数据存在频繁的插入删除操作时，我们可以采用链表结构来存储我们的数据，如果涉及到频繁查找的操作，我们可以采用数组来处理。实际工作中很多底层框架的封装都是采用组合模式进行设计，一般纯粹采用某种数据结构的比较少，所以具体还是要根据所处环境进行适当的方案设计。

最后

如果想学习更多H5游戏, webpack，node，gulp，css3，javascript，nodeJS，canvas数据可视化等前端知识和实战，欢迎在公号《趣谈前端》加入我们的技术群一起学习讨论，共同探索前端的边界。 前端进阶之从零到一实现单向 & 双向链表

更多推荐

链表前端开发前端架构javascript循环链表数据结构post数组前端前端前端
点赞
收藏
评论区
推荐文章
blmius blmius
•
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s
4061
0
0
helloworld_34035044 helloworld_34035044
•
2年前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时，如何在新增行里自动增加id呢？能新增整数排序id吗？目前可以在新增行里自动增加id，但只能用uuid函数增加UUID编码，不能新增整数排序id。uuid函数说明：获取一个UUID，可以在填报表中用来创建数据ID语法：uuid()或uuid(sep)参数说明：sep布尔值，生成的uuid中是否包含分隔符''，缺省为
1108
0
0
待兔 待兔
•
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
1039
0
0
Jacquelyn38 Jacquelyn38
•
3年前
2020年前端实用代码段，为你的工作保驾护航
有空的时候，自己总结了几个代码段，在开发中也经常使用，谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
2355
0
0
Stella981 Stella981
•
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签，将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
1321
0
0
Easter79 Easter79
•
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移
1159
0
0
Wesley13 Wesley13
•
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败，请联系管理员！');中国在东8区所以加8方法二：selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
1281
0
0
Stella981 Stella981
•
3年前
Docker 部署SpringBoot项目不香吗？
　　公众号改版后文章乱序推荐，希望你可以点击上方“Java进阶架构师”，点击右上角，将我们设为★“星标”！这样才不会错过每日进阶架构文章呀。　　!(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)　　2
1053
0
0
Wesley13 Wesley13
•
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
1482
0
0
Python进阶者 Python进阶者
•
9个月前
Excel中这日期老是出来00：00：00，怎么用Pandas把这个去除
大家好，我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下：这日期老是出来00：00：00，怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下：pd.toexcel之前把这
478
0
0
徐小夕
徐小夕
Lv1
男 · 上海我们科技 · 前端开发leader
do or never do
文章
116
粉丝
30
获赞
61
热门文章
vue3.0-template-admin | 一款基于vite的开箱即用的后台管理模版
从零使用electron搭建桌面端可视化编辑器
从零开发一款可视化大屏制作平台
什么是低代码（Low-Code）？
成长路线: 一个前端工程师的120天