如何在 Java 中对我的自定义泛型类型链表进行排序

Question

我正在用java编写我自己的通用类型的链表，而不是使用java集合链表。 链表的 add 方法由以下代码组成：

public void add(T item, int position) {
  Node<T> addThis = new Node<T>(item);
  Node<T> prev = head;
  int i;
  if(position <= 0) {
    System.out.println("Error: Cannot add element before position 1.");
  }
  else if(position == 1) {
    addThis.setNext(head);
    head = addThis;
  } else {
    for(i = 1; i < position-1; i++) {
      prev = prev.getNext();
      if(prev == null) {
        System.out.println("Cannot add beyond end of list");
      }
    } // end for
    addThis.setNext(prev.getNext());
    prev.setNext(addThis);
  }
} // end add

我将如何使当我添加新项目时，该项目与另一个项目进行比较并按字母顺序插入？ 我已经考虑过使用compareTo，但我不知道该怎么做。

谢谢

编辑：我有各种类：我有一个名为 Dvd 的类，它包含标题（字符串）的方法和变量以及该标题（int）的副本数。我还有一个链表类、一个列表接口、一个节点类和一个主类。

Answer 1

您的实现是否扩展了 java.util.List 接口？

您可以简单地将对象添加到列表中，然后使用 Collections.sort（） 对列表进行排序吗？

Answer 2

您提到使用泛型，但随后提到按字母顺序对它们进行排序。 泛型不一定是字符串，它们用于表示任何类型的类型，而排序属性（如按字母顺序）表示字母字符。 我的答案假设您期望具有字母性质的 T 类型的通用对象。 在我的示例中，我只使用String

您可以将代码设置为搜索要添加自己的位置，而不是提供它。

public void add(T item) {
    Node<T> addThis = new Node<T>(item);
    Node<T> itr = head;
    while (itr.hasNext()) {
        if (addThis.compareTo(itr.getNext()) <= 0) { // itr > addThis
            addThis.setNext(itr.getNext());
            itr.setNext(addThis);
            return;
        }
        itr = itr.getNext();
    }
    addThis.setNext(null);
    itr.setNext(addThis);
    return;
} // end add

然后在Node类中，您可以实现Interface Comparable。 我假设您存储了一个字符串，因为您询问了字母顺序。 此问题解释了按字母顺序比较字符串。

class Node implements Comparable<Node> {

    String value;  // ASSUMING YOU ARE USING A STRING AS YOUR GENERIC TYPE T
    @Override
    public int compareTo(Node otherNode) {
        int i;
        String thisString = this.getValue();
        String otherString = otherNode.getValue();
        int minSize = ( otherString.length() > thisString.length() ? thisString.length() : otherString.length() );
        for (i = 0; i < minSize; i++) {
             if (thisString.charAt(i) > otherString.charAt(i)) {
                 return 1;
             } else if (thisString.charAt(i) < otherString.charAt(i)) {
                 return -1;
             }
        }
        if (otherString.length() > thisString.length()) {
            return 1;
        } else if (otherString.length() < thisString.length()) {
            return -1;
        } else {
            return 0;
        }
    }
    // OTHER CLASS CONSTRUCTORS, VARIABLES, AND METHODS
}

为了使用简单的泛型来实现这一点，您需要使用类型实现Node类T实现Comparable如下所示：

class NodeNode<T extends Comparable<T>> implements Comparable {

    T value;
    @Override
    public int compareTo(Node otherNode) {
        return this.getValue().compareTo(otherNode.getValue());
    }
    // OTHER CLASS CONSTRUCTORS, VARIABLES, AND METHODS
}

Answer 3

我终于通过使用插入排序弄清楚了：

public void add(Dvd item) {
  DvdNode addThis = new DvdNode(item);
  if(head == null) {
    head = addThis;
  } else if(item.getTitle().compareToIgnoreCase(head.getItem().getTitle()) < 0) {
      addThis.setNext(head);
      head = addThis;
    } else {
        DvdNode temp;
        DvdNode prev;
        temp = head.getNext();
        prev = head;
        while(prev.getNext() != null && item.getTitle().compareToIgnoreCase
            (prev.getNext().getItem().getTitle()) > 0) {
          prev = temp;
          temp = temp.getNext();
        }
        addThis.setNext(temp);
        prev.setNext(addThis);
      }
}