Java >> Java tutorial >  >> Java

Java-program til at finde det midterste element i en sammenkædet liste

Java

I denne vejledning vil vi se, hvordan du finder det midterste element i en sammenkædet liste i java. LinkedList er en lineær datastruktur, hvor elementerne ikke er gemt på sammenhængende steder, og hvert element er et separat objekt med en datadel og adressedel. Hvert element er kendt som en node. På grund af dynamikken og lette indsættelser og sletninger foretrækkes de frem for arrays. Men før du går videre, hvis du ikke er bekendt med konceptet med den linkede liste i java, så tjek artiklen om Linked List i Java.

Input: Indtast Linked List-elementerne:6 7 8 4 5

Output: Det midterste element i den linkede liste er:8

Dette kan gøres ved at bruge følgende metoder:

Fremgangsmåde 1:Brug af metoden get()

Fremgangsmåde 2:Find det midterste element i et enkelt pas

Lad os se på hver af disse tilgange for en bedre forståelse.

Program 1:Java-program til at finde det midterste element i en sammenkædet liste

I dette program vil vi se, hvordan man finder det midterste element i en sammenkædet liste.

Algorithme:

  1. Start
  2. Opret en linket liste over heltaltyper ved hjælp af den linkede listeklasse.
  3. Tilføj nu elementer til den linkede liste.
  4. Først skal du finde det midterste indeks på den linkede liste ved at bruge formlen længde med 2.
  5. Brug metoden get(index) til at finde elementet.
  6. Udskriv det midterste element.
  7. Stop.

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

//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);
    }
}


LinkedList:[3, 2, 5, 6, 8, 13, 18]
Mellemelement:6

Program 2:Java-program til at finde det midterste element i en sammenkædet liste

I dette program vil vi se, hvordan man finder det midterste element i en sammenkædet liste.

Algorithme:

  1. Start
  2. Opret en linket liste over strengtyper ved hjælp af den linkede listedatastruktur.
  3. Tilføj nu elementer til den linkede liste.
  4. Først skal du finde længden af ​​den linkede liste.
  5. Brug to pointere til det samme.
  6. Den første markør vil øges ved hver iteration, mens den anden markør vil blive inkrementeret hver anden iteration.
  7. Når den første markør peger mod slutningen af ​​en linket liste, vil den anden markør pege på det midterste element af den linkede liste.
  8. Udskriv det midterste element.
  9. Stop.

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

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;
        }
    }
}


Det midterste element på den linkede liste:Orange


Java tag