0

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.

Community
  • 1
  • 1
Sachin Thapa
  • 3,559
  • 4
  • 24
  • 42

3 Answers3

1

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:

Pacane
  • 20,273
  • 18
  • 60
  • 97
  • Appreciate your response, but what if the values are not sorted in LinkedList, just edited question.. thanks for your patience as well. – Sachin Thapa Sep 27 '13 at 04:22
  • Well you talked about "position wise", as if the value didn't matter. Does it? – Pacane Sep 27 '13 at 04:23
  • I actually could recall the solution from days of learning data structure to use multiple pointers, so the solution that I have pasted. – Sachin Thapa Sep 27 '13 at 04:24
  • @Sachin but the solution you posted doesn't take sorting into account either. Should it? – Jason Sep 27 '13 at 04:26
  • @Jason - Yes, requirement was to find element at nth position. – Sachin Thapa Sep 27 '13 at 04:38
  • 1
    Yes, but nth position in the sorted or unsorted collection? – Jason Sep 27 '13 at 04:41
  • @Jason - What you see in code pasted above, need to use list as is no sorting. – Sachin Thapa Sep 27 '13 at 13:54
  • @Pacane - Thanks for the solution and suggestion for merge sort, is there any utility class in Java which will do it for me. Also if you see edited list number's could be random. – Sachin Thapa Sep 27 '13 at 13:56
  • @Pacane - Thanks a lot, I assume the complexity for `Collections.sort(list);` is `O(nlog(n))`, but mid element in this case is 5. – Sachin Thapa Sep 27 '13 at 15:44
  • Yeah it's about `O(nlogn)`, and if your mid element is 5, you sort, so there goes `O(nlogn)` and then you go all the way to the mid element, so `O(n)` (since the LinkedList doesn't support random access). So if you do sort + get to the element, the max complexity remains `O(nlogn)`. – Pacane Sep 27 '13 at 15:50
0

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);
kai
  • 6,702
  • 22
  • 38
0

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);
}
rohit k.
  • 128
  • 1
  • 14
  • Thanks for solution but you have mentioned `//Any sort algorithm suitable for integer arrays`, please provide some example or code. – Sachin Thapa Sep 27 '13 at 13:58
  • I just found another way. I have edited my answer accordingly. Once the list is sorted you can extract any value you want in ascending order. – rohit k. Oct 09 '13 at 04:26