Program JavaScript untuk memasukkan nod ke dalam senarai terpaut

Senarai terpaut ialah struktur data dengan panjang yang berbeza dan sebarang nod boleh dipadamkan atau ditambah pada senarai terpaut. Dalam tutorial ini, kami akan melaksanakan program lengkap untuk memasukkan nod dalam senarai terpaut dengan kerumitan ruang dan masa. Mari kita fahami pernyataan masalah terlebih dahulu.

pengenalan masalah

Dalam soalan yang diberikan, kami diberikan senarai terpaut dan memandangkan kami boleh menukar saiz senarai terpaut dengan menambah atau mengalih keluar nod dalam senarai terpaut, kami akan menambah atau memasukkan nod dalam senarai terpaut.

Dalam senarai terpaut, kami boleh menambah nod baharu di tiga lokasi berbeza: nod hadapan, selepas nod terakhir dan di tengah senarai terpaut. Sebagai contoh, senarai pautan yang diberikan ialah -

1 -> 2 -> 3 -> 4 -> 5 -> null, kita perlu menambah nod rawak dengan nilai 9. Oleh itu, terdapat banyak situasi di mana nod perlu ditambah, seperti -

• Tambah nod pada permulaan - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• Tambah nod di tengah - 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• Tambah nod di hujung - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

Mari lihat cara untuk mencapai tugasan berikut -

Tambah nod pada permulaan senarai terpaut

Contoh

Untuk menambah nod pada permulaan senarai terpaut, kita perlu mencipta nod baharu dan lulus kepala senarai terpaut ke nod baharu sebagai nod seterusnya, kemudian alihkan kepala ke nod baharu dan tambah nod nod baharu ke permulaan senarai terpaut.

// 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 add(data) {
   var new_node = new Node(data);
   new_node.next = head;
   return new_node;
}

var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

head = add(7);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at starting: ")
console.log(data + "null")

Kerumitan masa kod di atas ialah O(1), kerana kita hanya perlu mengalihkan penunjuk, dan tiada ruang tambahan digunakan, menjadikan kerumitan ruang O(1).

Tambahkan nod di tengah-tengah senarai terpaut

Contoh

Untuk menambah nod di tengah senarai terpaut, kita perlu mencipta nod baharu dan lulus nod itu sebelum kita boleh menambah nod baharu senarai terpaut sebagai nod seterusnya nod baharu, yang akan menambah nod nod baharu kepada senarai terpaut di tengah.

// 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 add(data,head) {
   var new_node = new Node(data);
   var temp = head;
   while(temp.value != 3) {
      temp  = temp.next;
   }
   new_node.next = temp.next;
   temp.next = new_node;
   return head;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7,head);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding node in middle:")
console.log(data + "null")

Kerumitan masa kod di atas ialah O(N) kerana kita perlu berpindah ke nod di mana nod baharu perlu ditambah. Kerumitan ruang proses di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Tambah nod di hujung senarai terpaut

Contoh

Untuk menambah nod pada penghujung senarai terpaut, kita mesti mencipta nod baharu dan menambah nod selepas nod ekor dan mengalihkan nod ekor ke nod seterusnya.

// 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 add(data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next
   return tail;
}
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 = add(7);
var data = 0;
while(head != null){
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at the end: ")
console.log(data + "null")

Kerumitan masa kod di atas ialah O(1), kerana kita hanya perlu mengalihkan penunjuk, dan tiada ruang tambahan digunakan, menjadikan kerumitan ruang O(1).

KESIMPULAN

Dalam tutorial di atas, kami mempelajari cara menambah nod baharu pada senarai terpaut sedia ada dalam tiga cara yang mungkin. Kami telah melihat kod yang betul dengan penjelasan dan kerumitan masa dan ruang. Menambah nod di tengah senarai terpaut mengambil masa O(N), manakala untuk dua kes lain kerumitan masanya ialah O(1), dan untuk ketiga-tiga kemungkinan kerumitan ruang ialah O(1).

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