JavaScript数据结构与算法——链表

chunquedong 发布于2019-08-23 15:14 / 2075人阅读

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

1.链表数据结构

链表存储有序的元素集合，但不同于数组，链表中的元素咋内存中并不是连续放置的每个元素有一个存储元素本身的节点和一个指向下一个元素的引用组成。下图展示了一个链表的结构：

链表的优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

2.创建链表

function LinkedList() {
    // 创建一个node类，表示将要加入的项 element表示要添加的值，next指向列表中下一个节点项的指针
    let Node = function(element) {
        this.element = element;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // 下面声明链表的方法
    // 1.向列表尾部添加一个新的项
    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++;
    }
    // 2.从列表中移除元素
    this.removeAt = function(position) {
        // 检查position是否超出链表范围
        if(position > -1 && position < length) {
            let current = head,
                previous,
                index = 0;
            // 移除第一个元素
            if(position === 0 ) {
                head = current.next;
            } else {
                // 循环到指定位置，找到该位置的 previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 将previous与current的下一项链接起来：跳过current
                previous.next = current.next;
            }    
            // 链表长度减一
            length--;
            // 返回被删除项
            return current.element;
        } else {
            // 不是有效位置，返回null
            return null
        }
    }
     // 3.在任意位置插入元素
    this.insert = function(element, position) {
        //判断是否超过链表范围
        if (position >= 0 && position<= length) {
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            // 在首位插入元素
            if (position === 0 ) {
                node.next = current;
                head = node;
            } else{
                // x循环到position应该添加的位置，取出previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 在previous和current间插入
                node.next = current;
                previous.next = node;
            };    
            // 更新链表长度
            length++;
            return true;
        } else{
            return false;
        };
    }
    //4. 把LinkedList对象转化成字符串
    this.toString = function() {
        let current = head,
            string = "";
        while(current) {
            string += current.element + (current.next ? "n" : "");
            current = current.next;
        }  
        return string;  
    }
    //5.链表中是否存在某个值
    this.indexOf = function(element) {
        let current = head,
            index = 0;
        while(current) {
            if(element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }  
        return -1; 
    } 
    //6.通过element实现remove元素
    this.remove = function(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
    //7.isEmpty size getHead方法
    this.isEmpty = function() {
        return length === 0; 
    }
    this.size = function() {
        return length;
    }
    this.getHead = function() {
        return head;
    }    
}

云服务器 GPU云服务器链表算法链表排序算法算法 c语言链表算法与数据结构

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

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

学习JavaScript数据结构与算法（二）：链表

摘要：实现移除给定的元素要移除的元素返回值表示移除成功方法说明移除单向链表中某个位置的元素。的前端乐园原文链接寒假前端学习学习数据结构与算法二链表本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第四篇文章：学习JavaScript数据结构与...

lolomaco 2019-08-22 11:00 评论0 收藏0
JavaScript的数据结构与算法（四） —— 双向链表

摘要：链表链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。链表又包括单向链表和双向链表双向链表双向链表与单向链表很是相像。但在双向链表中，还有指向上一个节点的链接，是双向的。链表链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本事的节点和一个指向下一个元素的引用组成。相对于传统的数组，链表的一个好处在于，添加或...

Youngdze 2019-08-21 17:13 评论0 收藏0
《Javascript数据结构和算法》笔记-「链表」

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

gclove 2019-08-26 13:22 评论0 收藏0
Javascript数据结构与算法（二）循环链表与有序链表

摘要：循环链表可以像单向链表引用，也可以像双向链表有双向引用。以下就以如何创建栈数据结构为例。循环链表可以像单向链表引用，也可以像双向链表有双向引用。性能上也跟双向链表差不多，如果position大于length/2，那就可以从尾部开始迭代，可以减少迭代的元素。唯一的区别在于最后一个元素指向下一个元素的指针(tail.next)不是undefine，而是第一个元素（head）。接下来来看一...

YacaToy 2019-08-26 10:49 评论0 收藏0
JavaScript的数据结构与算法（三） —— 单向链表

摘要：链表链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。相对于传统的数组，链表的一个好处在于，添加或者删除元素的时候不需要移动其他元素。链表链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本事的节点和一个指向下一个元素的引用组成。相对于传统的数组，链表的一个好处在于，添加或者删除元素的时候不需要移动其他元素。...

李涛 2019-08-21 17:14 评论0 收藏0