JS数据结构&算法学习——链表操作及封装

简介: 本文是(JS数据结构&算法学习——链表)的衔接文,涵盖了链表常见的6种方法封装与介绍

链表操作及封装

操作分类

  1. append(item):向链表尾部添加一个新的节点,item为节点数据
  2. insert(position, item):向链表的某个位置插入一个新的节点,position为插入位置,item为节点数据
  3. get(position):获取链表中某个位置的节点,position为位置
  4. indexOf(item):返回节点在链表中的位置索引,若在链表中没有该元素,则返回-1,其中item为要查询的节点数据
  5. update(position,item):修改某个节点的元素,position为某个节点的位置,item为要修改的数据
  6. remove(item):从链表中移除数据item对应的某个节点
  7. remove(position):从链表中移除位置position对应的某个节点
  8. isEmpty():判断链表是否为空,如果链表中不包含任何的节点,则返回true,反之则返回false
  9. size():返回链表所包含的节点个数
  10. toString():将链表转换为字符串形式

append方法

首先还是和之前的封装方式一样,我们先封装一下。

LinkList.prototype.append = function (data) {
    var newNode = new Node(data)
    this.length++
}
复制代码

而在封装append要考虑两种情况,即当链表本身为空的时候,新添加的节点是唯一的,这个时候只需要将头节点的指向改为新节点即可

1.webp.jpg

if (this.head == null) {
    this.head = newNode
}
复制代码

另外一种则是当链表不为空的时候,需要在其他节点后面添加节点,通过while从头节点开始直到current.next也就是节点的指向为空的时候将其指向改为新增节点

1.webp.jpg

else {
    var current = this.head
    while(current.next) {
        current = current.next
    }
    current.next = newNode
}
复制代码

toString方法

toString方法需要我们从第一个节点开始,拿到对应的item来不断拼接字符串

LinkList.prototype.toString = function () {
    var current = this.head
    var result = ""
    while (current) {
        result += current.data
        current = current.next
    }
    return result
}
复制代码

insert方法

insert方法可以将节点插入任意位置上

LinkList.prototype.insert = function (position,data) {
    var newNode = new Node(data)
    this.length++
}
复制代码

我们首先需要对position进行越界判断,判断其传参是否在链表的范围内还有是否合法

if (position < 0 || position > this.length) return false
复制代码

进一步我们可以进行插入的操作,即我们将插入位置的前一个节点的指向转向新节点,将新节点的指向转向位置后的节点,但是需要考虑两种情况,即插入位置是否是第一个。

当插入位置为第一个的时候新节点的指向需要改为当前头节点的指向,之后再将头节点指向新节点

if (position == 0) {
    newNode.next = this.head
    this.head = newNode
}
复制代码

1.webp.jpg

当插入位置不是第一个的时候,我们需要通过头节点向后寻找对应位置的前节点,首先需要将新节点的指向转向插入位置后的节点,再将插入位置前的节点指向改为我们的新节点,如果顺序反过来,那么我们就会找不到插入位置后的节点,造成了丢失的情况。

else {
    var index = 0
    var current = this.head
    var previous
    while (index++ < position) {
        previous = current
        current = current.next
    }
    newNode.next = current
    previous.next = newNode
}
复制代码

1.webp.jpg

get方法

get方法是根据传来的position位置来获取其对应的节点数据

LinkList.prototype.get = function (position) {}
复制代码

当然同样的,传参出现position的时候我们首先需要的就是先判断它是否越界,与之前不同的是将>改为>=

if (position < 0 || position >= this.length) return false
复制代码

get方法还是简单的只需要从头节点向后找对应的position的数据

var current = this.head
var index = 0
while (index < position) {
    current = current.next
    index++
}
return current.data
复制代码

indexOf方法

indexOf方法通过传入的数据来寻找并返回其数据在链表中的索引也就是下标

LinkList.prototype.indexOf = function (data) {
    var index = 0
    var current = this.head
    while (current) {
        if(current.data == data) {
            return index
        }
        current = current.next
        index++
    }
    return -1
}
复制代码

update方法

update通过传进来的位置参数来寻找并使用数据参数修改其值,同样的因为参数中有position,所有我们必须先进行越界判断再进行操作,最后通过直接修改current的data完成修改

LinkList.prototype.update = function (position,data) {
    if (position < 0 || position >= this.length) return false
    var index = 0
    var current = this.head
    while (index++ < position) {
        current = current.next
    }
    current.data = data
    retrun true
}
复制代码

removePo&remove方法

移除方法有两种形式,一种是根据位置去移除,一种是根据数据去移除,我们首先来介绍一下通过位置进行移除的封装,其实移除和插入的逻辑相似,同样也分两种情况,一种是移除第一个,另一种是移除其他位置

当移除位置为第一个的时候则将头节点的指向直接改为头节点的下一个节点

LinkList.prototype.removePo = function (position) {
    if (position < 0 || position >= this.length) return false
    if (position == 0) {
        this.head = this.head.next
    }
    this.length-1
}
复制代码

1.webp.jpg

当position为其他位置的时候则将位置前节点的指向改为位置后的节点,使用两个变量记录位置current的变化,当其满足条件的时候即到达指定位置的时候操作即可

else {
    var index = 0
    var current = this.head
    var previous
    while (index++ < position) {
        previous = current
        current = current.next
    }
    previous.next = cuurent.next
}
复制代码

1.webp.jpg

大家可能疑问那么我删除的节点哪去了?其实大家不用担心移除的节点会占内存,因为浏览器的回收机制会将它及时回收的。

remove方法则是根据传入的数据来进行移除,有了之前的封装我们直接调用indexOf和removePo直接获取,简单粗暴

LinkList.prototype.remove = function (data) {
   var position = this.indexOf(data)
   return this.removePo(position)
}


相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
157 4
|
11天前
|
存储 监控 算法
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
30 9
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
|
25天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
|
17天前
|
监控 算法 JavaScript
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
31 7
|
15天前
|
存储 监控 JavaScript
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
26 3
|
2月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
79 1

热门文章

最新文章