用於尋找鍊錶長度的 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)。

以上是用於尋找鍊錶長度的 JavaScript 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章！