加入收藏 | 设为首页 | 会员中心 | 我要投稿 PHP编程网 - 黄冈站长网 (http://www.0713zz.com/)- 数据应用、建站、人体识别、智能机器人、语音技术!
当前位置: 首页 > 综合聚焦 > 编程要点 > 资讯 > 正文

前端进阶:链表的概念和应用

发布时间:2021-06-04 16:03:36 所属栏目:资讯 来源:互联网
导读:副标题#e# 为了实现链表以及链表的操作,首先我们需要先定义链表的基本结构,第一步就是定义节点的数据结构。我们知道一个节点会有自己的值以及指向下一个节点的引用,所以可以这样定义节点: letNode=function(el){ this.el=el; this.next=null; } 接下来
副标题[/!--empirenews.page--]

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

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; 

(编辑:PHP编程网 - 黄冈站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

推荐文章
    热点阅读