Program JavaScript untuk mencari panjang senarai terpaut

Senarai terpaut ialah struktur data linear yang boleh berubah-ubah panjangnya. Dalam artikel ini, kami akan mencari panjang senarai terpaut yang diberikan dengan melaksanakan kod dan menyemak kes tepi. Kami akan menggunakan gelung while dan konsep kelas dalam artikel ini.

Pengenalan kepada masalah

Dalam masalah yang diberikan, kita diberikan senarai pautan, pertama, kita perlu membuat senarai pautan menggunakan kelas dan kemudian kita perlu mencari panjang senarai pautan yang diberikan. Memandangkan panjang senarai terpaut boleh berubah, kami akan mencari panjang senarai terpaut pada titik kod tertentu.

Kami akan menggunakan dua kaedah, pertama ialah kaedah lelaran terus menggunakan gelung while dan satu lagi kaedah rekursif untuk mencari panjang senarai pautan yang diberikan.

Kaedah berulang

Dalam kaedah ini, kami akan membuat senarai terpaut dahulu menggunakan kelas untuk menyediakan struktur bagi senarai terpaut. Kami akan menentukan beberapa fungsi, seperti fungsi tolak, untuk menambah nilai pada senarai terpaut dengan hanya menghantar pengepala dan data.

Contoh

Dalam proses ini, kami akan menggunakan gelung sementara, kepala atau nod permulaan senarai terpaut dan pembolehubah untuk mengira bilangan nod dalam senarai terpaut, iaitu panjang senarai terpaut yang diberikan.

// 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))

Dalam kaedah yang diberikan di atas, kami tidak menggunakan sebarang ruang tambahan dan melintasi senarai terpaut sekali sahaja. Oleh itu, kerumitan masa bagi kaedah di atas ialah O(N), di mana N ialah saiz senarai terpaut, dan kerumitan ruang bagi kaedah di atas ialah O(1).

Kaedah rekursif

Dalam kaedah ini kita akan mengikut langkah yang sama seperti dalam kaedah di atas untuk membuat senarai pautan, untuk tugas utama kita akan menggunakan kaedah rekursif.

Contoh

Memanggil fungsi yang sama dengan parameter berbeza dan keadaan asas tertentu daripada fungsi itu sendiri dipanggil rekursi. Dalam kaedah ini kita akan memanggil fungsi dengan kepala senarai terpaut dan kemudian dari fungsi itu kita akan memanggil fungsi itu semula tetapi dengan hujah nod seterusnya dari nod semasa. Sebagai nilai pulangan kami akan mengembalikan 1 + nilai pulangan panggilan rekursif dan hasilnya akan diberikan pada panggilan pertama. Mari lihat kod -

// 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))

Kerumitan masa dan ruang

Kerumitan masa kaedah rekursif ialah O(N), dengan N ialah bilangan nod yang terdapat dalam senarai terpaut yang diberikan. Kerumitan ruang kod di atas ialah O(N) kerana terdapat N panggilan secara keseluruhan dan untuk setiap panggilan kita perlu mengekalkan susunan nod semasa.

Kesimpulan

Dalam tutorial ini, kami mempelajari cara mencari panjang senarai terpaut yang diberikan dengan melaksanakan kod dan mengkaji kes tepi. Kami menggunakan gelung while dan konsep kelas daripada artikel ini dalam kaedah pertama dan kaedah rekursif untuk mencari panjang dalam kaedah kedua. Kerumitan masa bagi kedua-dua kaedah ialah O(N), di mana N ialah panjang senarai terpaut, manakala kerumitan ruang kaedah rekursif ialah O(N) disebabkan saiz tindanan.

Atas ialah kandungan terperinci Program JavaScript untuk mencari panjang senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!