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

徐小夕 等级 678 0 0

前言

前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用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游戏, webpacknodegulpcss3javascriptnodeJScanvas数据可视化等前端知识和实战,欢迎在公号《趣谈前端》加入我们的技术群一起学习讨论,共同探索前端的边界。 前端进阶之从零到一实现单向 & 双向链表

更多推荐

收藏
评论区

相关推荐

《前端实战总结》之使用解释器模式实现获取元素Xpath路径的算法
前端领域里基于javascript的设计模式和算法有很多,在很多复杂应用中也扮演着很重要的角色,接下来就介绍一下javascript设计模式中的解释器模式,并用它来实现一个获取元素Xpath路径的算法。 上期回顾 《前端实战总结》之迭代器模式的N1种应用场景(https://juejin.im/post/6844904008616771591)
从零到一教你基于vue开发一个组件库
前言 Vue是一套用于构建用户界面的渐进式框架,目前有越来越多的开发者在学习和使用.在笔者写完 从0到1教你搭建前端团队的组件系统(https://juejin.im
前端进阶之从零到一实现单向 & 双向链表
前言 前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章,如果感兴趣或者想进阶高级的朋友们可以参考学习一下: JavaScript 中的二
4K@60智能云台从零到一
![](https://oscimg.oschina.net/oscnet/378c3404-772f-4a7b-8968-a2fd109e61cb.png) 正文字数:6006  阅读时长:9分钟 > 近两年以来,短视频受到越来越多用户的喜爱和追捧,但短视频的制作成本却扼杀了大量内容创作者的热情和动力。LiveVideoStackCon2020北京
Curl之Post Json
curl Post Json $ curl -i -X POST -H "'Content-type':'application/x-www-form-urlencoded', 'charset':'utf-8', 'Accept': 'text/plain'" -d 'json_data={"a":"aaa","b":"bbb","data
IE和Firefox下event乱谈
如果在使用javascript的时候涉及到event处理,就需要知道event在不同的浏览器中的差异,因为javascript的事件模型有三种,它们分别是NN4、IE4+和W3C/Safari;这也造成了在不同的浏览器中处理event的差异,这里结合一些零碎的代码来说明如何做到event在IE4+和Firefox下的正常工作。首先看如下代码: functi
JavaScript零基础入门——(一)什么是JavaScript
JavaScript零基础入门——(一)什么是JavaScript ================================= 写在前面: 『Hello,大家好,我是振丹!从这节课开始,我会慢慢的带大家学习JavaScript的基础,至于进阶部分,有机会我也会专门开专题来讲。有做后端同学会说,现在微软的TypeScript开始火起来了,连Angu
JavaScript零基础入门——(十二)JavaScript的定时器
JavaScript零基础入门——(十二)JavaScript的定时器 =================================== 大家好,欢迎回到我们的JavaScript零基础入门。上一节课我们讲了JavaScript中一些常用的DOM操作,这里要补充一个点,上节课讲的table几个常用属性其实是有兼容性问题的,在部分IE浏览器中是不识别的
Node.js学习路线图
Node.js学习路线图 ------------ [从零开始nodejs系列文章](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fblog.fens.me%2Fseries-nodejs%2F),将介绍如何利Javascript做为服务端脚本,通过Nodejs框架web开发。Nodejs
Node.js简介及如何学习Node.js
本文介绍Node.js的诞生史以及如何学习Node.js。 Node.js简史 --------- 从Node.js的命名上可以看到,Node.js的官方开发语言是JavaScript。之所以选择使用JavaScript,显然与JavaScript的开发人员多有关。总所周知,JavaScript是伴随着互联网的发展而火爆起来的,JavaScript也是前
OCRunner 第零篇:从零教你写一个 iOS 热修复框架
> 作者: SilverFruity, https://github.com/SilverFruity 为什么要热修复 ------- 在软件开发过程中,很难避免 BUG 的存在,尤其是对于一些达到一定规模的 App 因为协作模式错综复杂,就很容易带着问题上线。 一旦问题上线之后,问题就麻烦了,不仅需要重新打包、测试,而且还需要重新提交审核,而这种修复
Python 与 Javascript 之比较
最近由于工作的需要开始开发一些Python的东西,由于之前一直在使用Javascript,所以会不自觉的使用一些Javascript的概念,语法什么的,经常掉到坑里。我觉得对于从Javascript转到Python,有必要总结一下它们之间的差异。 ### **基本概念** [Python](https://www.oschina.net/action/G
React TypeScript 从零实现 Popup 组件发布到 npm
> 本文转载自掘金《从0到1发布一个Popup组件到npm》,作者「海秋」。 > 点击下方阅读原文去点个赞吧! 上篇文章\[1\]中介绍了如何从 0 到 1 搭建一个 React 组件库架子,但为了一两个组件去搭建组件库未免显得大材小用。 这次以移动端常见的一个组件 `Popup` 为例,以最方便快捷的形式发布一个流程完整的 npm 包。 *
Springmvc异步上传文件
<script src="js/jquery.js" type="text/javascript"></script><script src="js/jquery.ext.js" type="text/javascript"></script><script src="js/jquery.form.js" type="text/javascript"
springboot2.x 从零到一(2、插件及基础环境开发)
1、用惯了idea,会觉得Eclipse质感较low。webstrom和idea界面美感和功能真香。下面先介绍几个自己也在用的插件,留名备份 1.1 lombok与swagger插件 -------------------- setting — plugins 搜索lombok,安装重启。pom文件添加依赖就能用了。 <dependency>