为什么需要双向链表
对于单向链表来说,从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历则没那么简单。另外,删除节点时我们需要借助于findPrevious这样一个辅助方法来实现,显得很繁琐。(此文章是对上一篇文章的后续,点击此处进入上一篇文章)
双向链表的实现
首先Node类需要增加一个previous属性:
function Node(element) { this.element = element; this.next = null; this.previous = null; }insert方法需要添加previous属性,使其指向该节点的前驱:
insert: function(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; newNode.previous = current; current.next = newNode; }remove方法将不再依赖于findPrevious方法,只需要在链表中找出存储待删除数据的节点,然后设置该节前驱的 next 属性,使其指向待删除节点的后继;设置该节点后继的 previous 属性,使其指向待删除节点的前驱。如下图所示:
remove: function(item) { var currNode = this.find(item); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } }增加反序显示链表的方法dispReverse:
//我们需要一个工具方法findLast来查找链表中的最后一个节点 findLast: function() { var currNode = this.head; while (!(currNode.next == null)) { currNode = currNode.next; } return currNode; } //反序显示链表数据 dispReverse: function() { var currNode = this.head; currNode = this.findLast(); while (!(currNode.previous == null)) { console.log(currNode.element); currNode = currNode.previous; } }完整的双向链表实现代码:
//节点类 function Node(element) { this.element = element; this.next = null; this.previous = null; } //链表类 function LList() { this.head = new Node("head"); } LList.prototype={ //反向显示所有节点 dispReverse:function(){ var currNode = this.head; currNode = this.findLast(); while (!(currNode.previous == null)) { console.log(currNode.element); currNode = currNode.previous; } }, //查找尾节点 findLast:function(){ var currNode = this.head; while (!(currNode.next == null)) { currNode = currNode.next; } return currNode; }, //删除节点 remove:function(item){ var currNode = this.find(item); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } }, //查找节点 find:function(item) { var currNode = this.head; while (currNode.element != item) { currNode = currNode.next; } return currNode; }, //插入节点 insert:function(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; newNode.previous = current; current.next = newNode; }, //正常显示所有节点 display:function() { var currNode = this.head; while (!(currNode.next == null)) { console.log(currNode.next.element); currNode = currNode.next; } } }
测试:
var lk=new LList(); //添加4个节点 lk.insert("likek","head"); lk.insert("zhangsan","likek"); lk.insert("lisi","zhangsan"); lk.insert("wangba","lisi"); //正常显示 lk.display(); /*likek zhangsan lisi wangba*/ //反向显示 lk.dispReverse(); /*wangba lisi zhangsan likek*/ //删除节点 lk.remove("lisi"); lk.display(); /*likek zhangsan wangba*/
相关推荐
接下来就是介绍两种常见的链表: 单向链表,双向链表在JavaScript中的实现。 单向链表 链表中最简单的形式就是单向链表,链表中的节点都包含两个部分,第一部分储存着自身信息,第二部分则储存有指向下一节点的指针...
通过JavaScript来封装实现常见的数据结构与算法 介绍 收录了各种常见的数据结构与算法通过 JavaScript 来封装的代码,可以直接拿取使用 注意 现在暂未更新完,进度会随着本人CSDN博客上的文章进度而更新,欢迎大家...
给单链表加一js实现JavaScript 算法和数据结构 排序算法 一些排序算法,它们是在 javascript 中实现的。 冒泡排序 堆排序 插入排序 归并排序 快速排序 选择排序 壳排序 力码 leetcode 问题的一些解决方案。 数据结构...
本文实例讲述了JavaScript数据结构之双向链表定义与使用方法。分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个...
数据结构与算法JavaScript描述 数组 列表 栈 队列 方块舞舞伴分配问题 基数排序 优先队列 链表 链表的实现 双向链表 循环链表 循环链表应用:约瑟夫环 字典 字典的实现 单词出现次数统计 散列表 散列的实现 散列表...
该存储库包含许多流行算法和数据结构的基于 JavaScript 的示例。 每个算法和数据结构都有自己单独的自述文件,其中包含相关解释和供进一步阅读的链接(包括 YouTube 视频的链接)。 阅读其他语言版本: 简体中文、...
JavaScript 数据结构和算法介绍用 JavaScript 编写的经典数据结构和算法示例。 查看测试以获取使用示例。算法数据结构: lib/linked_list.js 链表是一个轻量级的存储对象,它按照添加的顺序线性存储数据。 添加是O( ...
一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段,称为链接,它们是对节点序列中上一个节点和下一个节点的引用 开始节点和结束节点的上一个链接和下一...
leetcode题库 blog 2018-12 ...数据结构与算法专题 链表 - 单链表 - 双链表 数 - 二叉树 图 设计模式 工具类 git TODO 函数式编程 js原生函数及工具ramda库 数据结构及算法 webgl及three.js可视化 技巧
JavaScript 中的数据结构和算法用 Coffeescript 编写,使用 Mocha 和 Chai 进行测试。 安装: npm installgrunt二叉搜索树BST 的递归实现。 具有三个前序/内序/后序遍历以及广度优先遍历。双向链表不言自明节点双向...
创建我自己的算法和数据结构实现,并分享我所学到的知识以帮助其他想要学习它们的人,从而尽可能多地了解算法和数据结构。 通过学习《算法导论》一书(Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、...
algorithm js数据结构和算法 twoWay.js 双向循环链表,将进入的数据构建成一个圆环,每个节点双向引用。
各种算法和数据结构的实现已经通过动画幻灯片进行了演示和实现。 它涵盖了许多关于算法和数据结构的面试室问题。 问题和解决方案由- 动画幻灯片。 (为了使算法可视化更快) IDE 上的编码算法。 该课程涵盖以下主题 ...
计算机科学数据结构和算法 首先,我将使用 javascript 实现所有内容:nodejs、gulp、mocha 和其他 javascript 工具。 也许以后,我也可以用 C++、php、python 等其他语言来实现。 实施的: 堆 队列 二叉树 计划: ...
leetcode 阿里巴巴问题JavaScript 中的算法 在 JavaScript 中实现的算法、数据结构和编码挑战。 这个存储库是我在一段时间内实施的算法、数据结构和编码挑战的集合。...双向链表实现的方法:insert
vue中常用的算法使用例子理解原理,包括标准快排;二叉树diff算法;二叉树比较;二叉树遍历;二维数据;广度优先搜索;还原二叉树;空间复杂度;快速排序;...数据结构;双向链表;选择排序;栈与队列。
leetcode 阿里巴巴问题Java中的算法 用 Java 实现的算法、数据结构和编码挑战。 这个存储库是我在一段时间内实施的算法、数据结构和编码挑战的集合。...双向链表实现的方法:insertFirst()、insertLast()
2012-06-11 21:09 1,553,768 数据结构算法Visual.C.6.0程序集_源码.rar 2012-06-11 21:42 87,040 时域卷积定理的证明.ppt 2012-06-11 21:10 4,371 更改网关IP.rar 2012-06-11 20:57 1,419 栈的实现.txt 2012-06-11 ...
数据结构 以多种编程语言实现的算法和流行数据结构示例,经过全面测试。 要构建项目,请使用gradle build ##Algorithms ###Merge Sort 和 Inversion Count | | | | ###快速排序和比较计数 | | | | ###Karger 的最小...
####数据结构 基本数组 动态数组 单链表 双向链表 跳过列表 哈希表 二叉搜索树 笛卡尔树 B树 红黑树 展开树 AVL树 ####堆 链表(排序) 链表(未排序) 二叉堆 二项堆 斐波那契堆 ####图表 邻接表 发生率列表 ...