首页 > web前端 > js教程 > 正文

用于查找链表长度的 JavaScript 程序

WBOY
发布: 2023-08-26 20:01:16
转载
1419人浏览过

用于查找链表长度的 javascript 程序

链表是一种可以变长的线性数据结构,链表的长度是可以改变的,这就是数组中数组长度不能改变的问题。在本文中,我们将通过实现代码并检查边缘情况来找到给定链表的长度。我们将在本文中使用 while 循环和类概念。

问题简介

在给定的问题中,我们得到一个链表,首先,我们必须使用类创建链表,然后我们必须找到给定链表的长度。由于链表的长度是可以改变的,所以我们会在特定的代码点找到链表的长度。

我们将使用两种方法,首先是使用 while 循环的直接迭代方法,另一种是递归方法来查找给定链表的长度。

迭代方法

在此方法中,我们将首先使用类为链表提供结构来创建一个链表。我们将定义一些函数,例如push函数,通过简单地传递头和数据来将值添加到链表中。

立即学习Java免费学习笔记(深入)”;

示例

在此过程中,我们将使用 while 循环、链表的头或起始节点以及一个变量来计算链表中的节点数,即给定链表的长度。

// creating the linked list node
class Node{
   constructor(data)  {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function length(head){
   temp = head;
   var count = 0
   while(temp != null) {
      count++;
      temp = temp.next;
   }
   return count;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))
登录后复制

在上面给出的方法中,我们没有使用任何额外的空间,并且只遍历链表一次。因此,上述方法的时间复杂度为 O(N),其中 N 是链表的大小,上述方法的空间复杂度为 O(1)。

递归方法

在此方法中,我们将遵循与上述方法中创建链表相同的步骤,对于主要任务,我们将使用递归方法。

示例

使用与函数本身不同的参数和特定的基本条件调用相同的函数称为递归。在此方法中,我们将使用链表的头调用该函数,然后从该函数中,我们将再次调用该函数,但参数为当前节点的下一个节点。作为返回值,我们将返回 1 + 递归调用返回值,并且结果将在第一次调用时给出。让我们看看代码 -

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}

function length(cur) {
   if(cur == null) return 0;
   return 1 + length(cur.next);
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))
登录后复制

时间和空间复杂度

递归方法的时间复杂度为 O(N),其中 N 是给定链表中存在的节点数。上面代码的空间复杂度是O(N),因为总共有N次调用,并且对于每次调用,我们都必须维护当前的节点堆栈。

结论

在本教程中,我们学习了如何通过实现代码并研究边缘情况来查找给定链表的长度。我们在第一种方法中使用了本文中的 while 循环和类概念,在第二种方法中使用了递归方法来查找长度。两种方法的时间复杂度均为 O(N),其中 N 是链表的长度,而由于堆栈大小,递归方法的空间复杂度为 O(N)。

以上就是用于查找链表长度的 JavaScript 程序的详细内容,更多请关注php中文网其它相关文章!

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载
来源:tutorialspoint网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号