JS 实现单链表

Souleigh ✨ 等级 719 0 0
标签: 链表前端

要存储多个元素,数组(或列表)可能是最常用的数据结构。但这种数据结构有一个缺点:(在大多数语言中)数据的大小是固定的,从数组的起点或中间插入或移除项的成本很高。   链表存储有序的集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。   相对于传统的数组,链表的一个好处是,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。   举个例子,我们玩寻宝游戏,你有一条线索,这条线索是指向寻找下一条线索的地点的指针。你沿着这条链接去下一个地点,得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法,就是从起点(第一条线索)顺着列表去寻找。   让我们用JS实现最简单的单链表:

function LinkedList() {

    // Node辅助类,表示要加入列表的项,element是即将添加到列表的值,next是指向列表中下一个节点项的指针
    let Node = function (element) {
        this.element = element
        this.next = null
    }

    let length = 0
    let head = null

    // 向链表尾部追加元素
    this.append = function (element) {
        let node = new Node(element)
        let current
        if (head === null) { // 列表中第一个节点
            head = node
        } else {
            current = head
            while (current.next) {
                current = current.next // 找到最后一项,是null
            }
            current.next = node // 给最后一项赋值
        }
        length++ // 更新列表的长度
    }

    // 从链表中移除指定位置元素
    this.removeAt = function (position) {
        if (position > -1 && position < length) { // 值没有越界
            let current = head
            let previous, index = 0
            if (position === 0) { //  移除第一项
                head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next // 将previous与current的下一项连接起来,跳过current,从而移除
            }
            length-- // 更新列表的长度
            return current.element
        } else {
            return null
        }
    }

    // 在链表任意位置插入一个元素
    this.insert = function (position, element) {
        if (position >= 0 && position <= length) { // 检查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0
            if (position === 0) { // 在第一个位置添加
                node.next = current
                head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current // 在previous与current的下一项之间插入node
                previous.next = node
            }
            length++
            return true
        } else {
            return false
        }
    }

    // 把链表内的值转换成一个字符串
    this.toString = function () {
        let current = head,
            string = ''
        while (current) {
            string += current.element + ' '
            current = current.next
        }
        return string
    }

    // 在链表中查找元素并返回索引值
    this.indexOf = function (element) {
        let current = head,
            index = 0
        while (current) {
            if (element === current.element) {
                return index
            }
            index++
            current = current.next
        }
        return -1
    }

    // 从链表中移除指定元素
    this.remove = function (element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.size = function () {
        return length
    }

    this.getHead = function () {
        return head
    }
}
let list = new LinkedList()
list.append(1)
list.append(2)
console.log(list.toString()) // 1 2
list.insert(0, 'hello')
list.insert(1, 'world')
console.log(list.toString()) // hello world 1 2
list.remove(1)
list.remove(2)
console.log(list.toString()) // hello world 

单链表有一个变种 - 循环链表,最后一个元素指向下一个元素的指针,不是引用null,而是指向第一个元素,只需要修改下最后的next指向为head即可。

收藏
评论区

相关推荐

JS 实现单链表
要存储多个元素,数组(或列表)可能是最常用的数据结构。但这种数据结构有一个缺点:(在大多数语言中)数据的大小是固定的,从数组的起点或中间插入或移除项的成本很高。   链表存储有序的集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。   相对于传统的数组,链表的一个好处是
前端面试题自检 JS CSS 部分
JS类型 JavaScript的简单数据类型Number , String , Boolean , Undefined , Null , Symbol typeof 操作符的返回值 number string boolean undefined object function
JQ的简单使用(基础)——————JQ
JQ基础——JQ的简单使用 ------------- <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title></title> <style> .w{} </style> </head>
JS和CSS加载(渲染)机制不同
一、结论 ==== CSS可以在页面加载完成后随时渲染。举个例子:通过js给某个元素加一个id或者css,只要这个id或者css有对应的样式,此元素的样式就会自动生效。 JS不可以在页面加载完成后生效。最明显的例子就是使用EasyUI的时候,iframe中哪些样式无效(EasyUi是依靠JS进行样式处理的,所以无法运行JS,那么样式也就无法设置。简单点说
JS异步的底层原理:单线程加事件队列
**异步的底层原理:单线程+事件队列。** js的代码执行时单线程的,所谓单线程:就是js代码时从上到下按顺序依次执行的,一次只能做一件事情。事件队列可以看作一个容器,这个容器存储着js的回调函数,只有js代码执行结束后,才会去事件队列中调用这些回调函数。 例: 1 //以下的代码先执行for循环,再输出sum值,然后输出正常代码执行,最后
JS的常用属性
JS-------定义:基于事件和对象驱动,并具有安全性能的脚本语言。 引入:<script  type=”text/javascript”>具体js代码</script> <script  type=”text/javascript” src=”js文件”></script> 大小写敏感:例如:A与a是两个不同的东东 注释://  单
JS获取表单元素的值
<html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"> <title>测试</title> </head> <body> <form id="form1" name="form1"> 文本框
Java&Selenium自动化测试调用JS实现单击
Java&Selenium自动化测试调用JS实现单击 ========================== /* * the method of invoking js to do something * * @author davieyang * @create 2018-08-05 1:37 *
1、webpack入门例子。
在下面的例子中,简单使用webpack打包一个js。并且把这个js引用的其他js、json数据一起打包进去。 官网:[http://webpack.github.io/](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fwebpack.github.io%2F) 英文文档:  [http
CryptoJS
CryptoJS ======== 引用: [https://cdnjs.com/libraries/crypto-js](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fcdnjs.com%2Flibraries%2Fcrypto-js) WordArray (An array of
Delphi中Chrome Chromium、Cef3学习笔记(三)
原文   http://blog.csdn.net/xtfnpgy/article/details/46635871 Delphi与JS的交互问题: 一、执行简单的JS 上一篇已经讲过: chrm1.browser.MainFrame.ExecuteJavaScript('alert("abc");','about:blank',0); c
JavaScript学习笔记
JavaScript学习笔记 ============== 和HTML和CSS不一样,它是一门编程语言。 JS简介 ---- JS是一个客户端脚本语言,不需要编译,每一个浏览器都有JS的解析引擎。可以增强用户和HTML页面的交互,使网页产生动态。 JS的生成是在当时网速所限,必须在客户端就完成一些表单的校验等工作以减少客户端和服务器端的通信次数的实际
Javascript 是如何体现继承的 ?
js继承的概念 js里常用的如下两种继承方式: 原型链继承(对象间的继承) 类式继承(构造函数间的继承)   由于js不像java那样是真正面向对象的语言,js是基于对象的,它没有类的概念。所以,要想实现继承,可以用js的原型prototype机制或者用apply和call方法去实现 在面向对象的语言中,我们使用类来创建一个自定义对象
Js表单验证控件
演示地址:[http://weishakeji.net/Utility/Verify/Index.htm](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fweishakeji.net%2FUtility%2FVerify%2FIndex.htm) 开源地址:[https://githu
tensorflowjs 简单使用
原文链接: [tensorflowjs 简单使用](https://my.oschina.net/ahaoboy/blog/2870519) github [https://github.com/tensorflow/tfjs](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fgithu