资讯专栏INFORMATION COLUMN

JavaScript的数据结构与算法(三) —— 单向链表

李涛 / 1775人阅读

摘要:链表链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。相对于传统的数组,链表的一个好处在于,添加或者删除元素的时候不需要移动其他元素。

链表

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本事的节点和一个指向下一个元素的引用组成。相对于传统的数组,链表的一个好处在于,添加或者删除元素的时候不需要移动其他元素。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度),链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

数组和链表的一个不同在于数组可以直接访问任何位置的元素,而想要访问链表中的一个元素,需要从起点开始迭代列表。

链表又包括:单向链表 和 双向链表;

单向链表

链表中最简单的形式就是单向链表,链表中的节点都包含两个部分,第一部分储存着自身信息,第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL,如图所示:

让我们来简单实现一个单向链表类,并包含如下功能:

append(element): 添加元素到链表尾部

insert(position,element): 向单向链表中某个位置插入元素

indexOf(element): 寻找某个元素在单向链表中的位置

remove(element): 移除给定的元素

removeAt(position): 移除单向链表中某个位置的元素

getHead(): 获取单向链表的头部

isEmpty(): 检查单向链表是否为空,为空则返回true

toString(): 将链表所有内容以字符串输出

size(): 返回单向链表长度

代码如下:

 function LinkedList() {
    /**
     * 单向链表节点的构造函数
     * 
     * @param {any} element 要传入链表的节点
     */
    var Node = function (element) {
        this.element = element;
        this.next = null;
    }
    // 单向链表的长度
    var length = 0;
    // 单向链表的头节点,初始化为null
    var head = null;


    /**
     * 添加元素到链表尾部
     * 
     * @param {any} element 要传入链表的节点
     */
    this.append = function(element) {
        var node = new Node(element),
            current;

        if (head === null) {
            head = node
        } else {
            current = head;
            // 当next为null时,退出循环
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        length++;
    }

    /**
     * 向单向链表中某个位置插入元素
     * 
     * @param {any} position 位置
     * @param {any} element 要传入链表的节点
     */
    this.insert = function (position, element) {
        var node = new Node(element),
            current = head,
            previous,
            index;
        // 验证边界
        if (position < 0 || position >= length) {
            return false;
        }
        // 在链表头部插入
        if (position === 0) {
            node.next = current;
            head = node;
        } else {
            // 在链表除头部之外的地方插入(中间 or 末尾)
            while (index++ < position) {
                previous = current
                current = current.next
            }
            // 在前一个节点和当前节点中间插入
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    }

    
    /**
     * 寻找某个元素在单向链表中的位置
     * 
     * @param {any} element 要寻找的节点
     * @returns {Number} 返回值>=0则代表找到相应位置
     */
    this.indexOf = function (element) {
        var index = 0,
            current = head;

        while (current) {
            if (element === current.element) {
                return index
            }
            index++;
            current = current.next;
        }
        // 如果链表中不存该元素,返回-1
        return -1;
    }

    /**
     * 移除单向链表中某个位置的元素
     * 
     * @param {any} position 要移除的位置
     */
    this.removeAt = function (position) {
        var index = 0,
            previous,
            current = head;
        if (position < 0 || position >= length) {
            return null;
        }

        if (position === 0) {
            head = head.next;
        } else {
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        length--;
        return current.element;
    }

    /**
     * 移除给定的元素
     * 
     * @param {any} element 要移除的节点
     * @returns 
     */
    this.remove = function (element) {
        var index = this.indexOf(element);
        return this.removeAt(index)
    }

    /**
     * 获取单向链表的头部
     * 
     */
    this.getHead = function () {
        return head.element
    }

    /**
     * 检查单向链表是否为空
     * 
     * @returns 为空则返回true
     */
    this.isEmpty = function () {
        return length === 0
    }
    
    /**
     * 返回单向链表长度
     * 
     * @returns {Number}
     */
    this.size = function () {
        return length;
    }

    /**
     *  将链表所有内容以字符串输出
     * 
     * @returns {String}
     */
    this.toString = function () {
        var str = "",
            current = head;
        while(current) {
            str += current.element;
            current = current.next;
        }
        return str;
    }
}

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

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

相关文章

  • 学习JavaScript数据结构算法(二):链表

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

    lolomaco 评论0 收藏0
  • 学习数据结构算法链表

    摘要:本系列所有文章第一篇文章学习数据结构与算法之栈与队列第二篇文章学习数据结构与算法之链表第三篇文章学习数据结构与算法之集合第四篇文章学习数据结构与算法之字典和散列表第五篇文章学习数据结构与算法之二叉搜索树简单介绍链表链表一种常见的数据结构,可 本系列所有文章:第一篇文章:学习数据结构与算法之栈与队列第二篇文章:学习数据结构与算法之链表第三篇文章:学习数据结构与算法之集合第四篇文章:学习数...

    jerryloveemily 评论0 收藏0
  • javascript数据结构算法(一)单向链表双向链表

    摘要:创建双向链表创建节点继承添加前继指针初始化双向链表对链表最后一个元素进行引用插入操作尾插法任意位置添加元素删除操作删除特定位置的元素查询操作查询元素的位置查询尾部元素修改操作清空双向链表双向链表对象转为字符串 线性表 (List):零个或者多个数据元素的有限序列。线性表是一个序列,具有一对一的关系,而不能具备一对多的关系。线性表要求有限性,数据类型也要相同。本文参考的主要是大话数据结构...

    William_Sang 评论0 收藏0
  • Javascript数据结构算法》笔记-「链表

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

    gclove 评论0 收藏0
  • JavaScript数据结构算法(四) —— 双向链表

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

    Youngdze 评论0 收藏0

发表评论

0条评论

李涛

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<