专栏首页OECOMJavaScript实现单向链表数据结构

JavaScript实现单向链表数据结构

学习过数据结构的人都应该清楚,链表是一种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩容。链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个链表的结构:

相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

在我们现实生活中类似于链表这种数据结构的有很多,比如手表的表链,坦克的履带,火车等。想在其中插入一节需要先断开两节之间的联系,插入之后,将新插入的和之前的两个节点分别在联系起来。

创建一个链表

在原生的js中没有链表这么一个存储结构,需要我们来进行手动创建,下面我们来创建一下链表的基本骨架:

function LinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
    }
    var length = 0;
    var head = null;
}

在骨架中,我们需要一个Node类来作为基础节点,每一个节点都是通过new Node来实现的,length用来存储整个链表的长度,head指向链表的头。

然后我们需要实现以下链表的基本功能:

  • append(element):向列表尾部添加一个新的项
  • insert(position, element):向列表的特定位置插入一个新的项,返回最终插入的位置
  • remove(element):从列表中移除一项,移除成功返回true,如果链表中没有该元素则返回false
  • indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1
  • removeAt(position):从列表的特定位置移除一项
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false
  • size():返回链表包含的元素个数。与数组的length属性类似
  • toString():由于列表项使用了Node类,就需要重写继承自JavaScript对象默认的toString方法,让其只输出元素的值

append方法

append方法实现的是向链表的末尾添加一个元素,如果链表长度为0,则直接首元素就是该添加的元素,具体实现方式如下:

this.append = function(element){
    var node = new Node(element);
    var current = null;
    if(head==null){
        //此时链接长度为空,直接插入为首元素
        head = node;
    }else{
        current = head;
        while(current.next!=null){
            //遍历查找链表,直到找到最后一个元素
            current = current.next;
        }
        current.next = node;
    }
    //更新链表长度
    length++;
}

添加时首先要判断的是链表长度是否为空,也就是head首元素是否为null,也可以判断length是否为0。我们创建的Node类中next始终null,代表的是新创建的元素为末尾元素,其next为null,如果next不为空,则说明该值不是末尾元素,这为添加末尾元素时提供了判断依据。

insert方法

向列表的特定位置插入一个新的项,返回最终插入的位置,我们来看一下实现代码:

this.insert = function(position,element){
    try{
        position = parseInt(position);
        if(isNaN(position)||position>length){
            //position为非数字或者长度大于链表长度,则position位置为末尾插入
            position = length;
        }else if(position<0){
            //如果小于0,则默认插入链表顶部
            position = 0;
        }
        var node = new Node(element);
        var current = head,index = 0,previous = null;
        if(position==0){
            node.next = current;
            head = node;
        }else{
            while(index++<position){
                previous = current;
                current = previous.next;
            }
            node.next = current;
            previous.next = node;

        }
        length++;
        return position;
    }catch(e){
        console.log(e)
    }

}

插入方法需要检测判断一下这个position是否合法,如果是非数字或者数值大于链表长度,则默认添加到链表的尾部,如果数值小于0,则默认添加到链表的头部,然后则是创建一个节点,之后遍历链表,查找到其合适位置进行插入,最后更新链表长度,并将插入位置返回。

实现效果如图所示:

?

removeAt方法

从链表中特定位置移除元素和插入元素一样都需要判断position是否合法,但是该方法不能默认值,只要不合法就不能进行删除操作,以防误删数据,不存在的位置直接返回false,否则返回true,具体实现代码如下:

this.removeAt(position){
    try{
        position = parseInt(position);
        if(isNaN(position)||position>length||position<0){
            return false
        }
        var current = head,index = 0,previous = null;
        if(length==0){
            return false;
        }else if(position==0){
            head = current.next;
        }else{
            while(index++<position){
                previous = current;
                current = previous.next;
            }
            previous.next = current.next;
        }
        length--;
        return true;
    }catch(e){
        console.log(e);
        return false;
    }
}

indexOf方法

indexOf方法返回元素在列表中的索引,如果列表中没有该元素则返回-1。传入的参数是元素本身,我们需要对元素本身进行查找匹配,这里的元素有可能存储的是基本数据类型,也有可能是引用数据类型,这里我们需要进行区分。我们来看一下实现代码:

this.indexOf = function(element){
    var current = head;
    var index = -1;

    while(current){
        index++;
        if(current.element instanceof Object&& JSON.stringify(current.element)==JSON.stringify(element)){
            return index
        }else if(!(current.element instanceof Object)&&current.element==element){
            return index;
        }
        current = current.next;
    }

    return index;
}

remove方法

remove方法就很简单了,我们可以借助上面的indexOf和removeAt方法来进行实现,首先通过indexOf来获取元素位置,然后通过removeAt方法来进行删除操作,下面来看示例代码:

this.remove = function(element){
    var index = this.indexOf(element);
    if(index = -1){
        return false;
    }
    return this.removeAt(index);
}

isEmpty方法

这个方法很容易实现了,只需要判断他的length即可:

this.isEmpyt = function(){
    return length==0
}

size方法

这个方法和上面那个判断类似,只需要将length返回即可:

this.size = function(){
    return length;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 什么是BFC

    BFC 就是块级格式上下文,是页面盒模型布局中的一种 CSS 渲染模式,相当于一个独立的容器,里面的元素和外部的元素相互不影响。那么首先先来说一下常见的三种控制...

    无邪Z
  • jquery中load的用法

    调用load方法的完整格式是:load( url, [data], [callback] ),其中

    无邪Z
  • js点击按钮返回页面顶部

    在进行官网一类的网站建设时,经常会出现页面太长的现象,当用户滚动滚动条到最底部时返回顶部需要滚动多下滚动条,用户体验相当不好,于是就出现了当滚动条滚动到一定位置...

    无邪Z
  • NLP预训练模型大集合

    词语和句子嵌入已经成为任何基于深度学习的自然语言处理系统的必备组成部分。它们将词语和句子编码成稠密的定长向量,从而大大地提升神经网络处理文本数据的能力。近日,S...

    昱良
  • 自然语言处理基石 Embedding 最新进展汇总

    词嵌入(word embeddings)和句嵌入(sentence embeddings)已经成为任何基于深度学习的自然语言处理系统不可或缺的部分。

    崔庆才
  • 深度 | 万物向量化:用协作学习的方法生成更广泛的实体向量

    选自blog.insightdatascience 作者:Javed Qadrud-Din 机器之心编译 参与:Edison Ke、刘晓坤 来自 Insight...

    机器之心
  • CVPR2020 | 人脸识别基于通用表示学习

    认识wild faces是非常困难的,因为他们出现了各种各样的变化。传统的方法要么训练来自目标域的特定注释的变异数据,要么引入未标记的目标变异数据来适应训练数...

    计算机视觉研究院
  • 文本嵌入的经典模型与最新进展(下载PDF)

    昱良
  • Jeff Dean强推:可视化Bert网络,发掘其中的语言、语法树与几何学

    这篇文章是为了补充解释论文,大致呈现了主要的结论。请参阅论文以获得完整的参考文献和更多信息

    代码医生工作室
  • 让应用程序与您形影相随-PortableApps.com

    作为一名 IT 专业人员,您可能会经常需要从一台计算机移到另一台计算机。当您这样做时,您可能会希望能拥有一组随时可用的标准应用程序、工具和文档。满足这些需求的一...

    张善友

扫码关注云+社区

领取腾讯云代金券