JavaScript实现双向链表

呼市东平 發表於 2020-3-8 09:58:00

<h2 id="javascript实现双向链表">JavaScript实现双向链表</h2>
<h3 id="一双向链表简介">一、双向链表简介</h3>
双向链表：既可以从头遍历到尾，又可以从尾遍历到头。也就是说链表连接的过程是双向的，它的实现原理是：一个节点既有向前连接的引用，也有一个向后连接的引用。
双向链表的缺点：
<ul>
<li>每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些；</li>
<li>相对于单向链表，所占内存空间更大一些；</li>
<li>但是，相对于双向链表的便利性而言，这些缺点微不足道。</li>
</ul>
双向链表的结构：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/1.png" alt="image-20200227204728456" loading="lazy">
<ul>
<li>双向链表不仅有head指针指向第一个节点，而且有tail指针指向最后一个节点；</li>
<li>每一个节点由三部分组成：item储存数据、prev指向前一个节点、next指向后一个节点；</li>
<li>双向链表的第一个节点的prev指向null；</li>
<li>双向链表的最后一个节点的next指向null；</li>
</ul>
双向链表常见的操作（方法）：
<ul>
<li>append（element）：向链表尾部添加一个新的项；</li>
<li>inset（position，element）：向链表的特定位置插入一个新的项；</li>
<li>get（element）：获取对应位置的元素；</li>
<li>indexOf（element）：返回元素在链表中的索引，如果链表中没有元素就返回-1；</li>
<li>update（position，element）：修改某个位置的元素；</li>
<li>removeAt（position）：从链表的特定位置移除一项；</li>
<li>isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；</li>
<li>size（）：返回链表包含的元素个数，与数组的length属性类似；</li>
<li>toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；</li>
<li>forwardString（）：返回正向遍历节点字符串形式；</li>
<li>backwordString（）：返回反向遍历的节点的字符串形式；</li>
</ul>
<h3 id="二封装双向链表类">二、封装双向链表类</h3>
<h4 id="20创建双向链表类">2.0.创建双向链表类</h4>
先创建双向链表类DoubleLinklist，并添加基本属性，再实现双向链表的常用方法：
<pre><code> //封装双向链表类
function DoubleLinklist(){
 //封装内部类：节点类
 function Node(data){
 this.data = data
 this.prev = null
 this.next = null
 }

 //属性
 this.head = null
 this.tail ==null
 this.length = 0
 }
</code></pre>
<h4 id="21appendelement">2.1.append(element)</h4>
代码实现：
<pre><code> //append方法
 DoubleLinklist.prototype.append = data => {
 //1.根据data创建新节点
 let newNode = new Node(data)

 //2.添加节点
 //情况1：添加的是第一个节点
 if (this.length == 0) {
 this.tail = newNode
 this.head = newNode
 //情况2：添加的不是第一个节点
 }else {
 newNode.prev = this.tail
 this.tail.next = newNode
 this.tail = newNode
 }

 //3.length+1
 this.length += 1
 }
</code></pre>
过程详解：
添加节点时分为多种情况：
<ul>
<li>情况1：添加的是第一个节点：只需要让head和tail都指向新节点即可；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2.png" alt="image-20200228094847845" loading="lazy">
<ul>
<li>
情况2：添加的不是第一个节点，如下图所示：只需要改变相关引用的指向即可。
<ul>
<li>通过：newNode.prev = this.tail：建立指向1；</li>
<li>通过：this.tail.next = newNode：建立指向2；</li>
<li>通过：this.tail = newNode：建立指向3</li>
</ul>
要注意改变变量指向的顺序，最后修改tail指向，这样未修改前tail始终指向原链表的最后一个节点。
</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/3.png" alt="image-20200228095048677" loading="lazy">
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/4.png" alt="image-20200228095135301" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试append方法
list.append('aaa')
list.append('bbb')
list.append('ccc')
console.log(list);
</code></pre>
测试结果：
<ul>
<li>next方向：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/5.png" alt="image-20200305223911713" loading="lazy">
<ul>
<li>prev方向：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/6.png" alt="image-20200305224004626" loading="lazy">
<h4 id="22tostring汇总">2.2.toString()汇总</h4>
代码实现：
<pre><code> //将链表转变为字符串形式
 //一.toString方法
 DoubleLinklist.prototype.toString = () => {
 return this.backwardString()
 }

 //二.forwardString方法
 DoubleLinklist.prototype.forwardString = () => {
 //1.定义变量
 let current =this.tail
 let resultString = ""

 //2.依次向前遍历，获取每一个节点
 while (current) {
 resultString += current.data + "--"
 current = current.prev
 }
 return resultString
 }

 //三.backwardString方法
 DoubleLinklist.prototype.backwardString = () => {
 //1.定义变量
 let current = this.head
 let resultString = ""

 //2.依次向后遍历，获取每一个节点
 while (current) {
 resultString += current.data + "--"
 current = current.next
 }
 return resultString
 }
