CODEWITHSUNDEEP
javadata-structures
h4ck3d
h4ck3d

Reputation: 6364

How to find max and min element in a LinkedList most efficiently?

I have a linked list in Java ,say , LinkedList<T> list = new LinkedList<T>(); and I need to find the max / min element in it most efficiently , how can I do it?

How can I use Collections.max() function to find the max element from my linked list? What is the time complexity of this function ?

Upvotes: 1

Views: 14298

Answers (4)

Ritam Chakraborty
Ritam Chakraborty

Reputation: 495

You can also use stream.max() to get the max value of a LinkedList

LinkedList<Integer> linkedList = new LinkedList<>();

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

linkedList.stream().max(Integer::compareTo).ifPresent(System.out::println);

Output: 4

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533740

The time complexity is O(n) if you want it to be lower e.g. O(1) you need to use a different data structure such as a TreeSet.

how can i use Collections.max() for LinkedList 

List<Integer> list = ...
Integer max = Collections.max(list);

Upvotes: 6

Adam Sznajder
Adam Sznajder

Reputation: 9216

ArrayList<Integer> numbers = new ArrayList<Integer>();
/* fill with values */
Integer max = Collections.max(numbers);

Upvotes: 1

Amit Deshpande
Amit Deshpande

Reputation: 19185

Java Doc

This method iterates over the entire collection, hence it requires time proportional to the size of the collection. (O(n))

Usage

public class Test
{
  public static void main(String args[])
  {
    // create an LinkedList object
    LinkedList<Integer> list = new LinkedList<Integer>();

    // Add elements to LinkedList
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);

    //Use Max Method
    System.out.println(Collections.max(list));
}
}

Upvotes: 0

Related Questions