《Javascript数据结构和算法》笔记-「链表」

gclove 发布于2019-08-26 13:22 / 2783人阅读

摘要：链表数据结构与算法第五章链表数据结构链表不同与数组数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。

JavaScript-链表

《Javascript数据结构与算法》第五章

5.1 链表数据结构

链表不同与数组

数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。

链表插入或者移动一个元素时很高效，因为并不需要移动其他的元素位置。

链表存储元素的方式，在内存中不是有顺序的，每一个元素由

1.存储元素本身的节点

2.指向一下元素的指针组成

5.2 创建链表

5.2.0 创建链表的骨架

1.链表需要有一个 Node 类，表示要加入链表的项，它包括 2 个部分，一个是该项的值，和一个只想下一项的指针

2.链表还需要个表示链表长度的属性 length

3.表示第一项的引用 head

4.和一系列增删改查、查询长度的方法

function LinkedList() {
    function Node(element) {
        this.element = element;
        this.next = null;
    }

    this.length = 0;
    this.head = null;

    this.append = function(element) {};
    this.insert = function(position, element) {};
    this.remove = function(position) {};
}

5.2.1 append，向链表尾部添加元素

this.append = function(element) {
    var node = new Node(element); //此时node实例 {element:"111",next:null}

    this.length + 1;

    if (this.head === null) {
        this.head = node;
    } else {
        //插入到最后一项，但是由于没有顺序，所以我们没法直接得到链表的最后一项，只能while循环next为null
        let lastNode = head;
        while (lastNode.next !== null) {
            lastNode = lastNode.next;
        }
        lastNode.next = node;
    }
};

5.2.2 removeAt 从链表中删除元素

思路就是分 2 个情况

如果要删除第 0 项，就把 head 指向 head.next 就行了

如果要删除第 n 项，需要 while 循环找到这当前这个 current 项目，将 current 的前一项的 next，越过 current，指向指向 current 的下一项

这样当前元素被丢弃在计算机内存中，就等着被垃圾回收机制，自己回收了。

this.removeAt = function(position) {
    // 检查是否position参数的边界
    if (position > -1 && position < length) {
        let current = head,
            previous, // 表示position上一项元素
            index = 0;

        if (position === 0) {
            head = current.next;
        } else {
            // 如果index++，一直到index追上position时，那么这个current就是position索引对应的元素了
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 让position对应的元素的，上一项的next，越过要删除的这一项，直接指向下一项元素就好了
            previous.next = current.next;
        }
        length--;
        return current;
    } else {
        return null;
    }
};

5.2.3 insert 在某个位置插入

this.insert = function(position, element) {
    if (position >= 0 && position < length) {
        let node = new Node(element);
        let index = 0;
        let current = head;
        let previous;
        if (position === 0) {
            node.next = current;
            head = node;
        } else {
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    } else {
        return false;
    }
};

5.2.4 toString 打印链表

this.toString = function() {
    let current = head;
    let str = "";
    while (current) {
        str += current.element + (current.next ? " - " : "");
        current = current.next;
    }
    return str;
};

5.2.5 size 获取链表长度

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

双向链表骨架

以上是单向链表的JS实现，实际上链表还有多种不同的类型，比如双向链表、循环链表

双向链表和单向链表的一个区别在于，每一个item，不仅仅包括value和next指针，还包括prev指针

同时双向链表不仅仅保存head，也保存最后一项的引用。

这样的好处是：迭代单向链表时，如果错过了某一项，只能重新迭代，但是双向链表就找到上一项

function DoublyLinkedList(){
    let Node = function(){
        this.element = element;
        this.next = null;
        this.prev = null;  // 指向上一项的指针
    }

    let length = 0;
    let head = null;
    let tail = null;  // 保存最后一项的索引
}

循环链表

循环链表，是指最后一项的指针不是null，而是指向第一个元素的一种链表。

所以循环链表，有可能是单向链表，也可能是双向链表

双向循环链表，最后一项的指针指向head，第一项的指针指向tail

专线服务混合云链表算法链表排序算法算法 c语言链表 javascript学习笔记

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

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

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

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

sutaking 2019-08-26 13:28 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

Jonathan Shieber 2019-08-29 12:33 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

SHERlocked93 2019-08-22 11:04 评论0 收藏0