Java Program to Find the Middle Element in a Linked List

In this tutorial, we will see how to find the middle element of a linked list in java. LinkedList is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. But before moving further, if you are not familiar with the concept of the linked list in java, then do check the article on Linked List in Java.

Input: Enter the Linked List elements: 6 7 8 4 5

Output: The middle element of the Linked List is: 8

This can be done by using the following methods:

Approach 1: Using the get() method

Approach 2: Finding the Middle Element in a Single Pass

Let us look at each of these approaches for a better understanding.

Program 1: Java Program to Find the Middle Element in a Linked List

In this program, we will see how to find the middle element in a linked list.

Algorithm:

1. Start
2. Create a linked list of integer types using the linked list class.
3. Now add elements to the linked list.
4. First, find the middle index of the linked list by using the length by 2 formula.
5. Use the get(index) method to find the element.
6. Print the middle element.
7. Stop.

Let us look at the below example for a better understanding of the above algorithm.

//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]
Middle Element: 6

Program 2: Java Program to Find the Middle Element in a Linked List

In this program, we will see how to find the middle element in a linked list.

Algorithm:

1. Start
2. Create a linked list of string types using the linked list data structure.
3. Now add elements to the linked list.
4. First, find the length of the linked list.
5. Use two pointers for the same.
6. The first pointer will increment on each iteration whereas the second pointer will be incremented every second iteration.
7. When the first pointer will point to the end of a linked list, the second pointer will be pointing to the middle element of the linked list.
8. Print the middle element.
9. Stop.

Let us look at the below example for a better understanding of the above algorithm.

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

The middle element of the Linked List: Orange