Get the Middle Element of LinkedList in a Single Iteration in Java

Exercise:

Write a Java Program to get the middle element of linked list in a single iteration.

1.Get by single search

Click Here to View the Solution!
public 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(11);
        Node second = new Node(22);
        Node third = new Node(33);

        // 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("\nMiddle Element: " + ptr2.value);
    }
}
Click Here to View the Output!
LinkedList: 11 22 33 
 Middle Element: 22
Click Here to View the Explanation!
  • In this program, a LinkedList class is created with an object of Node class called head. Head represents the starting node of the linked list.
  • An inner class called Node is created next. This class has a variable called value and a Node object called next which represents the next node in the list.
  • The Node constructor assigns the argument to the value variable and the next object is assigned null initially.
  • In the main method, an object of LinkedList is created. The head of the list is initialized and rest of the nodes are instantiated.
  • Then, the nodes are linked together by assigning the following node as next node of the current node.
  • The linked list is then printed through traversal with the help of a Node object called pointer. It keeps executing loop till the next node of the current node equals to null.
  • For finding out the middle element in the list, two variables ptr1 and ptr2 are assigned the value of linked list’s head initially.
  • A loop executes till pt1.next equals to null.
  • The variable ptr1 is increased by 2 nodes while ptr2 is increased by 1 node in every iteration. Thus, when ptr1 reaches to the end, ptr2 will hold the middle element of the linked list.

2.Get using the LinkedList class

Click Here to View the Solution!
import java.util.LinkedList;

public class Main {
    public static void main(String[] args){

        // create a linked list using the LinkedList class
        LinkedList<String> languages = new LinkedList<>();

        // Add elements to LinkedList
        languages.add("Java");
        languages.addFirst("HTML");
        languages.addLast("Javascript");
        System.out.println("LinkedList: " + languages);

        // access middle element
        String middle = languages.get(languages.size()/2);
        System.out.println("Middle Element: " + middle);
    }
}
Click Here to View the Output!
LinkedList: [HTML, Java, Javascript]
 Middle Element: Java
Click Here to View the Explanation!
  • In this program, a built-in LinkedList interface is used for this data structure’s implementation.
  • It can be seen that a generic type <String> is used in conjunction with the LinkedList called languages.
  • Elements are added to this list using various methods for insertion and then the list is printed onto the screen.
  • Then the index in the middle of the list is retrieved using size()/2 which effectively divides the list into two parts.
  • The element present on this index is fetched through get() method and is stored in a variable called middle.
  • The value of middle is then printed to the screen.
%d bloggers like this: