如何找到链接列表的最大/最小元素

Question

我在我的情况下有一个双向链表。我想找到最大和最小元素。所以我想用集合来找到它。这里是我下面的代码节点首先：

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; 
    } 
} 

，这里是我的双向链表类：

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方法？是不是只有找到最大/最小元素的列表？

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; 
} 

第二种方法不太详细，因为Integer是Comparable（即，已经为你实现了Comparable），所以你不需要改变任何其他代码。

Answer 2

你的列表不是Collection，所以你不能使用Collections。

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; 
}