Struktur data dan algoritma di Java, Bahagian 5: Senarai yang berganda-ganda

Walaupun senarai yang mempunyai kaitan tunggal mempunyai banyak kegunaan, mereka juga mempunyai beberapa batasan. Untuk satu perkara, senarai berangkai tunggal mengehadkan traversal nod ke satu arah: anda tidak boleh melintasi senarai yang dipautkan tunggal ke belakang melainkan anda membalikkan pautan nodnya terlebih dahulu, yang memerlukan masa. Sekiranya anda melakukan traversal terbalik dan perlu mengembalikan node-traversal ke arah asal, anda harus mengulang inversi, yang memerlukan lebih banyak masa. Senarai berangkai tunggal juga menyekat penghapusan nod. Dalam senarai jenis ini, anda tidak boleh menghapus node sewenang-wenang tanpa akses ke pendahulu nod.

Nasib baik, Java menawarkan beberapa jenis senarai yang boleh anda gunakan untuk mencari dan menyusun data yang tersimpan dalam program Java anda. Tutorial terakhir dalam rangkaian struktur dan algoritma ini memperkenalkan pencarian dan penyusunan dengan senarai berangkai dua kali ganda dan senarai berkaitan bulat. Seperti yang akan anda lihat, kedua kategori struktur data ini dibina berdasarkan senarai yang dipautkan secara tunggal untuk menawarkan lebih banyak tingkah laku mencari dan menyusun dalam program Java anda.

Senarai yang berganda-ganda

A senarai duanya adalah terpakai berkaitan adalah senarai berpaut nod di mana setiap nod mempunyai sepasang bidang link. Medan satu pautan membolehkan anda melintasi senarai ke arah depan, sedangkan simpul yang lain membolehkan anda melintasi senarai ke arah belakang. Untuk arah ke hadapan, pemboleh ubah rujukan menyimpan rujukan ke nod pertama. Setiap nod menghubungkan ke node seterusnya melalui medan pautan "seterusnya", kecuali untuk node terakhir, yang medan pautan "seterusnya" mengandungi rujukan nol untuk menandakan akhir senarai (ke arah depan). Arah belakang berfungsi sama. Pemboleh ubah rujukan menyimpan rujukan ke simpul terakhir arah ke depan, yang anda tafsirkan sebagai nod pertama. Setiap nod memaut ke nod sebelumnya melalui medan pautan "sebelumnya". Node pertama "sebelumnya"medan pautan mengandungi nol untuk menandakan akhir senarai.

Cuba fikirkan senarai berangkai ganda sebagai sepasang senarai berangkai tunggal, masing-masing saling menghubungkan nod yang sama. Gambarajah dalam Rajah1 menunjukkan topForwardsenarai topBackwardberangkai tunggal yang disenaraikan -dikenalpasti dan -dikemukakan.

Operasi CRUD dalam senarai berganda

Membuat, memasukkan, dan menghapus nod adalah semua operasi biasa dalam senarai berganda-ganda. Mereka serupa dengan operasi yang anda pelajari untuk senarai yang dihubungkan secara tunggal. (Ingat bahawa senarai berangkai ganda hanyalah sepasang senarai berangkai tunggal yang saling menghubungkan nod yang sama.) Pseudokod berikut menunjukkan penciptaan dan penyisipan nod ke dalam senarai berganda berganda yang ditunjukkan dalam Rajah 1. Pseudocode juga menunjukkan nod penghapusan:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Contoh aplikasi: CRUD dalam senarai berganda-ganda

Contoh aplikasi Java DLLDemomenunjukkan cara membuat, memasukkan, dan menghapus node dalam senarai berganda. Kod sumber aplikasi ditunjukkan dalam Penyenaraian 1.

Penyenaraian 1. Aplikasi Java yang menunjukkan CRUD dalam senarai berganda-ganda

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Susun Penyenaraian 4 seperti berikut:

 javac DLLDemo.java 

Jalankan aplikasi yang dihasilkan seperti berikut:

 java DLLDemo 

Anda harus memerhatikan output berikut:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Berombak dalam senarai berganda

