Pelaksanaan LinkedList dalam Javascript-tutorial js-php.cn

Javascript 中 LinkedList 的实现

Senarai terpaut ialah struktur data yang terdiri daripada jujukan elemen, setiap elemen mengandungi rujukan (atau "pautan") kepada elemen seterusnya dalam jujukan. Elemen pertama dipanggil kepala dan elemen terakhir dipanggil ekor.

Senarai terpaut mempunyai banyak kelebihan berbanding struktur data lain. Sekarang mari kita lihat cara melaksanakan senarai terpaut menggunakan JavaScript.

Tentukan kelas Node dan kelas LinkedList

Ini pada asasnya merupakan prasyarat untuk melaksanakan senarai terpaut dalam JavaScript. Dalam langkah ini, anda perlu mencipta 2 kelas, satu untuk nod dan satu lagi untuk senarai terpaut.

Kelas Node mewakili satu nod dalam senarai terpaut. Ia mempunyai dua sifat: data dan seterusnya. Atribut data digunakan untuk menyimpan data sebenar nod, manakala atribut seterusnya adalah rujukan kepada nod seterusnya dalam senarai. Kelas Node terdiri daripada pembina yang memulakan data dan sifat seterusnya apabila mencipta Node baharu.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}

Salin selepas log masuk

Kelas LinkedList ialah perwakilan senarai terpaut itu sendiri. Ia mempunyai atribut kepala yang merujuk kepada nod pertama dalam senarai. Kelas LinkedList juga mempunyai pembina yang memulakan sifat kepala apabila mencipta LinkedList baharu.

class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
}

Salin selepas log masuk

Kelas LinkedList juga mengandungi kaedah yang membolehkan anda memasukkan, memadam dan mencari nod dalam senarai, sambil membenarkan operasi lain seperti mencetak senarai, mengira elemen, membalikkan senarai, dsb.

Cetak Senarai Pautan

Anda boleh mencetak elemen senarai terpaut dengan melintasi senarai terpaut dan mencetak data setiap nod.

printAll() {
   let current = this.head;
   while (current) {
      console.log(current.data);
      current = current.next;
   }
}

Salin selepas log masuk

Tambahkan nod pada senarai terpaut

Terdapat pelbagai cara untuk menambah data pada senarai terpaut, bergantung pada tempat nod baharu perlu dimasukkan, seperti berikut -

Tambahkan nod pada permulaan senarai terpaut

Untuk menambah nod/elemen pada permulaan senarai terpaut, sebaik sahaja anda membuat nod baharu dengan data, cuma tetapkan sifat seterusnya kepada kepala semasa senarai terpaut. Anda kemudiannya boleh mengemas kini kepala senarai terpaut ke nod baharu. Ini juga dipanggil sisipan kepala senarai terpaut dan merupakan jenis penambahan data yang paling asas. Ini dilakukan hanya dengan memanggil fungsi tambah yang ditakrifkan di bawah.

add(data) {
   const newNode = new Node(data);
   if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
   } else {
      this.tail.next = newNode;
      this.tail = newNode;
   }
   this.length++;
   return this;
}

Salin selepas log masuk

Tambahkan nod pada penghujung senarai terpaut

Untuk menambah nod/elemen pada penghujung senarai terpaut, kita perlu melintasi senarai terpaut dan mencari nod terakhir. Selepas itu buat nod baharu dengan data dan tetapkan sifat seterusnya nod terakhir kepada nod baharu. Ini juga dipanggil sisipan ekor senarai terpaut dan merupakan jenis tambahan data kedua paling asas. Ini dilakukan hanya dengan memanggil fungsi addToTail yang ditakrifkan di bawah.

addToTail(data) {
   let newNode = new Node(data);
   if (this.head === null) {
      this.head = newNode;
      return;
   }
   let current = this.head;
   while (current.next !== null) {
      current = current.next;
   }
   current.next = newNode;
}

Salin selepas log masuk

Tambah nod di lokasi tertentu

Untuk menambah nod/elemen pada kedudukan tertentu dalam senarai terpaut, anda boleh melintasi senarai terpaut untuk mencari nod pada kedudukan sebelum titik sisipan, buat nod baharu dengan data, tetapkan atribut seterusnya nod baharu ke nod semasa pada kedudukan itu, dan tukar Atribut seterusnya nod sebelumnya ditetapkan kepada nod baharu.

addAtPosition(data, position) {
   let newNode = new Node(data);
   if (position === 1) {
      newNode.next = this.head;
      this.head = newNode;
      return;
   }
   let current = this.head;
   let i = 1;
   while (i < position - 1 && current) {
      current = current.next;
      i++;
   }
   if (current) {
      newNode.next = current.next;
      current.next = newNode;
   }
}

Salin selepas log masuk

Contoh (tambah nod pada senarai terpaut)

