100字范文 > 【数据结构与算法】详解什么是双向链表并用代码手动实现一个双向链表

【数据结构与算法】详解什么是双向链表并用代码手动实现一个双向链表

时间：2023-09-02 16:32:05

本系列文章【数据结构与算法】所有完整代码已上传github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接

/Lpyexplore/structureAndAlgorithm-JS

上一篇文章讲解了链表的相关知识，并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构，叫做双向链表。顾名思义，普通的链表都是从head开始往后遍历结构内的元素，那么双向链表就是既可以从头开始遍历，又可以从结构的末尾开始遍历。

上一篇文章的跳转链接——【数据结构与算法】详解什么是链表，并用代码手动实现一个链表结构

本文就来详细讲解一下双向链表的概念以及如何实现一个双向链表。

公众号：前端印象不定时有送书活动，记得关注~关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

数据结构——双向链表

一、什么是双向链表二、双向链表的方法三、用代码实现双向链表（1）创建一个构造函数（2）创建内部构造函数（3）实现append()方法（4）实现insert()方法（5）实现get()方法（6）实现indexOf()方法（7）实现update()方法（8）实现removeAt()方法（9）实现remove()方法（10）实现isEmpty()方法（11）实现size()方法（12）实现toString()方法四、双向链表的补充五、总结

一、什么是双向链表

在上一篇文章中，我们用一个生活中的例子来解释了链表的概念，那么本文就延用这个例子，并对该例子做一些改动，来解释什么是双向链表

我们来看一下这个例子：

在一个教室里，所有的课桌排成一列，如图

相信在你们的读书生涯中，老师肯定有要求你们记住自己的前后桌是谁。所以该例子中，老师就要求学生们记住自己的前后桌，其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁；最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图：

这一列座位就相当于一个双向链表。

假如有一天，老师还没记住每个学生的名字，于是就问：这一列第三个人叫什么名字？这时就要从第一个学生开始数，例如从图中坐在第一个的小5开始数：第一个人是小5，他的后桌是小7；因此第二个人就是小7，他的后桌是小1；因此第三个人就是小1了。此时老师问小1：你的前桌叫什么名字？你的后桌叫什么名字？

因为刚开始老师就让每个学生记住了自己的前桌以及后桌，所以此时小1能很快地告诉老师他的前桌是小7，他的后桌是小6。

但是，我们设想一下，如果是上一篇文章的链表结构的例子中，如果老师在得知了第三个人是小1以后，询问小1的前桌叫什么名字，小1能回答上来吗？并不能，因为老师只让每个学生记住了自己的后桌，所以此时想要得知小1的前桌叫什么名字，只能这样：第三个学生叫小1，那么他的前桌就坐在第二个位置，所以从第一个学生开始数，第一个学生是小5，他的后桌是小7；因此第二个学生就是小7。当然本文举得例子中学生数量有点少，但一旦数量多起来了，每次问一个学生他的前桌叫什么名字的时候，都要从头开始数。

从中可以看出，让每个学生记住自己的前桌后桌是非常有必要的，因为在某些情况下，可以快速地解决问题。

上面讲了那么多，接下来我们就来看一下双向链表是什么样的，如图

可以看到，对比链表结构，双向链表多了一个指针tail，它是指向最后一个元素的，就相当于例子中的学生记住了自己是最后一排。

二、双向链表的方法

因为双向链表是链表的一种特殊形式，所以这两者的常用方法也是一样的，只不过实现方式不一样，那么我再列举一下有哪些常用方法吧，如下表

接下来就用JavaScript来实现一下以上这些方法

三、用代码实现双向链表

（1）创建一个构造函数

首先创建一个大的构造函数，用于存放双向链表的一些属性和方法。

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0}

其中，属性head表示双向链表中的第一个元素；属性tail表示双向链表中的最后一个元素

（2）创建内部构造函数