Java Collections Framework merangkumi Collectionskelas kaedah utiliti, yang merupakan sebahagian daripada java.utilpakej. Kelas ini merangkumi void shuffle(List list)kaedah yang " mengesahkan senarai yang ditentukan secara rawak menggunakan sumber kebiasaan lalai ." Sebagai contoh, anda mungkin menggunakan kaedah ini untuk merombak setumpuk kad yang dinyatakan sebagai senarai berangkai ganda ( java.util.LinkedListkelasnya adalah contoh). Dalam pseudokod di bawah ini, anda dapat melihat bagaimana algoritma Shuffle dapat mengubah senarai yang berganda:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

Algoritma Shuffle memperoleh sumber rawak dan kemudian melintasi senarai ke belakang, dari simpul terakhir hingga yang kedua. Berkali-kali menukar nod yang dipilih secara rawak (yang sebenarnya hanya bidang nama) ke "kedudukan semasa." Node dipilih secara rawak dari bahagian senarai yang berjalan dari simpul pertama ke kedudukan semasa, inklusif. Perhatikan bahawa algoritma ini diambil kira secara kasar dari void shuffle(List list)kod sumber.

Algoritma Shuffle pseudocode malas kerana hanya memfokuskan pada senarai tunggal yang bergerak maju. Ini adalah keputusan reka bentuk yang munasabah, tetapi kami membayar harga dalam kerumitan masa. Kerumitan masa adalah O ( n 2). Pertama, kita mempunyai gelung O ( n ) yang memanggil swap(). Kedua, dalam swap(), kita mempunyai dua gelung O ( n ) yang berurutan . Ingat peraturan berikut dari Bahagian 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

Bahagian (a) membincangkan algoritma berurutan. Di sini, kita mempunyai dua gelung O ( n ). Menurut peraturan, kerumitan waktu yang dihasilkan adalah O ( n ). Bahagian (b) membincangkan algoritma bersarang. Dalam kes ini, kita mempunyai O ( n ) dikalikan dengan O ( n ), menghasilkan O ( n 2).

Perhatikan bahawa kerumitan ruang Shuffle adalah O (1), yang dihasilkan dari pemboleh ubah pembantu yang dinyatakan.

Contoh aplikasi: Berombak dalam senarai berangkai ganda

Yang Shufflepermohonan di dalam Senarai 2 adalah demonstrasi algoritma Shuffle.

Penyenaraian 2. Algoritma Shuffle di Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Susun Penyenaraian 5 seperti berikut:

 javac Shuffle.java 

Jalankan aplikasi yang dihasilkan seperti berikut:

 java Shuffle 

Anda harus memerhatikan output berikut dari satu larian:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Senarai pautan pekeliling

Medan pautan di simpul terakhir senarai yang dipautkan tunggal mengandungi pautan nol. Ini juga berlaku dalam senarai yang dipautkan dua kali ganda, yang mengandungi medan pautan di simpul terakhir dari senarai tunggal yang dihubungkan ke depan dan ke belakang. Oleh itu, anggaplah bahawa simpul terakhir mengandungi pautan ke nod pertama. Dalam keadaan seperti ini, anda akan berakhir dengan senarai berangkai bulat , yang ditunjukkan dalam Gambar 2.

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • Mereka menawarkan penyisipan / penghapusan nod yang lebih pantas daripada operasi berdasarkan array yang setara. Hanya pautan yang perlu dikemas kini setelah mengenal pasti kedudukan sisipan / hapus. Dari perspektif array, penyisipan item data memerlukan pergerakan semua item data lain untuk membuat elemen kosong. Begitu juga, penghapusan item data yang ada memerlukan pergerakan semua item data lain untuk membuang elemen kosong. Semua pergerakan item data memerlukan masa.

Sebaliknya, tatasusunan menawarkan kelebihan berikut berbanding senarai terpaut:

  • Elemen array menempati memori yang lebih sedikit daripada nod kerana elemen tidak memerlukan medan pautan.
  • Susunan menawarkan akses lebih cepat ke item data, melalui indeks berdasarkan bilangan bulat.