</code></pre>
过程详解：
三种获取字符串的方法：toString（）、forwardString（）、backwardString（）实现原理相似，仅以backWardString方法为例：
<ul>
<li>定义current变量记录当前指向的节点。首先让current指向第一个节点，然后通过 current = current.next 依次向后遍历。在while循环中以(current)作为条件遍历链表，只要current ！= null就一直遍历，由此可获取链表所有节点的数据。</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/7.png" alt="image-20200228100030713" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试字符串方法
list.append('aaa')
list.append('bbb')
list.append('ccc')
console.log(list.toString());
console.log(list.forwardString());
console.log(list.backwardString());
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/8.png" alt="image-20200305225437424" loading="lazy">
<h4 id="23insertpositionelement">2.3.insert(position,element)</h4>
代码实现：
<pre><code> //insert方法
 DoubleLinklist.prototype.insert = (position, data) => {
 //1.越界判断
 if (position < 0 || position > this.length) return false

 //2.根据data创建新的节点
 let newNode = new Node(data)

 //3.插入新节点
 //原链表为空
 //情况1：插入的newNode是第一个节点
 if (this.length == 0) {
 this.head = newNode
 this.tail = newNode
 //原链表不为空
 }else {
 //情况2：position == 0
 if (position == 0) {
 this.head.prev = newNode
 newNode.next = this.head
 this.head = newNode
 //情况3：position == this.length
 } else if(position == this.length){
 this.tail.next = newNode
 newNode.prev = this.tail
 this.tail = newNode
 //情况4：0 < position < this.length
 }else{
 let current = this.head
 let index = 0
 while(index++ < position){
 current = current.next
 }
 //修改pos位置前后节点变量的指向
 newNode.next = current
 newNode.prev = current.prev
 current.prev.next = newNode
 current.prev = newNode
 }
 }
 //4.length+1
 this.length += 1
 return true//返回true表示插入成功
 }
</code></pre>
过程详解：
插入节点可分为多种情况：
当原链表为空时：
<ul>
<li>情况1：插入的新节点是链表的第一个节点；只需要让head和tail都指向newNode即可。</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/9.png" alt="image-20200228102437899" loading="lazy">
当原链表不为空时：
<ul>
<li>情况2：当position == 0，即在链表的首部添加节点：如下图所示：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/10.png" alt="image-20200228103942238" loading="lazy">
首先，通过：this.head.prev = newNode，改变指向1；
然后，通过：newNode.next = this.head，改变指向2；
最后，通过：this.head = newNode，改变指向3；
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/11.png" alt="image-20200228110014565" loading="lazy">
<ul>
<li>情况3：position == this.length，即在链表的尾部添加节点，如下图所示：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/12.png" alt="image-20200228105207102" loading="lazy">
首先，通过：this.tail.next = newNode，改变指向1；（注意这里使用this.tail指向原链表最后一个节点，而不是this.head。因为当length>1时，this.head != this.tail。）
然后，通过：newNode.prev = this.tail，改变指向2；
最后，通过：this.tail = newNode，改变指向3；
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/13.png" alt="image-20200228110745214" loading="lazy">
<ul>
<li>情况4：0 < position < this.length，即在链表的中间插入新节点，假设在position = 1的位置插入，如下图所示：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/14.png" alt="image-20200228112941682" loading="lazy">
首先，需要定义变量current按照之前的思路，通过while循环找到position位置的后一个节点，循环结束后index = position
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/15.png" alt="image-20200228113257650" loading="lazy">
如下图所示：当position = 1时，current就指向了Node2。这样操作current就等同于间接地操作Node2，还可以通过current.prev间接获取Node1。得到了newNode的前一个节点和后一个节点就可以通过改变它们的prev和next变量的指向来插入newNode了。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/16.png" alt="image-20200228120701923" loading="lazy">
通过：newNode.next = current，改变指向1；
通过：newNode.prev = current.prev，改变指向2；
通过：current.prev.next = newNode，改变指向3；
<blockquote>
注意必须最后才修改current.prev的指向，不然就无法通过current.prev获取需要操作的Node1了。
</blockquote>
通过：current.prev = current，改变指向4；
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/17.png" alt="image-20200228124931441" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试insert方法
list.insert(0, '插入链表的第一个元素')
list.insert(0, '在链表首部插入元素')
list.insert(1, '在链表中间插入元素')
list.insert(3, '在链表尾部插入元素')
console.log(list);
alert(list)
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/18.png" alt="image-20200228130649724" loading="lazy">
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/19.png" alt="image-20200228130748735" loading="lazy">
<h4 id="24getposition">2.4.get(position)</h4>
代码实现：
<pre><code> //get方法
 DoubleLinklist.prototype.get = position => {
 //1.越界判断
 if (position < 0 || position >= this.length) {//获取元素时position不能等于length
 return null
 }

 //2.获取元素
 let current = null
 let index = 0
 //this.length / 2 > position:从头开始遍历
 if ((this.length / 2) > position) {
 current = this.head
 while(index++ < position){
 current = current.next
 }
 //this.length / 2 =< position:从尾开始遍历
 }else{
 current = this.tail
 index = this.length - 1
 while(index-- > position){
 current = current.prev
 }
 }
 return current.data
 }