双向链表的每一个元素都有三个属性，即prev、item和next，分别表示该元素的前一个元素是谁、存储着该元素的值和该元素的后一个元素是谁。所以我们就在双向链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.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 = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//在末尾加入元素DoubleLinkedList.prototype.append = function (item) {// 1.创建新元素的实例对象let node = new Node(item)// 2.判断双向链表内是否有元素if(this.length === 0) {this.head = nodethis.tail = node}else {node.prev = this.tailthis.tail.next = nodethis.tail = node}// 3. 双向链表内元素 + 1this.length ++}}

接下里我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('js')dl.append('python')

此时的链表内是这样的

（4）实现insert()方法

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

为了方便大家理解，我用一个动图来向大家演示一下：

看完了方法的实现思路，我们来用代码实现一下该方法

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//向指定位置插入元素DoubleLinkedList.prototype.insert = function (position, item) {// 1.判断是否越界if(position < 0 || position > this.length) {return false}// 2.创建新元素的实例对象let node = new Node(item)let index = 0let current = this.headlet prev = null// 3.判断插入位置是否等于元素个数if(position === this.length) {//当 position 与 length相等时，就相当于在末尾添加元素this.append(item)}// 4. 判断元素是否添加到第一个位置else if(position === 0) {node.next = this.headthis.head.prev = nodethis.head = nodethis.length ++}else {// 5.遍历链表，直到找到position位置上的元素while (index < position) {prev = currentcurrent = current.nextindex ++}// 6.插入新元素prev.next = nodecurrent.prev = nodenode.prev = prevnode.next = currentthis.length ++}}}

接下来我们来使用一下该方法

let dl = new DoubleLinkedList()dl.insert(0, 'C++')

此时的双向链表是这样的

在执行一次insert()方法

di.append('js') //在末尾添加元素 jsdl.insert(1, 'python') //在索引 1处插入元素python

此时的双向链表是这样的

最后我们再向索引为3的位置插入元素java，因为此时length = 3，即双向链表元素个数为3，这就相当于在末尾添加元素

dl.insert(3, 'java')

所以此时的链表是这样的

（5）实现get()方法

get()方法就是获取对应位置上的元素。需要传入一个参数，即position，表示需要获取元素的索引

实现思路：

判断position是否越界。若越界，则直接返回false遍历链表，同时记录当前索引index，当index == position时，返回当前位置上的元素

该方法思路比较简单，几乎跟链表的get()方法一样，我们来看一下

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//获取对应位置上的元素DoubleLinkedList.prototype.get = function (position) {if(position < 0 || position > this.length - 1) {return false}let index = 0let current = this.headwhile (index < position) {current = current.nextindex ++}return current.item}}

我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('C++')dl.append('js')dl.append('python')dl.get(-2) //返回 falsedl.get(0) //返回 C++dl.get(2) //返回 pythondl.get(3) //返回 false

（6）实现indexOf()方法

indexOf()方法就跟数组的一样，获取某元素在双向链表中的索引值，若双向链表中不存在该元素，则返回-1。

这个方法思路很简单，就不详细讲解了，直接来看代码

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//获取元素的索引DoubleLinkedList.prototype.indexOf = function (item) {let current = this.headlet index = 0// 1.遍历双向链表while (index < this.length) {// 2. 找到对应元素，返回索引值if(current.item === item) {return index}else {index ++current = current.next}}// 3.未找到对应元素，返回 -1return -1}}

我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('C++')dl.append('js')dl.append('python')dl.indexOf('C++') //返回 0dl.indexOf('js') //返回 1dl.indexOf('python') //返回 2dl.indexOf('java')//返回 -1

（7）实现update()方法

update()方法就是用于修改双向链表中某位置上的元素的值。因此该方法需要传入两个参数，第一个参数是position，表示需要修改的元素的索引；第二个参数是NewItem，表示修改后的值

该方法的实现思路跟普通链表一模一样，所以就不讲解具体的实现思路了，直接来看代码吧

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//修改某位置上的元素DoubleLinkedList.prototype.update = function (position, item) {// 1.判断是否越界if(position < 0 || position >= this.length) {return false}let index = 0let current = this.head// 2.遍历双向链表，直到找到对应位置上的元素while (index < position) {index ++current = current.next}// 3.修改position索引位置上的元素的值current.item = itemreturn true}}

