資料結構
網路
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 次檢視
