专栏首页趣谈前端javascript探秘之从零到一实现单向 & 双向链表

javascript探秘之从零到一实现单向 & 双向链表

前言

前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用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到新的内存空间中。

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

本文分享自微信公众号 - 趣谈前端(beautifulFront),作者:徐小夕

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3分钟教你用原生js实现具有进度监听的文件上传预览组件

    本文主要介绍如何使用原生js,通过面向对象的方式实现一个文件上传预览的组件,该组件利用FileReader来实现文件在前端的解析,预览,读取进度等功能,...

    徐小夕
  • 15分钟带你了解前端工程师必知的javascript设计模式(附详细思维导图和源码)

    设计模式是一个程序员进阶高级的必备技巧,也是评判一个工程师工作经验和能力的试金石.设计模式是程序员多年工作经验的凝练和总结,能更大限度的优化代码以及对已有代码的...

    徐小夕
  • 基于jsoneditor二次封装一个可实时预览的json编辑器组件(react版)

    做为一名前端开发人员,掌握vue/react/angular等框架已经是必不可少的技能了,我们都知道,vue或react等MVVM框架提倡组件化开发,这样一方面...

    徐小夕
  • 《javascript数据结构和算法》读书笔记(3):链表

    储存多个元素,数组是最常用的。无论何种语言,都实现了数组。但是大多数语言中,数组的长度是固定的。数组修改操作的成本非常高。

    一粒小麦
  • 2-5 线性表之循环链表

    为了方便,我这里使用带头结点的单链表来构建循环链表,至于单链表带不带头结点的异同,我在前面的线性表之链表那篇文章中已经做过分析,就不再赘述。

    TeeyoHuang
  • 《剑指offer》分解让复杂问题更简单

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    ConardLi
  • 重读《学习JavaScript数据结构与算法-第三版》- 第6章 链表(一)

    本章为重读《学习JavaScript数据结构与算法》的系列文章,该章节主要讲述数据结构-链表,以及实现链表的过程和原理。

    胡哥有话说
  • 数据结构知否知否系列之 — 线性表的顺序与链式存储篇(8000 多字长文)

    线性表是由 n 个数据元素组成的有限序列,也是最基本、最简单、最常用的一种数据结构。

    五月君
  • 用js来实现那些数据结构08(链表02-双向链表)

      其实无论在任何语言中,一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝...

    zaking
  • 推力达1牛,我国首款牛级霍尔推力器完成点火试验

    近日,航天集团六院801所成功研制出了我国首款20千瓦大功率霍尔推力器,并完成点火试验,实现了我国自研推力器推力从毫牛级向牛级的跨越。

    镁客网

扫码关注云+社区

领取腾讯云代金券