Java >> Tutoriel Java >  >> Java

Programme Java pour trouver l'élément du milieu dans une liste chaînée

Java

Dans ce tutoriel, nous allons voir comment trouver l'élément du milieu d'une liste chaînée en java. LinkedList est une structure de données linéaire où les éléments ne sont pas stockés dans des emplacements contigus et chaque élément est un objet séparé avec une partie données et une partie adresse. Chaque élément est appelé nœud. En raison de la dynamique et de la facilité des insertions et des suppressions, ils sont préférés aux tableaux. Mais avant d'aller plus loin, si vous n'êtes pas familier avec le concept de liste chaînée en Java, consultez l'article sur la liste chaînée en Java.

Entrée : Saisissez les éléments de la liste chaînée :6 7 8 4 5

Sortie : L'élément du milieu de la liste chaînée est :8

Cela peut être fait en utilisant les méthodes suivantes :

Approche 1 :Utiliser la méthode get()

Approche 2 :Trouver l'élément central en un seul passage

Examinons chacune de ces approches pour une meilleure compréhension.

Programme 1 :Programme Java pour trouver l'élément du milieu dans une liste chaînée

Dans ce programme, nous verrons comment trouver l'élément du milieu dans une liste chaînée.

Algorithme :

  1. Démarrer
  2. Créez une liste chaînée de types d'entiers à l'aide de la classe de liste chaînée.
  3. Ajoutez maintenant des éléments à la liste liée.
  4. Tout d'abord, trouvez l'index du milieu de la liste chaînée en utilisant la formule de longueur par 2.
  5. Utilisez la méthode get(index) pour trouver l'élément.
  6. Imprimez l'élément du milieu.
  7. Arrêtez.

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

//Java Program to Find the Middle Element in a Linked List
import java.util.LinkedList;
public class Main 
{
  public static void main(String[] args)
  {
    // create a linked list using the LinkedList class
    LinkedList<Integer> ll = new LinkedList<>();
    // Add elements to LinkedList
    ll.add(2);
    ll.addFirst(3);
    ll.addLast(5);
    ll.addLast(6);
    ll.addLast(8);
    ll.addLast(13);
    ll.addLast(18);
    System.out.println("LinkedList: " + ll);
    // access middle element
    int middle = ll.get(ll.size()/2);
    System.out.println("Middle Element: " + middle);
    }
}


Liste liée :[3, 2, 5, 6, 8, 13, 18]
Élément du milieu :6

Programme 2 :Programme Java pour trouver l'élément du milieu dans une liste chaînée

Dans ce programme, nous verrons comment trouver l'élément du milieu dans une liste chaînée.

Algorithme :

  1. Démarrer
  2. Créez une liste liée de types de chaînes à l'aide de la structure de données de la liste liée.
  3. Ajoutez maintenant des éléments à la liste liée.
  4. D'abord, trouvez la longueur de la liste chaînée.
  5. Utilisez deux pointeurs pour la même chose.
  6. Le premier pointeur s'incrémentera à chaque itération tandis que le second pointeur sera incrémenté à chaque seconde itération.
  7. Lorsque le premier pointeur pointe vers la fin d'une liste liée, le deuxième pointeur pointe vers l'élément du milieu de la liste liée.
  8. Imprimez l'élément du milieu.
  9. Arrêtez.

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

public class LinkedListTest 
{
    public static void main(String args[]) 
    {
        //creating a LinkedList
      LinkedList linkedList = new LinkedList();
      LinkedList.Node head = linkedList.head();
      linkedList.add( new LinkedList.Node("Apple"));
      linkedList.add( new LinkedList.Node("Mango"));
      linkedList.add( new LinkedList.Node("Orange"));
      linkedList.add( new LinkedList.Node("Gauva"));
      linkedList.add( new LinkedList.Node("Litchi"));
      //finding middle element of LinkedList in single pass
      LinkedList.Node current = head;
      int length = 0;
      LinkedList.Node middle = head;
      while(current.next() != null){
          length++;
          if(length%2 ==0){
              middle = middle.next();
          }
          current = current.next();
      }
      if(length%2 == 1){
          middle = middle.next();
      }
      System.out.println("The middle element of the Linked List: "+ middle);
    } 
}
class LinkedList{
    private Node head;
    private Node tail;
    public LinkedList(){
        this.head = new Node("head");
        tail = head;
    }
    public Node head(){
        return head;
    }
    public void add(Node node){
        tail.next = node;
        tail = node;
    }
    public static class Node{
        private Node next;
        private String data;
        public Node(String data){
            this.data = data;
        }
        public String data() {
            return data;
        }
        public void setData(String data) {
            this.data = data;
        }
        public Node next() {
            return next;
        }
        public void setNext(Node next) {
            this.next = next;
        }
        public String toString(){
            return this.data;
        }
    }
}


L'élément du milieu de la liste chaînée :Orange


Balise Java