Dalam contoh di bawah, kami telah menambah nod pada kedudukan awal, akhir dan tertentu.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   //function to add data to tail
   addToTail(data) {
      let newNode = new Node(data);
      if (this.head === null) {
         this.head = newNode;
         return;
      }
      let current = this.head;
      while (current.next !== null) {
         current = current.next;
      }
      current.next = newNode;
   }
   
   // function to insert data to linked list at a particular index
   addAtPosition(data, position) {
      let newNode = new Node(data);
      if (position === 1) {
         newNode.next = this.head;
         this.head = newNode;
         return;
      }
      let current = this.head;
      let i = 1;
      while (i < position - 1 && current) {
         current = current.next;
         i++;
      }
      if (current) {
         newNode.next = current.next;
         current.next = newNode;
      }
   }
   
   // this function is used to iterate over the entire linkedlist and print
   it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();

// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after adding nodex at position 2");
list.addAtPosition("nodex",2);
list.printAll();
console.log("List after adding nodey to tail");
list.addToTail("nodey");
list.printAll();

Salin selepas log masuk

Output

Initial List:
node1
node2
node3
node4

List after adding nodex at position 2
node1
nodex
node2
node3
node4
List after adding nodey to tail
node1
nodex
node2
node3
node4
nodey

Salin selepas log masuk

Padamkan Nod

Data juga boleh dipadamkan melalui pelbagai kaedah atas permintaan.

Padamkan nod tertentu

Untuk memadamkan nod tertentu daripada senarai terpaut, kita perlu melintasi senarai terpaut dan mencari nod sebelum nod untuk dipadamkan, mengemas kini sifat seterusnya untuk melangkau nod yang akan dipadamkan dan mengemas kini rujukan ke nod seterusnya. Ini akan memadamkan nod berdasarkan nilai.

remove(data) {
   if (!this.head) {
      return null;
   }
   if (this.head.data === data) {
      this.head = this.head.next;
      this.length--;
      return this;
   }
   let current = this.head;
   while (current.next) {
      if (current.next.data === data) {
         current.next = current.next.next;
         this.length--;
         return this;
      }
      current = current.next;
   }
   return null;
}

Salin selepas log masuk

Padamkan nod di lokasi tertentu

Untuk memadamkan nod pada kedudukan tertentu dalam senarai terpaut, kita perlu melintasi senarai terpaut dan mencari nod sebelum nod untuk dipadamkan, mengemas kini sifat seterusnya untuk melangkau nod yang akan dipadamkan, dan kemudian mengemas kini rujukan kepada nod seterusnya. Ini pada asasnya memadamkan nod berdasarkan nilai indeksnya.

removeAt(index) {
   if (index < 0 || index >= this.length) return null;
   if (index === 0) return this.remove();
   let current = this.head;
   for (let i = 0; i < index - 1; i++) {
      current = current.next;
   }
   current.next = current.next.next;
   this.length--;
   return this;
}

Salin selepas log masuk

Contoh (mengalih keluar nod daripada senarai linear)

Dalam contoh di bawah, kami melaksanakan pemadaman nod dan nod tertentu di lokasi tertentu.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } 
      else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   // function to remove data from linked list
   remove(data) {
      if (!this.head) {
         return null;
      }
      if (this.head.data === data) {
         this.head = this.head.next;
         this.length--;
         return this;
      }
      let current = this.head;
      while (current.next) {
         if (current.next.data === data) {
            current.next = current.next.next;
            this.length--;
            return this;
         }
         current = current.next;
      }
      return null;
   }
   
   // function to remove from a particular index 
      removeAt(index) {
      if (index < 0 || index >= this.length) return null;
      if (index === 0) return this.remove();
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
         current = current.next;
      }
      current.next = current.next.next;
      this.length--;
      return this;
   }
   
   // this function is used to iterate over the entire linkedlist and print it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after removing node2");
list.remove("node2");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();

Salin selepas log masuk

Output

Initial List:
node1
node2
node3
node4
List after removing node2
node1
node3
node4

List after removing node at index 2
node1
node3

Salin selepas log masuk

Kesimpulan

Melaksanakan senarai terpaut dalam JavaScript melibatkan penciptaan kelas Nod untuk mewakili setiap nod dalam senarai dan kelas LinkedList untuk mewakili senarai itu sendiri, dan menambah kaedah pada kelas LinkedList untuk melaksanakan operasi seperti menambah dan mengalih keluar data dan mencetak senarai. Adalah penting untuk mempertimbangkan kes-kes tepi dan mengendalikannya dengan sewajarnya dalam pelaksanaan. Bergantung pada kes penggunaan, terdapat pelbagai cara untuk menambah atau mengalih keluar data daripada LinkedList.

Atas ialah kandungan terperinci Pelaksanaan LinkedList dalam Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!