链表的泛型实现和交换两个泛型对象

Question

通用 class 实现 Comparable

我的第一个问题是如何正确实现实现 compareTo 的泛型 class。我当前的 class 定义是：

public static class Node<T> implements Comparable<Node<T>>{

我的 compareTo 方法是：

public <T extends Comparable<T>> int compareTo(Node<T> n){

1a。这些定义正确吗？

1b。我应该如何完成我的 compareTo 方法？我在网上找到的许多文献都提到了在方法本身中使用 .compareTo()，这对我来说没有意义。

交换链表中的两个节点：

我当前的方法定义是

public void swap(Node<T> n1, Node<T> n2){
    // swap
}

是否可以在单链表实现中交换两个节点，或者交换方法是否固有地需要链表的双链实现？

Answer 1

1a. Are these definitions correct?

不完全是。您对 compareTo 的定义是声明一个类型变量，这可能是错误的：

public <T extends Comparable<T>> int compareTo(Node<T> n){

（实际上不应该编译。）

应该是：

@Override
public int compareTo(Node<T> n){

1b. How should I complete my compareTo method?

这取决于您要比较的内容。因为你没有具体说明，我们不知道。 ; )

Much of the literature I have found online has referenced using .compareTo() within the method itself, which does not make sense to me.

这是一个典型用法的例子：

// saying T must also be Comparable:
// it's possible you are supposed to do
// this for your own Node declaration too
//         vvvvvvvvvvvvvvvvvvvvvvv
class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
    T data;

    @Override
    public int compareTo(Node<T> that) {
        return this.data.compareTo( that.data );
    }
}

现在我们可以比较节点，但它实际上委托给了任何数据。我们不知道也不关心数据是什么（尽管它不能为空），只是它实现了 Comparable.

2. Is it possible to swap two nodes in a singly linked list implementation, or does the swap method inherently require a doubly linked implementation of a linked list?

这里的提示是您不需要交换节点，无论它们的数据是什么。

Answer 2

My current class definition is:

public static class Node<T> implements Comparable<Node<T>>{

and my compareTo method is:

public <T extends Comparable<T>> int compareTo(Node<T> n){

1a. Are these definitions correct?

class 声明看起来不错。与其说是 compareTo() 方法。通过在方法 (<T extends Comparable<T>>) 上指定类型参数，您声明了一个泛型方法，它与恰好依赖于 class 的普通方法不同。 =37=]类型参数。你想要这个，而不是：

public int compareTo(Node<T> n){

1b. How should I complete my compareTo method? Much of the literature I have found online has referenced using .compareTo() within the method itself, which does not make sense to me.

您可以根据 Node class 的字段以任何有意义的方式实施该方法。如果您不清楚什么会使 Node 比另一个少，那么 class 可能不应该实施 Comparable.

您对使用 .compareTo() 的困惑在问题本身中很明显。 compareTo() 作为特定 class 上下文之外的方法名称没有意义。这样的方法有很多，各不相同。在很多情况下，在实现一个不同[=39=的compareTo()方法时，使用一个class的compareTo()方法是明智的].

Is it possible to swap two nodes in a singly linked list implementation, or does the swap method inherently require a doubly linked implementation of a linked list?

可以在单链表中交换节点。您可能只能交换有效负载，但如果必须交换节点对象本身，那么您将需要遍历列表以找到每个节点的前一个节点。根据您的数据结构的详细信息，当要交换的节点之一是列表中的第一个时，您可能需要特殊处理。

链表的泛型实现和交换两个泛型对象

Generic type implementation of linked list and swapping two generic objects

java

generics

interface

comparable

通用 class 实现 Comparable

交换链表中的两个节点：