Struktur data dan algoritma di Java, Bahagian 4: Senarai yang dihubungkan secara tunggal

Seperti tatasusunan, yang diperkenalkan dalam Bahagian 3 dari siri tutorial ini, senarai terpaut adalah kategori struktur data asas yang berdasarkannya struktur data yang lebih kompleks. Walau bagaimanapun, tidak seperti urutan unsur, senarai terpaut adalah urutan nod, di mana setiap nod dihubungkan ke nod sebelumnya dan seterusnya dalam urutan. Ingat bahawa simpul adalah objek yang dibuat dari kelas rujukan diri, dan kelas rujukan diri mempunyai sekurang-kurangnya satu bidang yang jenis rujukannya adalah nama kelas. Nod dalam senarai terpaut dihubungkan melalui rujukan nod. Inilah contohnya:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

Dalam contoh ini, Employeeadalah kelas rujukan diri kerana nextbidangnya mempunyai jenis Employee. Medan ini adalah contoh medan pautan kerana dapat menyimpan rujukan ke objek lain dari kelasnya - dalam hal ini Employeeobjek lain .

Tutorial ini memperkenalkan selok-belok senarai yang dihubungkan secara tunggal dalam pengaturcaraan Java. Anda akan belajar operasi untuk membuat senarai yang dipautkan secara tunggal, memasukkan node ke dalam senarai yang dipautkan secara tunggal, menghapus node dari senarai yang dipautkan secara tunggal, menyatukan senarai yang dipautkan secara tunggal ke senarai lain yang dipautkan secara tunggal, dan membalikkan senarai yang dipautkan secara tunggal. Kami juga akan meneroka algoritma yang paling biasa digunakan untuk menyusun senarai yang dipautkan secara tunggal, dan diakhiri dengan contoh yang menunjukkan algoritma Penyisipan Penyisipan.

muat turun Dapatkan kod Muat turun tiga contoh aplikasi untuk artikel ini. Dicipta oleh Jeff Friesen untuk JavaWorld.

Apakah senarai yang dihubungkan secara tunggal?

Senarai pautan tunggal adalah senarai nod yang dipautkan di mana setiap nod mempunyai medan pautan tunggal. Dalam struktur data ini, pemboleh ubah rujukan mengandungi rujukan ke simpul pertama (atau atas); setiap nod (kecuali untuk simpul terakhir atau bawah) pautan ke yang seterusnya; dan medan pautan simpul terakhir mengandungi rujukan nol untuk menandakan akhir senarai. Walaupun pemboleh ubah rujukan biasanya dinamakan top, anda boleh memilih nama yang anda inginkan.

Rajah 1 membentangkan satu senarai yang mempunyai tiga nod.

Di bawah adalah pseudocode untuk senarai yang dipautkan secara tunggal.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodeadalah kelas rujukan diri dengan namemedan data dan nextmedan pautan. topadalah pemboleh ubah rujukan dari jenis Nodeyang menyimpan rujukan ke Nodeobjek pertama dalam senarai tunggal. Kerana senarai belum ada, topnilai awalnya adalah NULL.

Membuat senarai berangkai tunggal di Java

Anda membuat senarai yang dipautkan secara tunggal dengan melampirkan satu Nodeobjek. Pseudocode berikut membuat Nodeobjek, memberikan rujukannya top, memulakan bidang datanya, dan memberikannya NULLke medan pautan:

 top = NEW Node top.name = "A" top.next = NULL 

Gambar 2 menunjukkan senarai awal tunggal yang muncul dari kod pseudokod ini.

Operasi ini mempunyai kerumitan masa O (1) - berterusan. Ingat bahawa O (1) diucapkan "Big Oh of 1." (Lihat Bahagian 1 untuk peringatan bagaimana pengukuran kerumitan masa dan ruang digunakan untuk menilai struktur data.)

Memasukkan nod ke dalam senarai yang dipautkan secara tunggal

Memasukkan nod ke dalam senarai yang dipautkan secara tunggal agak lebih rumit daripada membuat senarai yang dipautkan secara tunggal kerana terdapat tiga kes yang perlu dipertimbangkan:

  • Penyisipan sebelum nod pertama.
  • Penyisipan selepas nod terakhir.
  • Penyisipan antara dua nod.

Penyisipan sebelum nod pertama

Node baru dimasukkan sebelum node pertama dengan menetapkan rujukan node atas ke medan pautan node baru dan memberikan rujukan node baru ke toppemboleh ubah. Operasi ini ditunjukkan oleh pseudocode berikut:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

Senarai dua yang dihasilkan Nodemuncul dalam Rajah 3.

Operasi ini mempunyai kerumitan masa O (1).

Penyisipan selepas nod terakhir

Node baru dimasukkan selepas node terakhir dengan memberikan null ke medan pautan node baru, melintasi senarai yang dipautkan tunggal untuk mencari node terakhir, dan memberikan rujukan node baru ke medan pautan node terakhir, seperti yang ditunjukkan oleh pseudocode berikut:

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

Gambar 4 menunjukkan senarai berikutan penyisipan NodeC selepas NodeA.

Operasi ini mempunyai kerumitan masa O ( n ) - linear. Kerumitan waktunya dapat ditingkatkan menjadi O (1) dengan mempertahankan referensi ke simpul terakhir. Sekiranya tidak perlu mencari simpul terakhir.

Penyisipan antara dua nod

Memasukkan simpul antara dua nod adalah kes yang paling kompleks. Anda memasukkan simpul baru antara dua nod dengan melintasi senarai untuk mencari simpul yang muncul sebelum nod baru, memberikan rujukan di medan pautan nod yang dijumpai ke medan pautan nod baru, dan memberikan rujukan nod baru ke pautan nod yang dijumpai bidang. Pseudocode berikut menunjukkan tugas-tugas ini:

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

Gambar 5 menunjukkan senarai berikutan penyisipan NodeD antara Nodes A dan C.

Operasi ini mempunyai kerumitan masa O ( n ).

Memadamkan nod dari senarai yang dipautkan secara tunggal

Menghapus nod dari senarai yang dipautkan secara tunggal juga agak lebih rumit daripada membuat senarai yang dipautkan secara tunggal. Walau bagaimanapun, hanya ada dua kes yang perlu dipertimbangkan:

  • Penghapusan nod pertama.
  • Penghapusan sebarang nod tetapi nod pertama.

Deletion of the first node

Deleting the first node involves assigning the link in the first node's link field to the variable that references the first node, but only when there is a first node:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted's link field to the preceding node's link field. Consider the following pseudocode:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

Saya telah membuat versi kedua SLLDemoaplikasi Java yang menunjukkan gabungan dan pembalikan. Penyenaraian 2 menunjukkan kod sumber aplikasi ini.