</code></pre>
过程详解：
定义两个变量current和index，按照之前的思路通过while循环遍历分别获取当前节点和对应的索引值index，直到找到需要获取的position位置后的一个节点，此时index = pos =x，然后return current.data即可。
如果链表的节点数量很多时，这种查找方式效率不高，改进方法为：
<blockquote>
一定要通过this.length来获取链表的节点数否则就会报错。
</blockquote>
<ul>
<li>当this.length / 2 > position：从头（head）开始遍历；</li>
<li>当this.length / 2 < position：从尾（tail）开始遍历；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/20.png" alt="image-20200228144005347" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试get方法
list.append('a')
list.append('b')
list.append('b1')
list.append('b2')
list.append('b3')
list.append('b4')
list.append('b5')
list.append('b6')
list.append('b7')
console.log(list.get(0));
console.log(list.get(7));
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/21.png" alt="image-20200228145413524" loading="lazy">
<h4 id="25indexofelement">2.5.indexOf(element)</h4>
代码实现：
<pre><code> //indexOf方法
 DoubleLinklist.prototype.indexOf = data => {
 //1.定义变量
 let current = this.head
 let index = 0

 //2.遍历链表，查找与data相同的节点
 while(current){
 if (current.data == data) {
 return index
 }
 current = current.next
 index += 1
 }
 return -1
 }
</code></pre>
过程详解：
以（current）作为条件，通过while循环遍历链表中的所有节点（停止条件为current = null）。在遍历每个节点时将current指向的当前节点的data和传入的data进行比较即可。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/22.png" alt="image-20200228150427485" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试indexOf方法
list.append('a')
list.append('b')
list.append('c')
console.log(list.indexOf('a'));
console.log(list.indexOf('c'));
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/23.png" alt="image-20200228150612681" loading="lazy">
<h4 id="27updatepositionelement">2.7.update(position,element)</h4>
代码实现：
<pre><code> //update方法
 DoubleLinklist.prototype.update = (position, newData) => {
 //1.越界判断
 if (position < 0 || position >= this.length) {
 return false
 }

 //2.寻找正确的节点
 let current = this.head
 let index = 0
 //this.length / 2 > position:从头开始遍历
 if (this.length / 2 > position) {
 while(index++ < position){
 current = current.next
 }
 //this.length / 2 =< position:从尾开始遍历
 }else{
 current = this.tail
 index = this.length - 1
 while (index -- > position) {
 current = current.prev
 }
 }

 //3.修改找到节点的data
 current.data = newData
 return true//表示成功修改
 }
