思享工具箱

原生JS实现双向链表

摘要：
Node类表示要加入链表中的项。它包含一个value属性，即要添加到链表中的值，一个next属性，即指向链表中下一个节点项的指针，以及一个prev属性，即指向链表中上一个节点项的指针。我们将在current和previous元素之间插入新元素。首先，node.next将指向current，而previous.next将指向node，这样就不会丢失节点之间的链接。
1.前言

双向链表和单向链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素，如下图所示：
原生JS实现双向链表第1张

从图中可以看到，双向链表中，在每个节点Node里有prev属性（指向上一个节点的指针）和next属性（指向下一个节点的指针），并且在链表中也有head属性（用来存储链表第一项的引用）和tail属性（用来存储链表最后一项的引用）。

2.代码实现

首先，我们可以先创建一个双向链表DoublyLinkedList类：

//创建一个Node辅助类，用来生成节点
class Node{
    constructor(value){
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    append(element){
       
    }
    find(value){
        
    }
    insert(position,element){
      
    }
    remove(value) {
       
    }
    removeAt(position){
        
    }
    size(){
       
    }
    isEmpty(){
       
    }
    nextPrint() {
        
    }
    prevPrint() {
        
    }
}

在创建DoublyLinkedList类时，我们还需要创建一个Node辅助类。Node类表示要加入链表中的项。它包含一个value属性，即要添加到链表中的值，一个next属性，即指向链表中下一个节点项的指针，以及一个prev属性，即指向链表中上一个节点项的指针。

DoublyLinkedList类也有存储链表项的数量的length属性（内部/私有变量）。
我们还需要存储第一个节点和最后一个节点的引用。为此，可以把这两个个引用分别存储在head和tail的变量中。

此外，DoublyLinkedList类中还包含了如下一些方法：

  • append(value)：向链表尾部追加一个新元素
  • find(value):根据元素值查找元素，并返回该元素
  • insert(position, value)：向链表的特定位置插入一个新的项
  • remove(value)：根据元素值删除元素，并返回该元素
  • removeAt(position)：根据元素位置删除元素，并返回该元素
  • isEmpty()：判断链表是否为空，是返回true，否返回false
  • size()：返回链表包含的元素个数
  • nextPrint():顺序遍历打印该链表
  • prevPrint():逆序遍历打印该链表
3.具体方法实现

3.1 append(value)：向链表尾部追加一个新元素

/**
* 向链表尾部追加一个新元素
* @param {} element  要追加的新元素
*/
append(value){
    let node = new Node(value);
    let current = this.head;
    if (!this.head) {   //如果链表为空
        this.head = node;
        this.tail = node;
    }else{
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
    }
    this.length ++;
}

3.2 find(value):根据元素值查找元素，并返回该元素

/**
* 根据元素值查找元素，并返回该元素
* @param {*} value 
*/
find(value){
    let current = this.head;
    if (!this.head) {   //如果链表为空
        console.log("这是一个空链表！！！");
        return null;
    }
    if (current.value == value) {
        return current;
    }
    while (current.next) {
        current = current.next;
        if (current.value === value) {
            return current
        }
    }
    console.log("没有找到该元素！！！");
    return null;
}

3.3 insert(position, value)：向链表的特定位置插入一个新的项

/**
* 向链表的特定位置插入一个新的项
* @param {Number} position 要插入的位置
* @param {*} element  要插入的新元素值
*/
insert(position,element){
    if (position >= 0 && position <= this.length) {
        let node = new Node(element);
        let current = this.head;
        let previous = null;
        let index = 0;
        if (position === 0) {   //如果在第一个位置插入
            if (!this.head) {   //如果链表为空
                this.head = node;
                this.tail = node;
            }else{
                node.next = current;
                current.prev = node;
                this.head = node;
            }
        } else if(position === this.length){   //如果在最后一个位置插入
            current = this.tail;
            current.next = node;
            node.prev = current;
            this.tail = node;
        }else {                          //如果在中间任意一个位置插入
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            node.next = current;
            previous.next = node;

            current.prev = node;
            node.prev = previous;
        }
        this.length++;
        return true;
    }else {
        console.log('该位置不存在！');
        return false;
    }   
}

代码说明：

向任意位置插入一个新元素，总共可归纳为三种情况：

  1. 在列表的第一个位置（列表的起点）插入一个新元素。如果列表为空，只需要把head和tail都指向这个新节点。如果不为空，current变量将是对列表中第一个元素的引用。就像我们在链表中所做的，把node.next设为current，而head将指向node（它将成为列表中的第一个元素）。不同之处在于，我们还需要为指向上一个元素的指针设一个值current.prev指针将由指向null变为指向新元素。node.prev指针已经是null，因此不需要再更新任何东西。
  2. 在列表最后添加一个新元素。因为我们还控制着指向最后一个元素的指针（tail）。current变量将引用最后一个元素。然后开始建立第一个链接：node.prev将引用current。current.next指针（指向null）将指向node（由于构造函数，node.next已经指向了null）。然后只剩一件事了，就是更新tail，它将由指
    向current变为指向node。
  3. 在列表中间插入一个新元素。通过迭代列表，直到到达要找的位置。我们将在current和previous元素之间插入新元素。首先，node.next将指向current，而previous.next将指向node，这样就不会丢失节点之间的链接。然后需要处理所有的链接：current.prev将指向node，而node.prev将指向previous。

3.4 remove(value)：根据元素值删除元素，并返回该元素

remove(value) {
    let current = this.find(value);
    if (current == null) {
        console.log("没有找到该元素！！！");
        return null;
    } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }
    this.length--;
    return current;
}

