数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找链表长度的 JavaScript 程序
链表是一种线性数据结构，可以是可变长度的，并且链表的长度可以更改，这是数组中无法更改数组长度的问题。在本文中，我们将通过实现代码并遍历边缘情况来查找给定链表的长度。我们将在本文中使用 while 循环和类概念。
问题简介
在给定的问题中，我们得到一个链表，首先，我们必须使用类创建链表，然后我们必须找到给定链表的长度。由于链表的长度可以更改，因此我们将在代码的特定点找到链表的长度。
我们将使用两种方法，首先是使用 while 循环的直接迭代方法，另一种是递归方法来查找给定链表的长度。
迭代方法
在这种方法中，我们将首先使用类创建一个链表，为链表提供结构。我们将定义一些函数，例如 push 函数，通过简单地传递头部和数据来将值添加到链表中。
示例
在此过程中，我们将使用 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)，因为栈的大小。
310 次查看
