JS 实现单链表

Souleigh ✨ 等级 375 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 中的柯里化
作为函数式编程语言,JS带来了很多语言上的有趣特性,比如柯里化。 1. 简介 柯里化(Currying),又称部分求值(Partial Evaluation),是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数而且返回结果的新函数的技术。 核心思想是把多参数传入的函数拆成单参数(或部分)函
😎手撕吊打面试官系列面试题
js基础 1. 用js打印一个乘法表 这一题面试官考察的是你关于js的打印相关基础api的熟悉程度,以及基本的数学常识,送分题 console.log( 111 212 224 313 326 339 414 428 4312 4416 515 5210 5315 5420 5525
项目实战之---AES 加密
ajax/index.js import axiosApi from '../js/fetch'; import { baseUrl, headerParams } from '../js/baseUrl'; // import引用AES源码js import CryptoJS from 'cryptojs/cryptojs'; console.lo
web性能优化的15条实用技巧
javascript在浏览器中运行的性能,可以认为是开发者所面临的最严重的可用性问题。这个问题因为javascript的阻塞性而变得复杂,事实上,多数浏览器使用单一进程来处理用户界面和js脚本执行,所以同一时刻只能做一件事。js执行过程耗时越久,浏览器等待响应的时间越长。 加载和执行 1.提高加载性能 1.IE8,FF,3.5,Safari 4和
element-ui Dialog组件的close-on-click-modal属性
element组件库的Dialog对话框默认可以通过点击 modal 关闭 Dialog,即点击空白处弹框可关闭。 单功能设置如下: <eldialog :closeonclickmodal"false" </eldialog 全局修改默认配置,点击空白处不能关闭弹窗: //在组件注册.js文件中 Dialog.props.cl
2. web前端开发分享-css,js进阶篇
2. web前端开发分享css,js进阶篇 一,css进阶篇:   等css哪些事儿看了两三遍之后,需要对看过的知识综合应用,这时候需要大量的实践经验, 简单的想法:把qq首页全屏另存为jpg然后
创建型模式之单例设计模式
什么是单例设计模式? 顾名思义,只有一个实例。 单例模式它主要是确保一个类只有一个实例,并且可以提供一个全局的访问点。 废话少说,直接上干货了 单例模式之饿汉式 所谓饿汉式,顾名思义,“ 它很饿 ”。所以说,它一旦被加载进来,就会直接实例化一个对象。 例如: language class Singleton { private static fin
前端面试题自检 JS CSS 部分
JS类型 JavaScript的简单数据类型Number , String , Boolean , Undefined , Null , Symbol typeof 操作符的返回值 number string boolean undefined object function
js去除字符串
js去除字符串js<DOCTYPE html<html<head <title</title</head<body</body<script type"text/javascript" function delHtmlTag(str){   return str.replace(/<^/g,""); } var s
React - Fiber原理
浏览器渲染 屏幕刷新率(FPS) 浏览器的正常绘制频率是60次/秒,小于这个值时,用户会感觉到卡顿 绘制一次的称为一帧,平均每帧16.6ms 帧 每个帧的开头包括样式计算、布局和绘制 js的执行是单线程,js引擎和页面渲染引擎都占用主线程,GUI渲染和Javascript执行两者是互斥的 如果某个js任务执行时间过长,浏览器会推迟渲染,每
天哪!几行js代码就可以实现拳皇小游戏
前言今天,我们用原生JS实现一个拳皇人物位置控制的小效果。话不多说,我们赶紧来看下如何实现吧!效果(非静止八神)分别按W、S、A、D键可实现位置移动,并且效果真实。源码html与css很简单,主要是js中有几点需要注意的。<!DOCTYPE html <html lang"en" <head  <meta charset"UTF8"  <title游
一次搞懂-JavaScript之异步编程
前言异步,就是非同步....这节内容可能会有点枯燥,但是却是 JavaScript 中非常重要的概念,非常有必要去学习。 目的 提升开发效率,编写易维护的代码 引子问题 请求时候为什么页面卡死??js$.ajax( url: "www.xx.com/api", async: false, // true success: function(result
前端开发进化之路
初级程序员仅能完成简单模块和项目的开发工作,难以胜任复杂模块的开发。通常是入行不久, 1 年及以下工作经验的同学。 能力要求1. 熟悉前端基础知识如 HTML、JS、CSS 。 2. 能够使用一门 MVVM 框架进行简单的业务开发。 3. 遇到复杂的组件和模块,会找现有的轮子使用。 4. 会使用百度、google 等检索工具搜索问题
前端 - 常见的异常捕获方法
前端异常捕获在ES3之前js代码执行的过程中,一旦出现错误,整个js代码都会停止执行,这样就显的代码非常的不健壮。从ES3开始,js也提供了类似的异常处理机制,从而让js代码变的更健壮,程序执行的过程中出现了异常,也可以让程序具有了一部分的异常恢复能力。js异常的特点是,出现不会导致JS引擎崩溃,最多只会终止当前执行的任务。回归正题,我们该如何在程序异常发生