• 技术文章 >web前端 >前端问答

    javascript中有链表吗

    长期闲置长期闲置2022-06-15 16:05:51原创210

    JavaScript中没有链表;链表是指多个元素组成的列表,元素存储不连续而是用next指针连接在一起,因此链表增删非首尾元素时不需要移动元素,只需要更改next的指向即可,在JavaScript中可以利用Object来模拟链表。

    本教程操作环境:windows10系统、javascript1.8.5版、Dell G3电脑。

    javascript中有链表吗

    javascript中没有链表

    什么是链表?

    04.png

    链表是多个元素组成的列表

    元素存储不连续,用next指针连接到一起

    JS中没有链表,但是可以用Object模拟链表

    常用操作

    新增节点 append

    删除节点 remove

    插入节点 insert

    获取索引 indexOf

    链表转字符串 toString

    获取链表长度 size

    判断链表是否为空 isEmpty

    数组 VS 链表

    数组: 增删非首尾元素时往往需要移动元素

    链表:增删非首尾元素,不许要移动元素,只需要更改next的指向即可。

    示例如下:

    JavaScript没有直接的链表实现,以下是自己对链表的简单实现

    function LinkedList(){
        var Node = function(element){
            this.element = element;
            this.next = null;
        }
        var head = null;
        var length = 0;
        // 定义append方法
        this.append = function(element){
            var node = new Node(element),
            current;
            // 当head为空时,就将新增的node作为head
            if(head === null){
                head = node
            }else{
                // 当head不为空时,将head赋值为当前值,通过判断当前值的next值是否存在遍历整个链表
                current = head;
                while(current.next){
                    current = current.next;
                }
                // 遍历到链表的最后一项时,设置最后一项的next为新增的内容
                current.next = node
            }
            // 每新增一项,length都加1操作
            length++;
        }
        // 定义toString方法
        this.toString = function(){
            var string = '',
            current = head;
            // 最初将当前值定位到头部,当current存在时,将current的值添加到需要返回的string中,之后将current取为链表下一个值
            while(current){
                string += current.element + ( current.next ? ',' : '');
                current = current.next
            }
            // 遍历完整个链表之后返回string
            return string;
        }
        this.removeAt = function(position){
            // 当指定的位置没有在链表的长度范围内时直接返回null
            if(position > -1 && position < length){
                var current = head,
                index = 0,
                previous;
                // 指定为值是第一个时就将head移到下一个位置
                if(position === 0){
                    head = current.next
                }else{
                    // 通过遍历的方式将current移动到指定位置,使用index记录移动的距离
                    while(index < position){
                        previous = current;
                        current = current.next;
                        index++;
                    }
                    // 删除是通过将指定位置的上一个节点的next指向指定位置的下一个节点
                    previous.next = current.next
                }
                // 一旦删除成功需要将长度减一并返回删除的值
                length--;
                return current.element;
            }
            return null;
        }
        // 实现插入功能
        this.insert = function(position,element){
            // 插入的位置不在链表范围内时返回false
            if(position > -1 && position <= length){
                var current = head,
                index = 0,
                node = new Node(element),
                previous;
                // 插入内容在头部时将插入的node的next指定为current,current此时为head,然后将head指定为插入的node
                if(position === 0){
                    node.next = current;
                    head = node;
                }else{
                    // 通过遍历的方式将指针指定到插入的位置,index记录当前移动的位置
                    while(index < position){
                        previous = current;
                        current = current.next
                        index++
                    }
                    // 插入元素通过将插入位置的上一个元素的next指向插入的节点,并将插入的节点的next指向当前节点
                    previous.next = node;
                    node.next = current;
                }
                // 插入成功之后length加1
                length++;
                return true;
            }
            return false
        }
        // 实现查找指定element的index的功能
        this.indexOf = function(element){
            var index = 0,
            current = head;
            // 通过遍历的方式寻找指定元素所在的位置.
            // 当前节点存在时,判断当前节点的element是否为需要寻找的element,如果是就返回此时的index,如果不是就继续向下遍历节点
            // 当存在两个相同内容时只会返回第一个index
            while(current){
                if(current.element === element){
                    return index;
                }
                current = current.next;
                index++;
            }
            return -1;
        }
    }

    实现之后进行如下调用:

    var linkedList = new LinkedList();
    linkedList.append(15);
    linkedList.append(10);
    linkedList.insert(1,2) // true
    linkedList.insert(2,2) // true
    linkedList.toString() // "15,2,2,10"
    linkedList.removeAt(3) // 10
    linkedList.toString() // "15,2,2"
    linkedList.indexOf(2) // 1

    【相关推荐:javascript视频教程web前端

    以上就是javascript中有链表吗的详细内容,更多请关注php中文网其它相关文章!

    声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
    专题推荐:javascript
    上一篇:javascript支持求余数的方法吗 下一篇:javascript有多线程吗
    20期PHP线上班

    相关文章推荐

    • 【活动】充值PHP中文网VIP即送云服务器• 一文掌握JavaScript数字类型• JavaScript的Symbol类型、隐藏属性及全局注册表详解• JavaScript总结之18种常用数组方法• JavaScript类数组和可迭代对象的实现原理详解• 简单了解JavaScript数据结构与算法之栈
    1/1

    PHP中文网