In dit voorbeeld zullen we leren om het middelste element van de gekoppelde lijst in één iteratie in Java te krijgen.
Om dit voorbeeld te begrijpen, moet u eerst de volgende tutorials bezoeken,
- Java LinkedList-klasse
- LinkedList-gegevensstructuur
Voorbeeld 1: verkrijg het middelste element van LinkedList in één zoekopdracht
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); ) )
Uitvoer
LinkedList: 1 2 3 Middenelement: 2
In het bovenstaande voorbeeld hebben we de datastructuur van de gekoppelde lijst in Java geïmplementeerd. We vinden dan het middelste element van de gekoppelde lijst in een enkele lus. Let op de code,
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; ) )
Hier hebben we twee variabelen ptr1 en ptr2. We gebruiken deze variabelen om de gekoppelde lijst te doorlopen.
Bij elke iteratie krijgt de ptr1 toegang tot de twee knooppunten en krijgt de ptr2 toegang tot het enkele knooppunt van de gekoppelde lijst.
Nu, wanneer de ptr1 het einde van de gekoppelde lijst bereikt, staat de ptr2 in het midden. Op deze manier zijn we in staat om het midden van de gekoppelde lijst in één iteratie te krijgen.
Voorbeeld 2: verkrijg het middelste element van LinkedList met behulp van de klasse 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); ) )
Uitvoer
LinkedList: (Cat, Dog, Horse) Middle Element: Dog
In het bovenstaande voorbeeld hebben we de LinkedListklasse gebruikt om de datastructuur van de gekoppelde lijst te implementeren. Let op de uitdrukking,
animals.get(animals.size()/2)
- size () / 2 - geeft de positie van het middelste element terug
- get () - retourneert het element in de middelste positie