我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('C++')dl.append('js')dl.append('python')

此时的链表是这样的

现在调用一下update()方法，修改索引位置为2的元素的值

dl.update(2, 'java')

此时的链表是这样的

（8）实现removeAt()方法

removeAt()方法就是用于移除双向链表中某位置上的某元素。该方法只需要传入一个参数position，表示需要移除元素的索引

实现思路：

先判断position是否越界，若越界了，则直接返回false表示移除元素失败若没有越界，则判断position是否为0，若等于0，则直接将第一个链表的next值赋值给head，然后length - 1若position不等于0而等于length - 1，则将末尾元素的前一个元素，即tail的prev对应的元素的next属性设置成null，并将tail指向当前tail的prev，最后length - 1若position既不等于0，又不等于length - 1，则遍历双向链表，同时记录当前索引index，遍历的当前元素current，current的上一个元素prev当index === position时，将current的下一个元素，即current的next属性值赋值给prev的next属性，同时将current的下一个元素的prev的prev属性设置成prev，最后length - 1

为了让大家更好地理解该方法的实现思路，我制作了一个动图来帮助大家理解，如图

思路讲完了，我们直接来看代码

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//移除某位置上的元素DoubleLinkedList.prototype.removeAt = function (position) {// 1.判断是否越界if(position < 0 || position >= this.length) {return false}// 2.判断清除的元素是否为链表的唯一元素if(position === 0 && position === this.length - 1) {this.head = nullthis.tail = null}// 3.判断清除的元素是否为链表的第一个元素else if(position === 0) {this.head.next.prev = nullthis.head = this.head.next}// 4.判断清除的元素是否为链表的最后一个元素else if(position === this.length - 1) {this.tail.prev.next = nullthis.tail = this.tail.prev}else {let current = this.headlet prev = nulllet index = 0// 5.遍历双向链表while (index < position) {index ++prev = currentcurrent = current.next}// 6.删除对应位置上的元素prev.next = current.nextcurrent.next.prev = prev}// 7.元素个数 - 1this.length --return true}}

我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('C++')dl.append('js')dl.append('python')dl.removeAt(2) //删除索引为 2位置上的元素

此时的双向链表是这样的

（9）实现remove()方法

remove()方法就是用于移除双向链表链表中的某元素，并返回被删除元素所在的索引位置，若链表中没有对应元素，则返回false。该方法需要传入一个参数data用于查找链表中对应的元素

实现思路：

利用上面封装的indexOf()方法，将data作为参数传入，获取到data在链表中的索引index。再利用上面封装的removeAt()方法，将index作为参数传入，就可以实现remove()方法的功能了。

我们简单来写一下代码实现该方法

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//移除某元素DoubleLinkedList.prototype.remove = function (data) {// 1.获取data在双向链表中的索引let index = this.indexOf(data)// 2.利用removeAt()方法删除双向链表中的datathis.removeAt(index)// 3.返回被删除元素data在双向链表中的索引return index}}

我们来使用一下该方法

let dl = new DoubleLinkedList()dl.append('C++')dl.append('js')dl.append('python')dl.remove('js') //返回 1,此时length = 2dl.remove('python') //返回 1,此时length = 1

此时的链表是这样的

（10）实现isEmpty()方法

isEmpty()方法就是判断双向链表中是否有元素。若有元素，则返回false；反之，返回true

该方法的实现思路很简单，直接判断属性length是否等于0就可以了。

话不多说，我们赶紧写代码实现一下该方法

function DoubleLinkedList() {//属性this.head = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.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 = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.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 = nullthis.tail = nullthis.length = 0//元素的构造函数function Node(item) {this.item = itemthis.next = nullthis.prev = null}//展示双向链表数据DoubleLinkedList.prototype.toString = function () {let current = this.headlet string = ''while (current) {string += current.item + ' 'current = current.next}return string}}