链表的通用类型实现和交换两个通用对象

Generic class implementing Comparable

My first question is how to correctly implement a Generic class that implements compareTo. My current class definition is:

我的第一个问题是如何正确实现实现compareTo的Generic类。我目前的课程定义是:

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

and my compareTo method is:

我的compareTo方法是:

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

1a. Are these definitions correct?

1A。这些定义是否正确?

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.

1B。我应该如何完成compareTo方法?我在网上找到的大部分文献都引用了方法本身使用的.compareTo(),这对我来说没有意义。

Swap two nodes in linked list:

My current method definition is

我目前的方法定义是

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

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?

是否可以在单链表实现中交换两个节点,或者交换方法本身是否需要链接列表的双向链接实现?

2 个解决方案

#1

1a. Are these definitions correct?

1A。这些定义是否正确?

Not completely. The definition you have for compareTo is declaring a type variable and this is probably wrong:

不完全的。你对compareTo的定义是声明一个类型变量,这可能是错误的:

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

(It actually shouldn't compile.)

(它实际上不应该编译。)

It should just be:

它应该只是:

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

1b. How should I complete my compareTo method?

1B。我应该如何完成compareTo方法?

That depends on what you're supposed to be comparing. Since you haven't specified, we don't know. ; )

这取决于你应该比较的东西。既然你没有说明,我们不知道。 ; )

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

我在网上找到的大部分文献都引用了方法本身使用的.compareTo(),这对我来说没有意义。

Here's an example of how this would typically be used:

以下是通常如何使用它的示例:

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

Now we can compare nodes, but it actually delegates to whatever the data is. We don't know or care what the data is (though it can't be null), just that it implements Comparable.

现在我们可以比较节点,但它实际上委托给任何数据。我们不知道或不关心数据是什么(尽管它不能为null),只是它实现了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?

2.是否可以在单链表实现中交换两个节点,或者交换方法本身是否需要链接列表的双向链接实现?

The hint here is that you don't need to swap nodes, just whatever their data is.

这里的提示是你不需要交换节点,只要他们的数据是什么。

#2

My current class definition is:

我目前的课程定义是:

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

and my compareTo method is:

我的compareTo方法是:

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

1a. Are these definitions correct?

1A。这些定义是否正确?

The class declaration looks fine. Not so much the compareTo() method. By specifying a type parameter on the method (<T extends Comparable<T>>) you are declaring a generic method, which is a different beast from an ordinary method that happens to rely on the class's type parameter. You want this, instead:

类声明看起来很好。而不是compareTo()方法。通过在方法上指定类型参数( >),您将声明一个泛型方法,这种方法与普通方法不同,后者恰好依赖于类的类型参数。你想要这个,而不是:

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.

1B。我应该如何完成compareTo方法?我在网上找到的大部分文献都引用了方法本身使用的.compareTo(),这对我来说没有意义。

You implement the method in whatever way makes sense, based on the fields of your Node class. If it's unclear to you what would make one Node less than another, then the class probably shouldn't be implementing Comparable.

您可以根据Node类的字段以任何有意义的方式实现该方法。如果你不清楚什么会使一个Node少于另一个Node,那么该类可能不应该实现Comparable。

Your confusion about use of .compareTo() is evident in the question itself. compareTo() is not meaningful as a method name outside the context of a particular class. There are a great many such methods, all different. In many cases it is sensible to use the compareTo() method of one class in the implementation of the compareTo() method of a different class.

关于使用.compareTo()的困惑在问题本身中很明显。 compareTo()作为特定类上下文之外的方法名称没有意义。有许多这样的方法,都各不相同。在许多情况下,在实现不同类的compareTo()方法时使用一个类的compareTo()方法是明智的。

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?

是否可以在单链表实现中交换两个节点,或者交换方法本身是否需要链接列表的双向链接实现?

It is possible to swap nodes in a singly-linked list. You might be able to swap just payloads, but if it is essential to swap the node objects themselves then you'll need to traverse the list to find each node's preceding node. Depending on details of your data structure, you might need special handling when one of the nodes to swap is the first in the list.

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