Temukan Elemen Tengah dari Daftar Tertaut di Java

1. Ikhtisar

Dalam tutorial ini, kami akan menjelaskan cara menemukan elemen tengah dari daftar tertaut di Java.

Kami akan memperkenalkan masalah utama di bagian selanjutnya, dan kami akan menunjukkan pendekatan berbeda untuk menyelesaikannya.

2. Melacak Ukuran

Masalah ini dapat dengan mudah diselesaikan hanya dengan melacak ukuran saat kita menambahkan elemen baru ke daftar . Jika kita tahu ukurannya, kita juga tahu letak elemen tengahnya, jadi solusinya sepele.

Mari kita lihat contoh penggunaan implementasi Java dari LinkedList :

public static Optional findMiddleElementLinkedList( LinkedList linkedList) { if (linkedList == null || linkedList.isEmpty()) { return Optional.empty(); } return Optional.of(linkedList.get( (linkedList.size() - 1) / 2)); }

Jika kita memeriksa kode internal kelas LinkedList , kita dapat melihat bahwa dalam contoh ini kita hanya menelusuri daftar sampai kita mencapai elemen tengah:

Node node(int index) { if (index > 1)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }

3. Menemukan Bagian Tengah Tanpa Mengetahui Ukurannya

Sangat umum bahwa kami menghadapi masalah di mana kami hanya memiliki simpul kepala dari daftar tertaut, dan kami perlu menemukan elemen tengah. Dalam kasus ini, kami tidak mengetahui ukuran daftarnya, yang membuat masalah ini lebih sulit untuk dipecahkan.

Kami akan menunjukkan di bagian selanjutnya beberapa pendekatan untuk memecahkan masalah ini, tetapi pertama-tama, kami perlu membuat kelas untuk mewakili simpul dari daftar.

Mari buat kelas Node , yang menyimpan nilai String :

public static class Node { private Node next; private String data; // constructors/getters/setters public boolean hasNext() { return next != null; } public void setNext(Node next) { this.next = next; } public String toString() { return this.data; } }

Selain itu, kami akan menggunakan metode helper ini dalam kasus pengujian kami untuk membuat daftar tertaut tunggal hanya menggunakan node kami:

private static Node createNodesList(int n) { Node head = new Node("1"); Node current = head; for (int i = 2; i <= n; i++) { Node newNode = new Node(String.valueOf(i)); current.setNext(newNode); current = newNode; } return head; }

3.1. Menemukan Ukurannya Terlebih Dahulu

Pendekatan paling sederhana untuk mengatasi masalah ini adalah menemukan ukuran daftar terlebih dahulu, dan setelah itu ikuti pendekatan yang sama yang kita gunakan sebelumnya - untuk mengulang hingga elemen tengah.

Mari kita lihat solusi ini beraksi:

public static Optional findMiddleElementFromHead(Node head) { if (head == null) { return Optional.empty(); } // calculate the size of the list Node current = head; int size = 1; while (current.hasNext()) { current = current.next(); size++; } // iterate till the middle element current = head; for (int i = 0; i < (size - 1) / 2; i++) { current = current.next(); } return Optional.of(current.data()); }

Seperti yang bisa kita lihat, kode ini mengulangi daftar dua kali. Oleh karena itu, solusi ini memiliki kinerja yang buruk dan tidak disarankan .

3.2. Menemukan Elemen Tengah dalam Satu Kali Secara Iteratif

Kami sekarang akan meningkatkan solusi sebelumnya dengan menemukan elemen tengah dengan hanya satu iterasi di atas daftar.

Untuk melakukan itu secara berulang, kita membutuhkan dua petunjuk untuk mengulang melalui daftar pada waktu yang sama. Satu penunjuk akan memajukan 2 node di setiap iterasi, dan penunjuk lainnya hanya akan memajukan satu node per iterasi .

Saat penunjuk yang lebih cepat mencapai akhir daftar, penunjuk yang lebih lambat akan berada di tengah:

public static Optional findMiddleElementFromHead1PassIteratively(Node head) { if (head == null) { return Optional.empty(); } Node slowPointer = head; Node fastPointer = head; while (fastPointer.hasNext() && fastPointer.next().hasNext()) { fastPointer = fastPointer.next().next(); slowPointer = slowPointer.next(); } return Optional.ofNullable(slowPointer.data()); }

Kami dapat menguji solusi ini dengan pengujian unit sederhana menggunakan daftar dengan elemen ganjil dan genap:

@Test public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( reateNodesList(4)).get()); }

3.3. Menemukan Elemen Tengah dalam Satu Umpan Secara Rekursif

Cara lain untuk mengatasi masalah ini dalam sekali jalan adalah dengan menggunakan rekursi. Kita dapat mengulang sampai akhir daftar untuk mengetahui ukuran dan, dalam callback, kita hanya menghitung sampai setengah dari ukuran tersebut.

Untuk melakukan ini di Java, kita akan membuat kelas tambahan untuk menyimpan referensi ukuran daftar dan elemen tengah selama eksekusi semua panggilan rekursif:

private static class MiddleAuxRecursion { Node middle; int length = 0; }

Sekarang, mari kita terapkan metode rekursif:

private static void findMiddleRecursively( Node node, MiddleAuxRecursion middleAux) { if (node == null) { // reached the end middleAux.length = middleAux.length / 2; return; } middleAux.length++; findMiddleRecursively(node.next(), middleAux); if (middleAux.length == 0) { // found the middle middleAux.middle = node; } middleAux.length--; }

Dan terakhir, mari buat metode yang memanggil metode rekursif:

public static Optional findMiddleElementFromHead1PassRecursively(Node head) { if (head == null) { return Optional.empty(); } MiddleAuxRecursion middleAux = new MiddleAuxRecursion(); findMiddleRecursively(head, middleAux); return Optional.of(middleAux.middle.data()); }

Sekali lagi, kami dapat mengujinya dengan cara yang sama seperti yang kami lakukan sebelumnya:

@Test public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(4)).get()); }

4. Kesimpulan

Di artikel ini, kami telah memperkenalkan masalah menemukan elemen tengah dari daftar tertaut di Java, dan kami telah menunjukkan cara berbeda untuk menyelesaikannya.

Kami telah memulai dari pendekatan paling sederhana di mana kami melacak ukurannya, dan setelah itu, kami melanjutkan dengan solusi untuk menemukan elemen tengah dari simpul kepala daftar.

Seperti biasa, kode sumber lengkap dari contoh tersedia di GitHub.