Membalik Daftar Tertaut di Java

1. Perkenalan

Dalam tutorial ini, kami akan menerapkan dua algoritma pembalikan daftar tertaut di Java.

2. Struktur Data Daftar Tertaut

Daftar tertaut adalah struktur data linier di mana penunjuk di setiap elemen menentukan urutannya. Setiap elemen dari daftar tertaut berisi bidang data untuk menyimpan data daftar dan bidang penunjuk untuk menunjuk ke elemen berikutnya dalam urutan. Juga, kita dapat menggunakan penunjuk kepala untuk menunjuk ke elemen awal dari daftar tertaut:

Setelah kita membalikkan daftar tertaut, kepala akan menunjuk ke elemen terakhir dari daftar tertaut asli, dan penunjuk setiap elemen akan menunjuk ke elemen sebelumnya dari daftar tertaut asli:

Di Java, kami memiliki kelas LinkedList untuk menyediakan implementasi daftar tertaut ganda dari antarmuka List dan Deque . Namun, kami akan menggunakan struktur data daftar tertaut tunggal umum dalam tutorial ini.

Mari kita mulai dengan kelas ListNode untuk mewakili elemen dari daftar tertaut:

public class ListNode { private int data; private ListNode next; ListNode(int data) { this.data = data; this.next = null; } // standard getters and setters }

Kelas ListNode memiliki dua bidang:

  • Nilai integer untuk merepresentasikan data elemen
  • Sebuah pointer / referensi ke elemen berikutnya

Daftar tertaut mungkin berisi beberapa objek ListNode . Misalnya, kita dapat membuat contoh daftar tertaut di atas dengan sebuah loop:

ListNode constructLinkedList() { ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i++) { ListNode node = new ListNode(i); if (head == null) { head = node; } else { tail.setNext(node); } tail = node; } return head; }

3. Implementasi Algoritma Iteratif

Mari menerapkan algoritma iteratif di Java:

ListNode reverseList(ListNode head) { ListNode previous = null; ListNode current = head; while (current != null) { ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; } return previous; }

Dalam algoritma iteratif ini, kami menggunakan dua variabel ListNode , sebelumnya dan saat ini , untuk mewakili dua elemen yang berdekatan dalam daftar tertaut. Untuk setiap iterasi, kami membalikkan kedua elemen ini dan kemudian beralih ke dua elemen berikutnya.

Pada akhirnya, penunjuk saat ini akan menjadi nol, dan penunjuk sebelumnya akan menjadi elemen terakhir dari daftar tertaut lama. Oleh karena itu, sebelumnya juga merupakan penunjuk kepala baru dari daftar tertaut yang dibalik, dan kami mengembalikannya dari metode.

Kami dapat memverifikasi implementasi berulang ini dengan pengujian unit sederhana:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

Dalam pengujian unit ini, pertama-tama kami membuat contoh daftar tertaut dengan lima node. Selain itu, kami memverifikasi bahwa setiap node dalam daftar tertaut berisi nilai data yang benar. Kemudian, kami memanggil fungsi iteratif untuk membalikkan daftar tertaut. Terakhir, kami memeriksa daftar tertaut yang dibalik untuk memastikan datanya dibalik seperti yang diharapkan.

4. Implementasi Algoritma Rekursif

Sekarang, mari kita terapkan algoritma rekursif di Java:

ListNode reverseListRecursive(ListNode head) { if (head == null) { return null; } if (head.getNext() == null) { return head; } ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; }

Dalam fungsi reverseListRecursive , kita secara rekursif mengunjungi setiap elemen dalam daftar tertaut hingga kita mencapai yang terakhir. Elemen terakhir ini akan menjadi kepala baru dari daftar tertaut yang dibalik. Juga, kami menambahkan elemen yang dikunjungi ke akhir daftar tertaut yang sebagian dibalik.

Demikian pula, kita dapat memverifikasi implementasi rekursif ini dengan pengujian unit sederhana:

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

5. Kesimpulan

Dalam tutorial ini, kami menerapkan dua algoritma untuk membalikkan daftar tertaut. Seperti biasa, kode sumber artikel tersedia di GitHub.