En este ejemplo, aprenderemos a obtener el elemento medio de la lista vinculada en una sola iteración en Java.
Para comprender este ejemplo, asegúrese de visitar primero los siguientes tutoriales,
- Clase Java LinkedList
- Estructura de datos LinkedList
Ejemplo 1: obtenga el elemento medio de LinkedList en una sola búsqueda
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); ) )
Salida
LinkedList: 1 2 3 Elemento intermedio: 2
En el ejemplo anterior, hemos implementado la estructura de datos de lista enlazada en Java. Luego encontramos el elemento central de la lista vinculada en un solo ciclo. Fíjate en el código
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; ) )
Aquí, tenemos dos variables ptr1 y ptr2. Usamos estas variables para iterar a través de la lista vinculada.
En cada iteración, ptr1 accederá a los dos nodos y ptr2 accederá al único nodo de la lista enlazada.
Ahora, cuando ptr1 llegue al final de la lista enlazada, ptr2 estará en el medio. De esta manera, podemos obtener la mitad de la lista vinculada en una sola iteración.
Ejemplo 2: obtener el elemento medio de LinkedList usando la clase 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); ) )
Salida
LinkedList: (gato, perro, caballo) Elemento medio: perro
En el ejemplo anterior, hemos utilizado la LinkedListclase para implementar la estructura de datos de la lista vinculada. Note la expresión,
animals.get(animals.size()/2)
- size () / 2 - devuelve la posición del elemento medio
- get () : devuelve el elemento en la posición media
