I dette eksempel lærer vi at få det midterste element på den linkede liste i en enkelt iteration i Java.
For at forstå dette eksempel skal du først besøge følgende tutorials,
- Java LinkedList-klasse
- LinkedList Datastruktur
Eksempel 1: Få det midterste element i LinkedList i en enkelt søgning
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); ) )
Produktion
LinkedList: 1 2 3 Mellemelement: 2
I ovenstående eksempel har vi implementeret den sammenkædede liste datastruktur i Java. Vi finder derefter det midterste element på den linkede liste i en enkelt sløjfe. Bemærk koden,
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; ) )
Her har vi to variabler ptr1 og ptr2. Vi bruger disse variabler til at gentage gennem den linkede liste.
I hver iteration får ptr1 adgang til de to knudepunkter, og ptr2 får adgang til den enkelte knude på den linkede liste.
Nu, når ptr1 når slutningen af den linkede liste, vil ptr2 være i midten. På denne måde er vi i stand til at få midten af den sammenkædede liste i en enkelt iteration.
Eksempel 2: Få det midterste element i LinkedList ved hjælp af klassen 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); ) )
Produktion
LinkedList: (Kat, Hund, Hest) Mellemelement: Hund
I eksemplet ovenfor har vi brugt LinkedList
klassen til at implementere den sammenkædede liste datastruktur. Bemærk udtrykket,
animals.get(animals.size()/2)
- størrelse () / 2 - returnerer positionen for det midterste element
- get () - returnerer elementet i midterpositionen