Struktur Data dengan JavaScript: Senarai Singly-Linked dan senarai dua kali ganda

Artikel ini meneroka senarai yang berkaitan dengan tunggal dan dua kali ganda, dua struktur data asas dalam sains komputer. Selalunya disalahpahami, struktur ini difahami dengan baik melalui analogi relatable: pemburu pemulung.

Memahami senarai yang berkaitan dengan singly

Senarai yang berkaitan dengan singly adalah urutan nod yang saling berkaitan. Setiap nod memegang data dan penunjuk merujuk nod seterusnya dalam urutan. Ini mencerminkan pemburu pemulung: Setiap petunjuk (nod) mengandungi mesej (data) dan arahan (penunjuk) yang membawa kepada petunjuk seterusnya. Seluruh urutan petunjuk membentuk perburuan lengkap.

Operasi senarai berkaitan singly

Kami akan mengkaji operasi untuk kedua -dua Node dan SinglyList (atau, dalam kes kami, DoublyList ) pembina.

• Node: Blok bangunan asas yang mengandungi data.
• Doublylist:
  • _length : Mengesan bilangan nod.
  • head : menunjuk ke nod pertama.
  • tail : Point ke nod terakhir (perbezaan utama dari senarai yang berkaitan dengan tunggal).
  • add(value) : Menambah nod baru.
  • searchNodeAt(position) : Cari nod pada indeks tertentu.
  • remove(position) : Menghapus nod pada indeks tertentu.

Pelaksanaan senarai yang berkaitan dengan dua kali ganda

Mari kita melaksanakan DoublyList dalam JavaScript.

Pertama, pembina Node :

 nod kelas {
  pembina (nilai) {
    this.data = nilai;
    this.previous = null; // penunjuk ke nod sebelumnya
    this.next = null; // penunjuk ke nod seterusnya
  }
}

Pembina DoublyList :

 kelas doublylist {
  pembina () {
    this._length = 0;
    this.head = null;
    this.tail = null;
  }
}

Kaedah senarai yang berkaitan dengan dua kali ganda

Berikut adalah pelaksanaan add(value) , searchNodeAt(position) , dan remove(position) , diubahsuai untuk traversal bidirectional.

add(value) :

 tambah (nilai) {
  const node = nod baru (nilai);
  jika (this._length) {
    this.tail.next = node;
    node.Previous = this.tail;
    this.tail = node;
  } else {
    this.head = node;
    this.tail = node;
  }
  this._length;
  Node kembali;
}

searchNodeAt(position) : (sama dengan versi senarai yang berkaitan dengan tunggal)

 searchNodeat (kedudukan) {
  // ... (pelaksanaan tetap sama) ...
}

remove(position) :

 keluarkan (kedudukan) {
  // ... (pelaksanaan lebih kompleks, mengendalikan empat kes: kedudukan tidak sah, mengeluarkan kepala, mengeluarkan ekor, mengeluarkan nod tengah. Rujuk artikel asal untuk pelaksanaan terperinci.) ...
}

Kesimpulan

Artikel ini memberikan penjelasan yang jelas mengenai senarai yang berkaitan dengan tunggal dan dua kali ganda, menggunakan analogi memburu pemulung. Kod JavaScript yang disediakan menunjukkan pelaksanaan senarai yang berkaitan dengan dua kali ganda, menonjolkan perbezaan dan kerumitan utama berbanding dengan senarai yang berkaitan dengan singly. Ingatlah untuk bereksperimen dengan kod untuk menguatkan pemahaman anda.

Atas ialah kandungan terperinci Struktur Data dengan JavaScript: Senarai Singly-Linked dan senarai dua kali ganda. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!