D
D
dc65k2020-09-17 09:55:18
Java
dc65k, 2020-09-17 09:55:18

How to find middle element in LinkedList in one pass?

Hello. The question, of course, is very amateurish, but still I would be grateful for help in explaining.
I'm learning Java, went through the theoretical material on collections, and decided to practice.
I found a solution to this problem:
https://javarevisited.blogspot.com/2012/12/how-to-...
But, what I don't understand, here is my own implementation of the LinkedList class.
Accordingly, I have the following questions, first, why do your own implementation, second, how to solve this problem using import java.util.LinkedList;
To start like this:

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String args[]) {
        // creating LinkedList with 5 elements including head
        LinkedList linkedList = new LinkedList();

        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");
        linkedList.add("5");

Once again I repeat that the question is amateurish, but I would like to understand this point.

As for how to solve this problem:
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static List<String> findMiddleElementLinkedList(LinkedList<String> linkedList) {

        System.out.println("linkedList " + linkedList);

        return List.of(linkedList.get((linkedList.size() - 1) / 2));

    }

    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();

        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");
        linkedList.add("5");

        System.out.println(findMiddleElementLinkedList(linkedList));

    }
}


The first question remains: why in this example:
https://javarevisited.blogspot.com/2012/12/how-to-...
use your own implementation?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Dmitry Roo, 2020-09-17
@dc65k

The problem says "you need to find the middle element of LinkedList in one pass and you don't know the length of LinkedList."
Apparently, for this, their own implementation was written without the length method.
Solution with java.util.LinkedList, without using the length method:

public static void main(String args[]) {

        LinkedList<Integer> linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);
        linkedList.add(6);

        //finding middle element of LinkedList in single pass
        Iterator<Integer> current = linkedList.iterator();
        int length = 0;
        Iterator<Integer> middle = linkedList.iterator();
        Integer result = 0;

        while (current.hasNext()) {
            length = current.next();
            if (length % 2 == 0) {
                result = middle.next();
            }
        }

        if (length % 2 == 1) {
            result = middle.next();
        }

        System.out.println("length of LinkedList: " + length);
        System.out.println("middle element of LinkedList : " + result);

    }

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question