3.5 removeAt(position)：根据元素位置删除元素，并返回该元素

removeAt(position){
    if (position >= 0 && position <= this.length) {
        let current = this.head;
        let previous = null;
        let index = 0;
        if (position === 0) {          //如果删除第一个位置
            head = current.next;
            head.prev = null;
            if (this.length === 1) {   //如果链表中只有一个元素
                this.tail = null;
            }
        } else if (position === this.length-1) {   //如果删除最后一个位置
            current = this.tail;
            this.tail = current.prev;
            this.tail.next = null;
        } else {
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = current.next;
            current.next.prev = previous;
        }
        this.length--;
        return current;
    } else {
        console.log('该位置不存在！');
        return null;
    }
}

代码说明：

从任意位置删除一个元素，总共也可归纳为三种情况：

  1. 从头部移除第一个元素。current变量是对列表中第一个元素的引用，也就是我们想移除的元素。需要做的就是改变head 的引用， 将其从current 改为下一个元素
    。但我们还需要更新current.next指向上一个元素的指针（因为第一个元素的prev指针是null）。因此，把head.prev的引用改为null（因为head也指向列表中新的第一个元素，或者也可以用current.next.prev）。由于还需要控制tail的引用，我们可以检查要移除的元素是否是第一个元素，如果是，只需要把tail也设为null。
  2. 从尾部最后一个位置移除元素。既然已经有了对最后一个元素的引用（tail），我
    们就不需要为找到它而迭代列表。这样我们也就可以把tail的引用赋给current变量，接下来，需要把tail的引用更新为列表中倒数第二个元素（current.prev，或者tail.prev也可以）。既然tail指向了倒数第二个元素，我们就只需要把next指针更新为null（tail.next= null）。
  3. 从列表中间移除一个元素。首先需要迭代列表，直到到达要找的位置。current变量所引用的就是要移除的元素。那么要移除它，我们可以通过更新previous.next和current.next.prev的引用，在列表中跳过它。因此，previous.next将指向current.next，而current.next.prev将指向previous。

3.6 isEmpty()：判断链表是否为空，是返回true，否返回false

isEmpty(){
    if (this.length === 0) {
        return true;
    } else {
        return false;
    }
}

3.7 size()：返回链表包含的元素个数

size(){
    return this.length
}

3.8 nextPrint():顺序遍历打印该链表

nextPrint() {
    var current = this.head;
    while (current != null) {
        console.log(current.value);
        current = current.next;
    }
}

3.9 prevPrint():逆序遍历打印该链表

prevPrint() {
    var current = this.tail;
    while (current != null) {
        console.log(current.value);
        current = current.prev;
    }
}
4. 完整代码

完整代码请戳☞☞☞DoublyLinkedList

标签：#链表#新元素#指针变量#js#指针 | 浏览：201 | 发布日期：

免责声明：文章转载自《原生JS实现双向链表》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇基本模运算Spark在美团的实践下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

内存池技术的原理与实现

6.1 自定义内存池性能优化的原理  如前所述，读者已经了解到"堆"和"栈"的区别。而在编程实践中，不可避免地要大量用到堆上的内存。例如在程序中维护一个链表的数据结构时，每次新增或者删除一个链表的节点，都需要从内存堆上分配或者释放一定的内存；在维护一个动态数组时，如果动态数组的大小不能满足程序需要时，也要在内存堆上分配新的内存空间。 6.1.1 默认内存管...

使用插件bootstrap-table实现表格记录的查询、分页、排序等处理

在业务系统开发中，对表格记录的查询、分页、排序等处理是非常常见的，在Web开发中，可以采用很多功能强大的插件来满足要求，且能极大的提高开发效率，本随笔介绍这个bootstrap-table是一款非常有名的开源表格插件，在很多项目中广泛的应用。Bootstrap-table插件提供了非常丰富的属性设置，可以实现查询、分页、排序、复选框、设置显示列、Card...

利用js获取图片尺寸与图片大小（高度与宽度)

利用获取图片尺寸与图片大小（高度与宽度)要注意一点的是要等 图片加载完成后才能js 获取图片宽度与高度的，所以要判断在readystate=="complete"的状态下获取大小,如果是利用file上传的话，每次都要点击清除 image=new image(); imgage.width与高度哦。<!doctype html public "-//w...

一步一步实现网站的多语言版本

    网站在开发的过程中需要实现多语言版本，我们暂且认为有英语和汉语两个版本。网站结构包括，UI过程，rest服务，以及相应的js，各个部分我们都要实现多语言，不要求一键切换，但是在部署过程中要能实现多与语言配置。 首先我们出场的是资源文件，C#的项目实现本地化和区域化，我们要用到资源文件。 添加资源文件夹 添加资源文件项 这里文件的命名最好能规范，...

前端-Vue基础1

Vue核心思想：只要改变数据，页面就会发生改变 1.引入vue 1.下载vue.js 2.在script标签的src属性中，引入vue.js <script src="js/vue.js"></script> 2.vue实例 el：vue接管的div元素，注：只能接管一个div，所有需要vue处理的，必须写在这个div中 data...

vue-i18n web 前端国际化

vue-i18n是一个针对于vue的国际化插件，使用非常简单 1. 下载包 npm install vue-i18n  2、创建中、英文包文件 创建两个文件，一个为zh.js代表中文，en.js代表英文，具体内容格式如下 zh.js文件　　　　　　　　　　　　　　　　　　　　　en.js文件     3、配置main.js // 引入插件和语言包 imp...

最新文章

随机推荐

思享工具箱导航