java - 如何找到链表的最大/最小元素

Question

我的例子有一个双向链表。我想找到最大和最小元素。所以我想使用集合来找到它。首先是我的 Node 代码:

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)，因此您不需要更改任何其他代码。