Implementasi Java Circular Linked List

1. Perkenalan

Dalam tutorial ini, kita akan melihat implementasi daftar tautan melingkar di Java.

2. Daftar Tertaut Melingkar

Daftar tertaut melingkar adalah variasi dari daftar tertaut di mana simpul terakhir menunjuk ke simpul pertama, menyelesaikan satu lingkaran penuh simpul . Dengan kata lain, variasi dari daftar tertaut ini tidak memiliki elemen nol di akhir.

Dengan perubahan sederhana ini, kami memperoleh beberapa manfaat:

  • Setiap node dalam daftar tertaut melingkar bisa menjadi titik awal
  • Akibatnya, seluruh daftar dapat dilalui mulai dari node mana pun
  • Karena simpul terakhir dari daftar tertaut melingkar memiliki penunjuk ke simpul pertama, mudah untuk melakukan operasi enqueue dan dequeue

Secara keseluruhan, ini sangat berguna dalam implementasi struktur data antrian.

Dari segi kinerja, ini sama dengan implementasi daftar tertaut lainnya kecuali untuk satu hal: Melintasi dari simpul terakhir ke simpul kepala dapat dilakukan dalam waktu yang konstan . Dengan daftar tertaut konvensional, ini adalah operasi linier.

3. Implementasi di Jawa

Mari kita mulai dengan membuat kelas Node tambahan yang akan menyimpan nilai int dan penunjuk ke simpul berikutnya :

class Node { int value; Node nextNode; public Node(int value) { this.value = value; } }

Sekarang mari buat simpul pertama dan terakhir dalam daftar tertaut melingkar, biasanya disebut kepala dan ekor:

public class CircularLinkedList { private Node head = null; private Node tail = null; // .... }

Di subbagian berikutnya kita akan melihat operasi paling umum yang dapat kita lakukan pada daftar tertaut melingkar.

3.1. Memasukkan Elemen

Operasi pertama yang akan kita bahas adalah penyisipan node baru. Saat memasukkan elemen baru, kita perlu menangani dua kasus:

  • The kepala simpul adalah nol , yang tidak ada unsur sudah ditambahkan. Dalam kasus ini, kita akan membuat simpul baru yang kita tambahkan sebagai kepala dan ekor dari daftar karena hanya ada satu simpul
  • The kepala node tidak nol , yang mengatakan, ada satu atau lebih elemen yang sudah ditambahkan ke daftar. Dalam hal ini, ekor yang ada harus mengarah ke simpul baru dan simpul yang baru ditambahkan akan menjadi ekor

Dalam kedua kasus di atas, nextNode untuk tail akan mengarah ke head

Mari buat metode addNode yang mengambil nilai untuk dimasukkan sebagai parameter:

public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; tail.nextNode = head; }

Sekarang kita dapat menambahkan beberapa angka ke daftar tertaut melingkar kita:

private CircularLinkedList createCircularLinkedList() { CircularLinkedList cll = new CircularLinkedList(); cll.addNode(13); cll.addNode(7); cll.addNode(24); cll.addNode(1); cll.addNode(8); cll.addNode(37); cll.addNode(46); return cll; }

3.2. Menemukan sebuah Elemen

Operasi selanjutnya yang akan kita lihat adalah mencari untuk menentukan apakah suatu elemen ada dalam daftar.

Untuk ini, kita akan memperbaiki node dalam daftar (biasanya head ) sebagai currentNode dan melintasi seluruh daftar menggunakan nextNode dari node ini , sampai kita menemukan elemen yang diperlukan.

Mari menambahkan metode baru containsNode yang mengambil searchValue sebagai parameter:

public boolean containsNode(int searchValue) { Node currentNode = head; if (head == null) { return false; } else { do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.nextNode; } while (currentNode != head); return false; } }

Sekarang, mari tambahkan beberapa tes untuk memverifikasi bahwa daftar yang dibuat di atas berisi elemen yang kami tambahkan dan tidak ada yang baru:

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(8)); assertTrue(cll.containsNode(37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() { CircularLinkedList cll = createCircularLinkedList(); assertFalse(cll.containsNode(11)); }

3.3. Menghapus sebuah Elemen

Selanjutnya, kita akan melihat operasi hapus. Mirip dengan penyisipan, kami memiliki beberapa kasus (tidak termasuk kasus di mana daftarnya sendiri kosong) yang perlu kami lihat.

  • Elemen yang akan dihapus adalah kepala itu sendiri . Dalam hal ini, kita perlu memperbarui kepala sebagai simpul berikutnya dari kepala saat ini , dan simpul ekor berikutnya sebagai kepala baru
  • Elemen yang akan dihapus adalah elemen apa pun selain kepala . Dalam hal ini, kita hanya perlu mengupdate node berikutnya dari node sebelumnya sebagai node berikutnya dari node yang perlu dihapus.

Sekarang kita akan menambahkan metode baru deleteNode yang menggunakan valueToDelete sebagai parameter:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Sekarang mari tambahkan tes sederhana untuk memverifikasi bahwa penghapusan berfungsi seperti yang diharapkan untuk semua kasus:

@Test public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(13)); cll.deleteNode(13); assertFalse(cll.containsNode(13)); assertTrue(cll.containsNode(1)); cll.deleteNode(1); assertFalse(cll.containsNode(1)); assertTrue(cll.containsNode(46)); cll.deleteNode(46); assertFalse(cll.containsNode(46)); }

3.4. Melintasi Daftar

Kita akan melihat traversal dari daftar tertaut melingkar kita di bagian akhir ini . Mirip dengan operasi pencarian dan hapus, untuk traversal kita memperbaiki currentNode sebagai head dan melintasi seluruh daftar menggunakan nextNode dari node ini.

Mari tambahkan metode baru traverseList yang mencetak elemen yang ditambahkan ke daftar:

public void traverseList() { Node currentNode = head; if (head != null) { do { LOGGER.info(currentNode.value + " "); currentNode = currentNode.nextNode; } while (currentNode != head); } } 

Seperti yang bisa kita lihat, pada contoh di atas, selama traversal, kita cukup mencetak nilai dari masing-masing node, sampai kita kembali ke node head.

4. Kesimpulan

Dalam tutorial ini, kita telah melihat bagaimana menerapkan daftar tertaut melingkar di Java dan menjelajahi beberapa operasi yang paling umum.

Pertama, kami mempelajari apa sebenarnya daftar tertaut melingkar yang menyertakan beberapa fitur dan perbedaan paling umum dengan daftar tertaut konvensional. Kemudian, kami melihat cara menyisipkan, mencari, menghapus, dan melintasi item dalam implementasi daftar tertaut melingkar kami.

Seperti biasa, semua contoh yang digunakan dalam artikel ini tersedia di GitHub.