用於尋找鍊錶長度的 JavaScript 程式-js教程-PHP中文網

用於尋找鍊錶長度的 JavaScript 程式

WBOY

發布： 2023-08-26 20:01:16

轉載

1264 人瀏覽過

用于查找链表长度的 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))

登入後複製