Cara Melaksanakan Senarai Berpaut Tunggal dalam JavaScript

Hai ?, selamat datang kembali ke siri ini pada senarai terpaut. Dalam artikel terakhir kami, kami mempelajari tentang asas senarai terpaut, termasuk definisi, istilah, perbezaannya dengan tatasusunan dan jenis senarai terpaut. Saya berjanji kita akan menyelami lebih mendalam tentang pelaksanaan senarai terpaut, jadi mari kita mulakan.

Rangka Kursus

1. Pengenalan
2. Melaksanakan Senarai Berpaut Tunggal
   • Mencipta Nod baharu
   • Sisipkan pada Permulaan
   • Sisipkan di Hujung
   • Padamkan Nod
   • Cari Nod
   • Lintas Senarai
3. Kesimpulan

pengenalan

Seperti yang telah kita pelajari dalam artikel sebelumnya, Senarai Terpaut ialah struktur data asas dalam dunia pengaturcaraan. Ia terdiri daripada nod, di mana setiap nod mengandungi data dan rujukan (atau pautan) ke nod seterusnya (dalam senarai berpaut tunggal) atau kedua-dua nod seterusnya dan sebelumnya (dalam senarai berganda ganda) dalam jujukan. Tidak seperti tatasusunan, senarai terpaut tidak menyimpan elemen dalam lokasi memori bersebelahan, membolehkan sisipan dan pemadaman yang cekap.

Memahami konsep senarai terpaut adalah penting untuk menguasai struktur data dan algoritma. Dalam artikel ini, kami akan menyelami lebih mendalam tentang pelaksanaan senarai terpaut, bermula dengan asas senarai pautan tunggal.

Melaksanakan Senarai Berpaut Tunggal

Senarai Pautan Tunggal ialah jenis senarai terpaut yang paling mudah, di mana setiap nod menghala ke nod seterusnya dalam jujukan. Sama seperti dalam imej di bawah.

Kini, tiba masanya untuk mula melaksanakan operasi asas senarai pautan tunggal kami. Boleh?

Mencipta Node baharu

Mari kita mulakan dengan mencipta kelas Node baharu. Kelas Node akan mempunyai pembina yang mengambil data untuk nod dan penunjuk seterusnya yang pada mulanya ditetapkan kepada null.

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Kelas Nod yang baru dibuat ini (yang mewakili nod dalam senarai terpaut) boleh digambarkan seperti di bawah.

Sebelum kami meneruskan, mari buat contoh baharu kelas SinglyLinkedList kami yang akan mengadakan operasi senarai terpaut kami.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Sisipkan pada Permulaan

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Penjelasan: Memasukkan pada permulaan adalah seperti seseorang yang baru menyertai barisan di hadapan. Mereka menjadi orang pertama yang baharu, memaut kepada orang pertama yang terdahulu.

Masukkan di Hujung

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Penjelasan: Memasukkan pada penghujung adalah seperti seseorang yang menyertai baris di hujung sekali. Kita perlu berjalan hingga ke penghujung untuk mencari orang terakhir, kemudian pautkan mereka kepada orang baharu.

Padamkan Nod

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Penjelasan: Memadamkan nod adalah seperti seseorang di tengah baris memutuskan untuk keluar. Kami mencari orang itu dan menghubungkan orang sebelum mereka dengan orang selepas mereka.

Cari Nod

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Penjelasan: Mencari nod adalah seperti cuba mencari orang tertentu dalam baris. Kami bermula di hadapan dan bertanya kepada setiap orang sehingga kami menemui mereka atau sampai ke penghujung.

Lintas Senarai

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Penjelasan: Merentasi adalah seperti berjalan di barisan dan memberi salam kepada setiap orang. Kami bermula di hadapan dan terus bergerak sehingga kami sampai ke penghujung.

Kesimpulan

Dalam artikel ini, kami telah mempelajari tentang operasi asas senarai terpaut dan cara melaksanakannya dalam JavaScript. Dalam artikel seterusnya, kita akan mempelajari tentang Senarai Berganda Berkaitan.

Ingat, menguasai senarai terpaut memerlukan latihan. Teruskan menyelesaikan masalah dan melaksanakan struktur data ini dalam pelbagai senario.

Kekal Kemas Kini dan Terhubung

Untuk memastikan anda tidak terlepas mana-mana bahagian dalam siri ini dan untuk berhubung dengan saya untuk perbincangan yang lebih mendalam tentang Pembangunan Perisian (Web, Pelayan, Mudah Alih atau Mengikis / Automasi), struktur data dan algoritma serta teknologi menarik yang lain topik, ikuti saya di:

• GitHub
• Linkedin
• X (Twitter)

Nantikan dan selamat mengekod ?‍??

Atas ialah kandungan terperinci Cara Melaksanakan Senarai Berpaut Tunggal dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!