</code></pre>
过程详解：
以（index++ < position）为条件，通过while循环遍历链表中的节点（停止条件为index = position）。循环结束后，current指向需要修改的节点。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/24.png" alt="image-20200228152136284" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试update方法
list.append('a')
list.append('b')
console.log(list.update(1, 'c'));
console.log(list);
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/25.png" alt="image-20200228151340638" loading="lazy">
<h4 id="28removeatposition">2.8.removeAt(position)</h4>
代码实现：
<pre><code> //removeAt方法
 DoubleLinklist.prototype.removeAt = position => {
 //1.越界判断
 if (position < 0 || position >= this.length) {
 return null
 }

 //2.删除节点
 //当链表中length == 1
 //情况1：链表只有一个节点
 let current = this.head//定义在最上面方便以下各种情况返回current.data
 if (this.length == 1) {
 this.head = null
 this.tail = null
 //当链表中length > 1
 } else{
 //情况2：删除第一个节点
 if (position == 0) {
 this.head.next.prev = null
 this.head = this.head.next
 //情况3：删除最后一个节点
 }else if(position == this.length - 1){
 current = this.tail//该情况下返回被删除的最后一个节点
 this.tail.prev.next = null
 this.tail = this.tail.prev
 }else{
 //情况4：删除链表中间的节点
 let index = 0
 while(index++ < position){
 current = current.next
 }
 current.next.prev = current.prev
 current.prev.next = current.next
 }
 }

 //3.length -= 1
 this.length -= 1
 return current.data//返回被删除节点的数据
 }
</code></pre>
过程详解：
删除节点时有多种情况：
当链表的length = 1时：
<ul>
<li>情况1：删除链表中的所有节点：只需要让链表的head和tail指向null即可。</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/26.png" alt="image-20200228153331976" loading="lazy">
当链表的length > 1时：
<ul>
<li>
情况2：删除链表中的第一个节点：
通过：this.head.next.prev = null，改变指向1；
通过：this.head = this.head.next，改变指向2；
虽然Node1有引用指向其它节点，但是没有引用指向Node1，那么Node1会被自动回收。
</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/27.png" alt="image-20200228162347115" loading="lazy">
<ul>
<li>
情况3：删除链表中的最后一个节点：
通过：this.tail.prev.next = null，修改指向1；
通过：this.tail = this.tail.prev，修改指向2；
</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/28.png" alt="image-20200228161946691" loading="lazy">
<ul>
<li>情况4：删除链表中间的节点：</li>
</ul>
通过while循环找到需要删除的节点，比如position = x，那么需要删除的节点就是Node(x+1)，如下图所示：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/29.png" alt="image-20200228161648125" loading="lazy">
通过：current.next.prev = current.prev，修改指向1；
通过：current.prev.next = current.next，修改指向2；
这样就没有引用指向Node(x+1)了（current虽指向Node(x+1)，但current时临时变量，该方法执行完就会被销毁），随后Node(x+1)就会被自动删除。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/30.png" alt="image-20200228162415044" loading="lazy">
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

//2.测试removeAt方法
list.append('a')
list.append('b')
list.append('c')
console.log(list.removeAt(1));
console.log(list);
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/31.png" alt="image-20200228163935060" loading="lazy">
<h4 id="29其他方法">2.9.其他方法</h4>
其他方法包括：remove(element)、isEmpty()、size()、getHead()、getTail()
代码实现：
<pre><code>/*--------------------其他方法-------------------*/
//八.remove方法
DoubleLinklist.prototype.remove = data => {
//1.根据data获取下标值
let index = this.indexOf(data)

//2.根据index删除对应位置的节点
return this.removeAt(index)
}

//九.isEmpty方法
DoubleLinklist.prototype.isEmpty = () => {
return this.length == 0
}

//十.size方法
DoubleLinklist.prototype.size = () => {
return this.length
}

//十一.getHead方法：获取链表的第一个元素
DoubleLinklist.prototype.getHead = () => {
return this.head.data
}

//十二.getTail方法：获取链表的最后一个元素
DoubleLinklist.prototype.getTail = () => {
return this.tail.data
}
</code></pre>
测试代码：
<pre><code> //测试代码
//1.创建双向链表
let list = new DoubleLinklist()

