Liste liée aux structures de données et aux algorithmes

Hari 1

Struktur data asas

Kami bukan sahaja akan belajar tentang senarai terpaut dengan cara tradisional; kami juga akan meneroka kelas Node dan LinkedList, serta semua operasi yang boleh dilakukan padanya.

Apakah itu Senarai Berpaut?

Senarai terpaut ialah koleksi elemen yang dipanggil nod, di mana setiap nod mengandungi elemen data dan rujukan (atau pautan) ke nod seterusnya dalam jujukan.
Senarai terpaut ialah struktur data linear di mana elemen disimpan dalam nod. Setiap nod mengandungi dua bahagian:
Tidak seperti tatasusunan, *senarai terpaut tidak menyimpan elemen dalam lokasi memori bersebelahan.
* Sebaliknya, setiap nod menghala ke nod seterusnya, membenarkan penggunaan memori dinamik dan sisipan atau pemadaman elemen yang mudah.

perkara utama Senarai Berpaut

1. Struktur Nod: Senarai terpaut terdiri daripada nod, setiap satu mengandungi nilai dan rujukan kepada nod seterusnya. Meneroka struktur dan sifat nod membantu dalam memahami cara senarai terpaut mengatur dan menyimpan data.
2. Kepala dan Ekor: Nod pertama dalam senarai terpaut dipanggil kepala, manakala nod terakhir dirujuk sebagai ekor. Memahami ciri dan kefungsian nod kepala dan ekor adalah penting untuk traversal dan manipulasi senarai terpaut yang cekap.

Ciri-ciri Utama:

Saiz dinamik: Ia boleh membesar atau mengecut mengikut keperluan.
Akses berurutan: Mengakses elemen memerlukan merentasi dari nod pertama (kepala).

Jenis Senarai Terpaut:

Terdapat tiga bentuk asas senarai terpaut
1. Senarai pautan tunggal.
2. Senarai terpaut berganda.
3. Senarai pautan pekeliling.

Dalam artikel ini, Kami akan meneroka senarai dipautkan tunggal.

Senarai terpaut tunggal.

Setiap nod mempunyai rujukan kepada nod seterusnya.

• Setiap nod mengandungi:
  • Data (nilai yang anda mahu simpan).
  • Penunjuk seterusnya, yang menunjuk ke nod seterusnya dalam jujukan.
• Penunjuk seterusnya nod terakhir adalah batal kerana tiada nod selepasnya.

Analogi Kehidupan Sebenar: Anak panah – Sebaik sahaja anak panah ditembak, ia hanya boleh bergerak ke hadapan.
Sebaik sahaja anak panah dilepaskan, ia terbang dalam garis lurus tanpa keupayaan untuk kembali.
Begitu juga, dalam Senarai Pautan Tunggal, sebaik sahaja anda berpindah dari satu nod ke nod seterusnya, anda tidak boleh berundur—anda hanya boleh terus bergerak ke hadapan.

[Data | Next] -> [Data | Next] -> [Data | Next] -> null

Operasi pada Senarai Berpaut Tunggal

• Perjalanan
• Mencari
• Panjang
• Sisipan:
  • Sisipkan pada permulaan
  • Sisipkan di hujung
  • Sisipkan pada kedudukan tertentu
• Pemadaman:
  • Padam dari awal
  • Padam dari penghujung
  • Padamkan nod tertentu

Sisipan:

Masukkan pada permulaan

Jom buat kelas Node

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

Mari pecahkan kelas Node.

**Kelas Node mewakili setiap elemen individu dalam senarai terpaut. Setiap nod mengandungi dua sifat:

Sifat:

- Data: Ini memegang nilai yang disimpan dalam nod (seperti nombor, rentetan atau objek).
- Seterusnya: Ini memegang rujukan (atau penuding) ke nod seterusnya dalam senarai terpaut. Pada mulanya, ia ditetapkan kepada null kerana apabila nod dibuat, ia belum dipautkan kepada mana-mana nod lain.

Pecahan:

Pembina (pembina(data)):
Ini ialah kaedah khas dalam kelas JavaScript yang dipanggil apabila tika baharu kelas Node dibuat.
Parameter data dihantar masuk apabila membuat nod baharu dan ia menyimpan nilai sebenar nod tersebut.
this.next = null; menetapkan sifat seterusnya kepada null pada mulanya kerana apabila nod dibuat, ia belum disambungkan kepada mana-mana nod lain lagi.

