Trong ví dụ này, chúng ta sẽ học cách lấy phần tử giữa của danh sách liên kết trong một lần lặp duy nhất trong Java.
Để hiểu ví dụ này, trước tiên hãy đảm bảo rằng bạn truy cập các hướng dẫn sau,
- Lớp Java LinkedList
- Cấu trúc dữ liệu LinkedList
Ví dụ 1: Lấy phần tử giữa của LinkedList trong một lần tìm kiếm
class LinkedList ( // create an object of Node class // represent the head of the linked list Node head; // static inner class static class Node ( int value; // connect each node to next node Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( // create an object of LinkedList LinkedList linkedList = new LinkedList(); // assign values to each linked list node linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // connect each node of linked list to next node linkedList.head.next = second; second.next = third; // print the linked list Node pointer = linkedList.head; System.out.print("LinkedList: " ); while (pointer != null) ( System.out.print(pointer.value + " "); pointer = pointer.next; ) // Find the middle element Node ptr1 = linkedList.head; Node ptr2 = linkedList.head; while (ptr1.next != null) ( // increase the ptr1 by 2 and ptr2 by 1 // if ptr1 points to last element // ptr2 will points to middle element ptr1 = ptr1.next; if(ptr1.next !=null) ( ptr1 = ptr1.next; ptr2 = ptr2.next; ) ) System.out.println("Middle Element: " + ptr2.value); ) )
Đầu ra
LinkedList: 1 2 3 Phần tử giữa: 2
Trong ví dụ trên, chúng ta đã triển khai cấu trúc dữ liệu danh sách liên kết trong Java. Sau đó, chúng tôi tìm phần tử giữa của danh sách liên kết trong một vòng lặp. Lưu ý mã,
while (ptr1.next != null) ( // increase the ptr1 by 2 and ptr2 by 1 // if ptr1 points to last element // ptr2 will points to middle element ptr1 = ptr1.next; if(ptr1.next !=null) ( ptr1 = ptr1.next; ptr2 = ptr2.next; ) )
Ở đây, chúng ta có hai biến ptr1 và ptr2. Chúng tôi sử dụng các biến này để lặp qua danh sách được liên kết.
Trong mỗi lần lặp, ptr1 sẽ truy cập vào hai nút và ptr2 sẽ truy cập vào nút đơn của danh sách liên kết.
Bây giờ, khi ptr1 đến cuối danh sách được liên kết, ptr2 sẽ ở giữa. Bằng cách này, chúng ta có thể lấy giữa danh sách được liên kết trong một lần lặp duy nhất.
Ví dụ 2: Lấy phần tử giữa của LinkedList bằng lớp LinkedList
import java.util.LinkedList; class Main ( public static void main(String() args)( // create a linked list using the LinkedList class LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.addFirst("Cat"); animals.addLast("Horse"); System.out.println("LinkedList: " + animals); // access middle element String middle = animals.get(animals.size()/2); System.out.println("Middle Element: " + middle); ) )
Đầu ra
LinkedList: (Cat, Dog, Horse) Phần tử giữa: Dog
Trong ví dụ trên, chúng ta đã sử dụng LinkedListlớp để triển khai cấu trúc dữ liệu danh sách liên kết. Chú ý biểu thức,
animals.get(animals.size()/2)
- size () / 2 - trả về vị trí của phần tử giữa
- get () - trả về phần tử ở vị trí giữa