/*------------其他方法的测试--------------*/
list.append('a')
list.append('b')
list.append('c')
list.append('d')
//remove方法
console.log(list.remove('a'));
console.log(list);
//isEmpty方法
console.log(list.isEmpty());
//size方法
console.log(list.size());
//getHead方法
console.log(list.getHead());
//getTead方法
console.log(list.getTail());
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/32.png" alt="image-20200228165845014" loading="lazy">
<h4 id="210完整实现">2.10.完整实现</h4>
<pre><code>//封装双向链表
function DoubleLinklist(){
//封装内部类：节点类
function Node(data){
this.data = data
this.prev = null
this.next = null
}

//属性
this.head = null
this.tail ==null
this.length = 0

//常见的操作：方法
//一.append方法
DoubleLinklist.prototype.append = data => {
//1.根据data创建新节点
let newNode = new Node(data)

//2.添加节点
//情况1：添加的是第一个节点
if (this.length == 0) {
 this.tail = newNode
 this.head = newNode
//情况2：添加的不是第一个节点
}else {
 newNode.prev = this.tail
 this.tail.next = newNode
 this.tail = newNode
}

//3.length+1
this.length += 1
}

//二.将链表转变为字符串形式
//2.1.toString方法
DoubleLinklist.prototype.toString = () => {
return this.backwardString()
}

//2.2.forwardString方法
DoubleLinklist.prototype.forwardString = () => {
//1.定义变量
let current =this.tail
let resultString = ""

//2.依次向前遍历，获取每一个节点
while (current) {
 resultString += current.data + "--"
 current = current.prev
}
return resultString
}

//2.3.backwardString方法
DoubleLinklist.prototype.backwardString = () => {
//1.定义变量
let current = this.head
let resultString = ""

//2.依次向后遍历，获取每一个节点
while (current) {
 resultString += current.data + "--"
 current = current.next
}
return resultString
}

//三.insert方法
DoubleLinklist.prototype.insert = (position, data) => {
//1.越界判断
if (position < 0 || position > this.length) return false

//2.根据data创建新的节点
let newNode = new Node(data)

//3.插入新节点
//原链表为空
 //情况1：插入的newNode是第一个节点
if (this.length == 0) {
 this.head = newNode
 this.tail = newNode
//原链表不为空
}else {
 //情况2：position == 0
 if (position == 0) {
 this.head.prev = newNode
 newNode.next = this.head
 this.head = newNode
 //情况3：position == this.length
 } else if(position == this.length){
 this.tail.next = newNode
 newNode.prev = this.tail
 this.tail = newNode
 //情况4：0 < position < this.length
 }else{
 let current = this.head
 let index = 0
 while(index++ < position){
 current = current.next
 }
 //修改pos位置前后节点变量的指向
 newNode.next = current
 newNode.prev = current.prev
 current.prev.next = newNode
 current.prev = newNode
 }
}
//4.length+1
this.length += 1
return true//返回true表示插入成功
}

//四.get方法
DoubleLinklist.prototype.get = position => {
//1.越界判断
if (position < 0 || position >= this.length) {//获取元素时position不能等于length
 return null
}

//2.获取元素
let current = null
let index = 0
//this.length / 2 > position:从头开始遍历
if ((this.length / 2) > position) {
 current = this.head
 while(index++ < position){
 current = current.next
}
//this.length / 2 =< position:从尾开始遍历
}else{
 current = this.tail
 index = this.length - 1
 while(index-- > position){
 current = current.prev
}
}
return current.data
}

//五.indexOf方法
DoubleLinklist.prototype.indexOf = data => {
//1.定义变量
let current = this.head
let index = 0

//2.遍历链表，查找与data相同的节点
while(current){
 if (current.data == data) {
 return index
 }
 current = current.next
 index += 1
}
return -1
}

//六.update方法
DoubleLinklist.prototype.update = (position, newData) => {
//1.越界判断
if (position < 0 || position >= this.length) {
 return false
}

//2.寻找正确的节点
let current = this.head
let index = 0
//this.length / 2 > position:从头开始遍历
if (this.length / 2 > position) {
 while(index++ < position){
 current = current.next
}
//this.length / 2 =< position:从尾开始遍历
}else{
 current = this.tail
 index = this.length - 1
 while (index -- > position) {
 current = current.prev
 }
}

//3.修改找到节点的data
current.data = newData
return true//表示成功修改
}

//七.removeAt方法
DoubleLinklist.prototype.removeAt = position => {
//1.越界判断
if (position < 0 || position >= this.length) {
 return null
}

//2.删除节点
//当链表中length == 1
//情况1：链表只有一个节点
let current = this.head//定义在最上面方便以下各种情况返回current.data
if (this.length == 1) {
 this.head = null
 this.tail = null
//当链表中length > 1
} else{
 //情况2：删除第一个节点
 if (position == 0) {
 this.head.next.prev = null
 this.head = this.head.next
 //情况3：删除最后一个节点
 }else if(position == this.length - 1){
 current = this.tail//该情况下返回被删除的最后一个节点
 this.tail.prev.next = null
 this.tail = this.tail.prev
 }else{
 //情况4：删除链表中间的节点
 let index = 0
 while(index++ < position){
 current = current.next
 }
 current.next.prev = current.prev
 current.prev.next = current.next
 }
}

//3.length -= 1
this.length -= 1
return current.data//返回被删除节点的数据
}
/*--------------------其他方法-------------------*/
//八.remove方法
DoubleLinklist.prototype.remove = data => {
//1.根据data获取下标值
let index = this.indexOf(data)

//2.根据index删除对应位置的节点
return this.removeAt(index)
}

//九.isEmpty方法
DoubleLinklist.prototype.isEmpty = () => {
return this.length == 0
}

//十.size方法
DoubleLinklist.prototype.size = () => {
return this.length
}

//十一.getHead方法：获取链表的第一个元素
DoubleLinklist.prototype.getHead = () => {
return this.head.data
}

//十二.getTail方法：获取链表的最后一个元素
DoubleLinklist.prototype.getTail = () => {
return this.tail.data
}

}
</code></pre>
<h3 id="三链表结构总结">三、链表结构总结</h3>
单向链表有head和next两个属性，双向链表有head、tail、next、prev四个属性。处理好它们的指向，相当于将它们正确地连接在一起，这样就组成了一条链，这就是简单链表的实现。
在实际开发中链表使用得非常多，比如Java中的LinkList就是双向链表。
<h4 id="31注意点">3.1.注意点</h4>
<ul>
<li>在链表中current = current.next 可以从左往右看，看成是current --> current.next，即current指向current的下一个节点。</li>
<li>删除节点的原理：只要没有引用指向该对象，无论该对象是否有引用指向其他对象，该对象都会被回收（删除）。</li>
<li>参数中凡是有position的都要进行越界判断。</li>
</ul>
<h4 id="32链表的增删改查">3.2.链表的增删改查</h4>
以双向链表为例：链表的增删改查无非就是获取链表中相应的节点改变其中的prev和next两个变量的指向。
<ul>
<li>
情况一：只需要head和tail两个变量就可以获取需要操作的变量（这里指的是能够轻松获取，当然你想通过head.next.next...或tail.prev.prev...来获取想要的节点也可以），在这种情况下链表的长度length：0<= length <=2。
</li>
<li>
情况二：不能靠tail和head来获取到需要操作的变量时，可采用while循环遍历的方式，找到需要操作的节点：
</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/33.png" alt="image-20200228113257650" loading="lazy">
在这种情况下，如果我们想要在链表的position = x的位置插入新节点，那么可以通过current获取position的后一个节点Node(x+1)，通过current.prev获取position位置的前一个节点Node(x)；之后修改Node(x+1)和Node(x)中的prev和next两个变量的指向即可在pos=x 的位置插入新节点。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/34.png" alt="image-20200228133450822" loading="lazy">
<h4 id="33修改链表引用指向">3.3.修改链表引用指向</h4>
应先修改newNode引用的指向，再修改其他引用
<ul>
<li>情况1：通过head和tail引用就能获取需要操作的节点时，最后更改head或tail变量的指向（因为它们分别指向链表的第一个和最后一个节点，获取其他节点时可能需要用到它们）。</li>
<li>情况2：使用current获取到需要操作的节点时，最后更改curren.next或current.prev的指向。因为current.next和current.prev表示的是Node(x+2)和Node(x)这两个节点，如下图所示，一旦变更它们的指向就无法获取Node(x)或Node(x+2)了，</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/35.png" alt="image-20200228133725909" loading="lazy">
<h4 id="34遍历链表">3.4.遍历链表</h4>
积累两种遍历思路
<ul>
<li>获取指定的position = x 位置的后一个节点和索引值：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/36.png" alt="image-20200228144005347" loading="lazy">
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/37.png" alt="image-20200228113257650" loading="lazy">
循环结束后index = position = x，变量current就指向了Node(x+1)，变量index的值为Node(x+1)的索引值x。
<ul>
<li>遍历链表中的所有节点：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/38.png" alt="image-20200228132334514" loading="lazy">
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/39.png" alt="image-20200228145930043" loading="lazy">
当current.next = null时停止循环，此时current指向链表的最后一个节点。
<blockquote>
参考资料：JavaScript数据结构与算法
</blockquote>

</div>
<div id="MySignature" role="contentinfo">
多抽出1分钟来学习，让你的生命更加精彩！ 
来源：https://www.cnblogs.com/AhuntSun-blog/p/12441095.html

頁: [1]

琼殿技术论坛's Archiver

JavaScript实现双向链表