【数据结构与算法】详解什么是双向链表，并用代码手动实现一个双向链表 |
您所在的位置：网站首页 › 数据结构用什么实现 › 【数据结构与算法】详解什么是双向链表，并用代码手动实现一个双向链表 |
【数据结构与算法】详解什么是双向链表，并用代码手动实现一个双向链表
|
本系列文章【数据结构与算法】所有完整代码已上传 github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接 https://github.com/Lpyexplore/structureAndAlgorithm-JS上一篇文章讲解了链表的相关知识，并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构，叫做 双向链表。 顾名思义，普通的链表都是从 head 开始往后遍历结构内的元素，那么双向链表就是既可以从头开始遍历，又可以从结构的末尾开始遍历。 上一篇文章的跳转链接——【数据结构与算法】详解什么是链表，并用代码手动实现一个链表结构 本文就来详细讲解一下双向链表的概念以及如何实现一个双向链表。 公众号：前端印象不定时有送书活动，记得关注~关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】
在上一篇文章中，我们用一个生活中的例子来解释了链表的概念，那么本文就延用这个例子，并对该例子做一些改动，来解释什么是 双向链表 我们来看一下这个例子： 在一个教室里，所有的课桌排成一列，如图 假如有一天，老师还没记住每个学生的名字，于是就问：这一列第三个人叫什么名字？这时就要从第一个学生开始数，例如从图中坐在第一个的 小5 开始数：第一个人是 小5，他的后桌是 小7；因此第二个人就是 小7，他的后桌是 小1；因此第三个人就是 小1 了。此时老师问 小1：你的前桌叫什么名字？你的后桌叫什么名字？ 因为刚开始老师就让每个学生记住了自己的前桌以及后桌，所以此时 小1 能很快地告诉老师他的前桌是 小7，他的后桌是 小6。 但是，我们设想一下，如果是上一篇文章的 链表结构 的例子中，如果老师在得知了第三个人是 小1 以后，询问 小1 的前桌叫什么名字，小1 能回答上来吗？并不能，因为老师只让每个学生记住了自己的后桌，所以此时想要得知 小1 的前桌叫什么名字，只能这样：第三个学生叫 小1，那么他的前桌就坐在第二个位置，所以从第一个学生开始数，第一个学生是 小5，他的后桌是 小7；因此第二个学生就是 小7。当然本文举得例子中学生数量有点少，但一旦数量多起来了，每次问一个学生他的前桌叫什么名字的时候，都要从头开始数。 从中可以看出，让每个学生记住自己的前桌后桌是非常有必要的，因为在某些情况下，可以快速地解决问题。 上面讲了那么多，接下来我们就来看一下 双向链表 是什么样的，如图 因为 双向链表 是链表的一种特殊形式，所以这两者的常用方法也是一样的，只不过实现方式不一样，那么我再列举一下有哪些常用方法吧，如下表 方法含义append()向双向链表尾部追加元素insert()在双向链表的某个位置插入元素get()获取双向链表对应位置的元素indexOf()获取某元素在双向链表中的索引update()修改双向链表中某个位置上的元素的值removeAt()移除双向链表中某位置上的某元素remove()移除双向链表中的某元素isEmpty()判断双向链表内是否为空size()返回双向链表内元素个数toString()以字符串的形式展示双向链表内的所有元素接下来就用 JavaScript 来实现一下以上这些方法 三、用代码实现双向链表 （1）创建一个构造函数首先创建一个大的构造函数，用于存放双向链表的一些属性和方法。 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 }其中，属性 head 表示双向链表中的第一个元素；属性 tail 表示双向链表中的最后一个元素 （2）创建内部构造函数双向链表的每一个元素都有三个属性，即prev 、item 和 next，分别表示该元素的前一个元素是谁 、存储着该元素的值和该元素的后一个元素是谁。所以我们就在双向链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } } （3）实现append()方法append()方法就是将元素添加到双向链表的末尾。 实现思路： 先创建新元素的实例对象 node先判断双向链表内有无元素，若没有元素，则将属性 head 和 属性 tail 都指向 node，最后属性 length + 1若双向链表中有元素了，则因为双向链表内多了一个指针 tail，所以我们要实现 append()方法也就方便了很多，只需要将 tail 指向 node，然后将原本的末尾元素 old_node 的 next 指向 node，并将 node 的 prev属性指向 old_node即可，然后属性 length + 1为了方便大家理解，我用一个动图来向大家演示一下： 思路讲解完了，我们来实现一下该方法 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //在末尾加入元素 DoubleLinkedList.prototype.append = function (item) { // 1.创建新元素的实例对象 let node = new Node(item) // 2.判断双向链表内是否有元素 if(this.length === 0) { this.head = node this.tail = node } else { node.prev = this.tail this.tail.next = node this.tail = node } // 3. 双向链表内元素 + 1 this.length ++ } }接下里我们来使用一下该方法 let dl = new DoubleLinkedList() dl.append('js') dl.append('python')此时的链表内是这样的 insert()方法就是在指定的索引位置插入元素。一共需要传入两个参数，第一个是 position，表示需要插入元素的位置；第二个参数是 item，表示元素的值 实现思路： 创建新的元素实例对象 node判断指定的索引位置 position 是否越界，即是否小于0，或者大于双向链表的长度。若越界了，则直接返回false判断 position 是否为0。若为0，则直接将双向链表原本的第一个元素 ，也就是 head所对应的元素 old_node 赋值给 node的 next属性，再将 node 赋值给 old_node 的 prev 属性，然后将 node赋值给 head，表示现在链表的第一个元素为 node若 position 不为0，则遍历双向链表，同时记录遍历的索引 index 、遍历的上一个元素 prev 和在 index索引位置上的元素 current，当 index == position时，将 node赋值给 prev的 next属性，将 current 赋值给 node的 next属性，再将 prev 赋值给 node 的 prev 属性，最后将 node 赋值给 current 的 prev 属性属性 length + 1为了方便大家理解，我用一个动图来向大家演示一下： 我们来使用一下该方法 let dl = new DoubleLinkedList() dl.append('C++') dl.append('js') dl.append('python') dl.indexOf('C++') //返回 0 dl.indexOf('js') //返回 1 dl.indexOf('python') //返回 2 dl.indexOf('java') //返回 -1 （7）实现update()方法update()方法就是用于修改双向链表中某位置上的元素的值。因此该方法需要传入两个参数，第一个参数是 position，表示需要修改的元素的索引；第二个参数是 NewItem，表示修改后的值 该方法的实现思路跟普通链表一模一样，所以就不讲解具体的实现思路了，直接来看代码吧 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //修改某位置上的元素 DoubleLinkedList.prototype.update = function (position, item) { // 1.判断是否越界 if(position = this.length) { return false } let index = 0 let current = this.head // 2.遍历双向链表，直到找到对应位置上的元素 while (index //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //移除某位置上的元素 DoubleLinkedList.prototype.removeAt = function (position) { // 1.判断是否越界 if(position = this.length) { return false } // 2.判断清除的元素是否为链表的唯一元素 if(position === 0 && position === this.length - 1) { this.head = null this.tail = null } // 3.判断清除的元素是否为链表的第一个元素 else if(position === 0) { this.head.next.prev = null this.head = this.head.next } // 4.判断清除的元素是否为链表的最后一个元素 else if(position === this.length - 1) { this.tail.prev.next = null this.tail = this.tail.prev } else { let current = this.head let prev = null let index = 0 // 5.遍历双向链表 while (index //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //移除某元素 DoubleLinkedList.prototype.remove = function (data) { // 1.获取data在双向链表中的索引 let index = this.indexOf(data) // 2.利用removeAt()方法删除双向链表中的data this.removeAt(index) // 3.返回被删除元素data在双向链表中的索引 return index } }我们来使用一下该方法 let dl = new DoubleLinkedList() dl.append('C++') dl.append('js') dl.append('python') dl.remove('js') //返回 1,此时length = 2 dl.remove('python') //返回 1,此时length = 1此时的链表是这样的 isEmpty()方法就是判断双向链表中是否有元素。若有元素，则返回 false；反之，返回 true 该方法的实现思路很简单，直接判断属性 length 是否等于 0 就可以了。 话不多说，我们赶紧写代码实现一下该方法 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //判断双向链表是否为空 DoubleLinkedList.prototype.isEmpty = function () { if(this.length === 0) { return true } else { return false } } }我们来使用一下该方法 let dl = new DoubleLinkedList() dl.isEmpty() //返回 true,此时双向链表中无元素 dl.append('C++') dl.append('js') dl.append('python') dl.isEmpty() //返回 false,此时双向链表中有3个元素 （11）实现size()方法szie()方法就是返回链表内的元素个数 我们来实现一下该方法 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //返回双向链表元素个数 DoubleLinkedList.prototype.size = function () { return this.length } }我们来使用一下该方法 let dl = new DoubleLinkedList() dl.size() //返回 0,此时双向链表中无元素 dl.append('C++') dl.append('js') dl.append('python') dl.size() //返回 3,此时双向链表中有3个元素 （12）实现toString()方法toString()方法就是以字符串的形式展示双向链表内的所有元素 实现思路很简单，就是遍历双向链表中的每一个元素，并将每个元素以字符串的形式连接起来即可 我们来实现一下该方法 function DoubleLinkedList() { //属性 this.head = null this.tail = null this.length = 0 //元素的构造函数 function Node(item) { this.item = item this.next = null this.prev = null } //展示双向链表数据 DoubleLinkedList.prototype.toString = function () { let current = this.head let string = '' while (current) { string += current.item + ' ' current = current.next } return string } } 四、双向链表的补充其实平常的时候 双向链表 的应用场景比较多，而且它某些时候比普通的链表数据操作的效率要高。 例如：假设有一个 length = 9999 的普通链表，我们要删除该链表索引为 9997 的元素，那么我们只能从链表的第一个元素，即从 head 指向的元素开始遍历链表，直到找到索引为 9997 的元素，一共要遍历9998次，这样效率是非常低的。 那么如果把普通链表换成双向链表呢？当我们得知要删除索引为 9997 的元素时，我们可以先计算 9997 与 9999 - 1 = 9998 的差值 、9997 与 0 的差值，若前者差值小，则可以从双向链表的 tail 指向的元素往前遍历；反之，从 head 指向的元素往后遍历。如图 双向链表的讲解就到这里了，希望大家对双向链表有了更深一层的理解。下一篇文章我将讲解一下哈希表。 大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。 然后大家可以关注一下我的微信公众号：前端印象，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。 或者也可以去我的github上获取完整代码，欢迎大家点个Star https://github.com/Lpyexplore/structureAndAlgorithm-JS我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~ 带你们在Python爬虫的过程中学习Web前端 |
相信在你们的读书生涯中，老师肯定有要求你们记住自己的前后桌是谁。所以该例子中，老师就要求学生们记住自己的前后桌，其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁；最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图： 
这一列座位就相当于一个 双向链表。
可以看到，对比 链表结构，双向链表 多了一个指针 tail，它是指向最后一个元素的，就相当于例子中的学生记住了自己是最后一排。
看完了方法的实现思路，我们来用代码实现一下该方法
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |