CODEWITHSUNDEEP
javaarrays
Sachin Thapa
Sachin Thapa

Reputation: 3709

Finding middle and third element of Arraylist in Java using multiple Iterators

There has been some questions already on SO to find middle element.

How to find the kth largest element in an unsorted array of length n in O(n)?

Here is a different approach using multiple Iterators, can you please help to compare this in terms of complexity ? 

package linkedlist;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> l = new LinkedList<String>();
    l.add("11");
    l.add("2");
    l.add("3");
    l.add("14");
    l.add("5");
    l.add("16");
    l.add("7");
    l.add("18");
    l.add("9");

        int i = 1;

        Iterator<String> it = l.iterator();
        Iterator<String> it1 = l.iterator();
        Iterator<String> it2 = l.iterator();

        String mid = null;
            String third = null;

        while(it.hasNext()){
            i++;
            it.next();
            if(i%2==0){
                mid = it1.next();
            }
            if(i%3==0){
                third = it2.next();
            }
        }

        System.out.println(mid);
        System.out.println(third);
    }
}

Also if you could suggest better way of writing this using utility classes provided by Java, trying to avoid writing custom code for Node etc ?

Any help would be highly appreciated.

Upvotes: 0

Views: 3001

Answers (3)

rohit k.
rohit k.

Reputation: 128

Provided your list will contain only integers, you can use following solution. This inbuilt sort uses TimSort (derived from Merge sort) :

public class sortList {

public static void main(String[] args) {

    LinkedList<Integer> l = new LinkedList<Integer>();
    Collections.sort(l);
}

Upvotes: 0

Pacane
Pacane

Reputation: 21471

Given that you want to have it position-wise, here's the code post the n-th element.

List<String> alist = new LinkedList<String>();
alist.add("0");
alist.add("1");
alist.add("2");

String value = alist.get(1); // returns "1"

If you want the mid element, I would suggest dividing by 2 the size of the list to get the index

edit:

As much as I think you don't want your list to be sorted, I think (if we think about the complexity), it would be for the best.

In fact, if you use a merge-sort it should be in O(nlog(n)) and then you could use the method I provided you which is (I believe) in O(n) since your data structure is not indexed. So basically you would find the n-th element of your list (given there's no duplicates) in O(nlogn)

edit2:

For the sort, I'd just use

Collections.sort(list);

According to the docs:

The sort operation uses a slightly optimized merge sort algorithm that is fast and stable:

Upvotes: 1

kai
kai

Reputation: 6887

I think i still dont understand this question. Otherwise this is the solution to get the middle index of a List. This work also if the size is odd.

String mid; 
mid=l.get(((l.size())-(l.size()%2))/2);

Upvotes: 0

Related Questions