Contoh:

let node1 = new Node(10); // Create a node with the value 10
console.log(node1.data);  // Output: 10
console.log(node1.next);  // Output: null (because it's not linked to any other node yet)

Jom buat kelas SingleLinkList

class SinglyLinkedList {
  constructor() {
    this.head = null; // Initially, the list is empty, so the head is null.
    this.size = 0; // The size is initially 0, as there are no nodes in the list.
  }

  // Insert at the beginning
  insertAtBeginning(data) {
    let newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // The new node's next points to the current head
    this.head = newNode; // Update the head to be the new node
    this.size++; // Increment the size of the list
  }
}

Kelas SinglyLinkedList mewakili keseluruhan struktur senarai terpaut. Ia menguruskan berbilang objek Nod dan menyediakan kaedah untuk bekerja dengan senarai, seperti memasukkan, memadam dan melintasi nod dan sebagainya.

Sifat:

- Ketua: Ini adalah rujukan kepada nod pertama (atau "kepala") senarai terpaut. Pada mulanya, ia ditetapkan kepada null, bermakna senarai itu kosong.
- Saiz: Ini menjejaki bilangan nod yang berada dalam senarai terpaut pada masa ini. Pada mulanya, ia ditetapkan kepada 0 kerana senarai itu kosong.

Pecahan:

Pembina (pembina()):

this.head = null;: This initializes the linked list with no elements, so the head points to null.
this.size = 0;: The size starts as 0 because there are no nodes in the list.

insertAtBeginning(data): for the sake of simplicity, later on, we will Deep Dive into the insertAtBeginning(data) method
let newNode = new Node(data);: This creates a new node with the value passed in as data.
newNode.next = this.head;: This links the new node to the current head (which could be nullif the list is empty or point to an existing node if the list has elements).
this.head = newNode;: This updates the head of the list to point to the new node, making it the first node in the list.
this.size++;: The size of the linked list is increased by 1 as a new node has been added.

let's Test

let list = new SinglyLinkedList();
list.insertAtBeginning(10); // List becomes: 10
list.insertAtBeginning(20); // List becomes: 20 -> 10
console.log(list.head.data); // Output: 20 (since the head is now the first node with value 20)
console.log(list.size);      // Output: 2 (since there are two nodes in the list)

Linked List deep dive Line by Line.

let's jump into the insertAtBeginning(data) method .

class Node {
  constructor(data) {
    this.data = data;   // Store the data value (like 10, 20, etc.)
    this.next = null;   // Initialize the next pointer as null
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;   // Initially, the list is empty, so the head is null
    this.size = 0;      // The size of the list starts at 0
  }

  // Insert at the beginning of the list
  insertAtBeginning(data) {
    // Step 1: Create a new node with the given data
    let newNode = new Node(data); 

    // Explanation:
    // First time: If we insert 10, the newNode looks like this -> Node { data: 10, next: null }
    // Second time: If we insert 20, the newNode looks like this -> Node { data: 20, next: null }

    // Step 2: Point the new node's next property to the current head of the list
    newNode.next = this.head;

    // Explanation:
    // First time: Since the list is empty (this.head is null), newNode's next is set to null.
    // Second time: this.head is now the node with data 10, so newNode’s next will point to the node with data 10. 
    // So it looks like this: Node { data: 20, next: Node { data: 10, next: null } }

    // Step 3: Make the new node the new head of the list
    this.head = newNode;

    // Explanation:
    // First time: Now, the new node becomes the head. The list looks like this: Node { data: 10, next: null }.
    // Second time: The new node (with data 20) becomes the head, and it points to the previous head (which is the node with data 10).

    // Step 4: Increment the size of the list
    this.size++;

    // Explanation:
    // First time: The size is now 1 because there is one node (data 10).
    // Second time: The size becomes 2 because we added another node (data 20).
  }
}

// Example Usage:
let list = new SinglyLinkedList();
list.insertAtBeginning(10);  // First insertion: the list becomes [10]
list.insertAtBeginning(20);  // Second insertion: the list becomes [20 -> 10]

console.log(list);

// Output:
// SinglyLinkedList {
//   head: Node { data: 20, next: Node { data: 10, next: null } },
//   size: 2
// }

Coming soon...

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!