如何查找链表的最大/最小元素

Question

我的案例中有一个双链表。我想找到最大和最小元素。所以我想使用集合来找到它。下面是我的Node first:代码

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，您需要能够对它们进行比较。例如，您可以为您的方法提供一个自定义比较器：

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

另一种方法是使您的列表只保留可比较项目：

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

您的列表不是集合，因此不能将集合与之一起使用。

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