Как найти элемент max/min связанного списка

Question

У меня есть двойной список в моем случае. И я хочу найти элемент max и min. Поэтому я хочу использовать Коллекции, чтобы найти его. Вот мой код ниже для узла первый:

public class Node<T> { 
    Node<T> prev; 
    Node<T> next; 
    T data; 

    public Node(T _data) 
    { 
     data = _data; 
     prev = null; 
     next = null; 
    } 

    public Node(T _data, Node<T> _prev, Node<T> _next) 
    { 
     data = _data; 
     prev = _prev; 
     next = _next; 
    } 

    T getData() 
    { 
     return data; 
    } 

    public void setNext(Node<T> _next) 
    { 
     next = _next; 
    } 

    public void setPrev(Node<T> _prev) 
    { 
     prev = _prev; 
    } 

    public Node<T> getNext() 
    { 
     return next; 
    } 

    public Node<T> getPrev() 
    { 
     return prev; 
    } 
} 

А вот мой двусвязный класс List:

public class DoublyLinkedList<T> { 
    private Node<T> head; 
    private Node<T> tail; 
    int listCount = 0; 

    public void traverseF() 
    { 
     Node<T> temp = head; 

     while(temp != null) 
     { 
      System.out.print(temp.getData() + " "); 
      temp = temp.getNext(); 
     } 
    } 

    public void traverseB() 
    { 
     Node<T> temp = tail; 

     while(temp != null) 
     { 
      System.out.print(temp.getData() + " "); 
      temp = temp.getPrev(); 
     } 
    } 

    public void insertFirst(T data) 
    { 
     Node<T> temp = new Node<T>(data); 
     if(head == null) 
     { 
      head = temp; 
      tail = temp; 
      temp.setNext(null); 
      temp.setPrev(null); 
     } 
     else 
     { 
      temp.setNext(head); 
      head.setPrev(temp); 
      head = temp; 
     } 
    } 

} 

Итак, мой основной код:

import java.util.Collections; 


public class glavna { 

    public static void main(String[] args) { 
     DoublyLinkedList<Integer> DLL = new DoublyLinkedList<Integer>(); 

     DLL.insertFirst(32); 
     DLL.insertFirst(22); 
     DLL.insertFirst(55); 
     DLL.insertFirst(10); 

     DLL.traverseF(); 

     Integer max = Collections.max(DLL); 

    } 
} 

Как именно я вызовите метод Collections.max или Collections.min? Разве список не нужен только для поиска элементов max/min?

public T getMin() 
{ 
    Node<T> temp = head; 
    T min = head.getData(); 
    while(temp.getNext() != null) 
    { 
     if(temp.getData() < min) // error 
     { 
      //min = temp.getData(); 
     } 
    } 
} 

Answer 1

Для реализации getMin дженериков вам нужно, чтобы иметь возможность сравнить их. Вы можете, например, предоставлять собственные Comparator вашему методу:

public T getMin(Comparator<? super T> comparator) { 
    Node<T> temp = head.getNext(); 
    T min = head.getData(); 
    while(temp != null) { 
     T candidateValue = temp.getData(); 
     if (comparator.compare(candidateValue, min) < 0) { // equivalent to candidate < min 
      min = candidateValue; 
     } 
     temp = temp.getNext(); 
    } 
    return min; 
} 

Затем вызова метода для Integer:

getMin(new Comparator<Integer>() { 
    @Override 
    public int compare(Integer arg0, Integer arg1) { 
     return arg0.compareTo(arg1); 
    } 
}); 

Другой подход, чтобы сделать список только сохранить Comparable пункты:

public class DoublyLinkedList<T extends Comparable<? super T>> { 

а затем у вас есть getMin() метод compareTo способ:

public T getMin() { 
    Node<T> temp = head.getNext(); 
    T min = head.getData(); 
    while(temp != null) { 
     T candidateValue = temp.getData(); 
     if (candidateValue.compareTo(min) < 0) { // equivalent to candidate < min 
      min = candidateValue; 
     } 
     temp = temp.getNext(); 
    } 
    return min; 
} 

Второй подход менее многословным, так как это IntegerComparable (т.е. уже сравнивается с вами), поэтому вам не нужно менять какой-либо другой код.

Answer 2

Вы не являетесь коллекцией, поэтому вы не можете использовать Коллекции.

Answer 3

Метод Collections.max ожидает аргумент, который реализует Collection. Самый простой способ, вероятно, будет расширить AbstractCollection и добавить эти методы:

@Override 
public Iterator<T> iterator() { 
    return new Iterator<T>() { 
     private Node<T> node = head; 
     @Override 
     public boolean hasNext() { 
      return node != null; 
     } 

     @Override 
     public T next() { 
      T next = node.data; 
      node = node.getNext(); 
      return next; 
     } 
    }; 
} 

@Override 
public int size() { 
    int size = 0; 
    Node<T> node = head; 
    while (node != null) { 
     size++; 
     node = node.getNext(); 
    } 
    return size; 
}