《JavaScript数据结构与算法》笔记——第5章链表

sutaking 发布于2019-08-26 13:28 / 2086人阅读

摘要：链表存储有序的元素集合，不同于数组，链表中的元素在内存中并不是连续放置，每个元素有一个存取元素本身的节点和一个指向下一个元素的引用组成。优点添加或者移除元素的时候不需要移动其他元素。

链表存储有序的元素集合，不同于数组，链表中的元素在内存中并不是连续放置，每个元素有一个存取元素本身的节点和一个指向下一个元素的引用组成。

优点：添加或者移除元素的时候不需要移动其他元素。只需要找到加入的节点，断开并插入一个元素（修改引用）

function LinkedList() {
    let Node = function (element) {// 辅助类，包含一个element属性即具体的值，以及一个next属性即指向下一个节点的引用
        this.element = element;
        this.next = null;
    };
    let length = 0;
    let head = null;
    /**
     * 向列表尾部添加一个新的项
     * @param element
     */
    this.append = function (element) {
        let node = new Node(element), current;
        if (head === null) {
            head = node;
        } else {
            current = head;
            // 循环列表找到最后一项
            while (current.next) {
                current = current.next
            }
            // 将最后一项的引用指向新元素（将最后一项的next指向node，建立新连接）
            current.next = node;
        }
        length++;// 更新列表的长度
    };
    /**
     * 向列表的特定位置插入一个新的项
     * @param position
     * @param element
     */
    this.insert = function (position, element) {
        if (position > -1 && position < length) {
            let node = new Node(element);
            let current = head, previous, index = 0;
            if (position === 0) {
                head = node;
                node.next = current
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next
                }
                previous.next = node;
                node.next = current
            }
            length++;
            return true
        } else {
            return false
        }
    };
    /**
     * 从列表的特定位置移出一项
     * @param position
     */
    this.removeAt = function (position) {
        // 检查越界值
        if (position > -1 && position < length) {// 验证该位置是否有效
            // current是对要移出元素的引用
            // previous是对要移出的元素前一个元素的引用
            let current = head, index = 0, previous;
            // 移出第一项
            if (position === 0) {
                head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next
                }
                // 将previous与current的下一项链接起来：这样跳过current，从而实现移出，垃圾收集
                previous.next = current.next
            }
            length--;
            return current.element
        } else {
            return null
        }
    };
    /**
     * 从列表移出一项
     * @param element
     */
    this.remove = function (element) {
        
    };
    /**
     * 返回元素在列表中的索引
     * @param element
     */
    this.indexOf = function (element) {
        let current = head, index = 0;
        while(current){
            if(element === current.element){// 判定条件需要优化，对于应用类型要判定值相等
                return index;
            }
            index++;
            current = current.next
        }
        return -1
    };
    this.isEmpty = function () {
    };
    this.size = function () {
    };
    this.getHead = function () {
    };
    /**
     * 由于使用Node辅助类，所以要重写继承自默认对象的toString方法
     */
    this.toString = function () {
        let current = head, string = "";
        while (current) {
            string += current.element + (current.next ? "n" : "");
            current = current.next
        }
        return string
    };
    this.print = function () {
    }
}

双向链表

循环链表

云服务器 GPU云服务器 js数据结构与算法第2 js数据结构与算法+第2 明解c语言第9章 javascript入门经典第5版

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/108866.html

《JavaScript数据结构与算法》笔记——第7章字典和散列表

摘要：在字典中，存储的是键，值，集合可以看作值，值的形式存储元素，字典也称为映射方法描述备注向字典中添加新元素通过某个键值从字典中移除对应的数据值判断某个键值是存在于这个字典中通过键值获取对应的数据值返回字典所有元素的数量删除字典中所有元素将字典在字典中，存储的是[键，值]，集合可以看作[值，值]的形式存储元素，字典也称为映射方法描述备注 set(key,...

zorro 2019-08-26 13:28 评论0 收藏0
重读《学习JavaScript数据结构与算法-第三版》- 第6章链表（一）

摘要：前言本章为重读学习数据结构与算法的系列文章，该章节主要讲述数据结构链表，以及实现链表的过程和原理。链表，是存储有序的元素集合。链表中的元素在内存中并不是连续放置的，每个元素由一个存储自身的元素节点和一个指向下一个元素的引用指针或链接组成。定场诗伤情最是晚凉天，憔悴厮人不堪言；邀酒摧肠三杯醉.寻香惊梦五更寒。钗头凤斜卿有泪，荼蘼花了我无缘；小楼寂寞新雨月.也难如钩也难圆。前言...

lmxdawn 2019-08-26 11:00 评论0 收藏0
《Javascript数据结构和算法》笔记-「链表」

摘要：链表数据结构与算法第五章链表数据结构链表不同与数组数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。 JavaScript-链表《Javascript数据结构与算法》第五章 5.1 链表数据结构链表不同与数组数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。链表插入或者移动一个元素时很高效，因为并不需要移动其他的元素位置。链表存储元素的方式...

gclove 2019-08-26 13:22 评论0 收藏0
《算法》第一章学习笔记js实现

摘要：算法第一章学习笔记实现更多内容目标总结本书主要内容，相应算法使用来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限确定有效的并适合用计算机程序来实现的解决问题的方法。《算法》第一章学习笔记js实现更多内容目标：总结本书主要内容，相应算法使用js来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们关注的大多...

baishancloud 2019-08-30 13:45 评论0 收藏0
《算法》第一章学习笔记js实现

摘要：算法第一章学习笔记实现更多内容目标总结本书主要内容，相应算法使用来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限确定有效的并适合用计算机程序来实现的解决问题的方法。《算法》第一章学习笔记js实现更多内容目标：总结本书主要内容，相应算法使用js来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们关注的大多...

K_B_Z 2019-08-21 17:05 评论0 收藏0