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)
}


相关文章
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
82 29
|
18天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
77 25
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
271 11
架构学习:7种负载均衡算法策略
深度剖析:共享文件怎么设置密码和权限的 Node.js 进阶算法
在数字化时代,共享文件的安全性至关重要。本文聚焦Node.js环境,介绍如何通过JavaScript对象字面量构建数据结构管理文件安全信息,包括使用`bcryptjs`库加密密码和权限校验算法,确保高效且安全的文件共享。通过实例代码展示加密与权限验证过程,帮助各行业实现严格的信息资产管理与协作。
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
52 9
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
43 5
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
53 7
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
35 3
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表

热门文章

最新文章