我正在用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)的副本数。我还有一个链表类、一个列表接口、一个节点类和一个主类。
您的实现是否扩展了 java.util.List 接口?
您可以简单地将对象添加到列表中,然后使用 Collections.sort() 对列表进行排序吗?
您提到使用泛型,但随后提到按字母顺序对它们进行排序。 泛型不一定是字符串,它们用于表示任何类型的类型,而排序属性(如按字母顺序)表示字母字符。 我的答案假设您期望具有字母性质的 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
}
我终于通过使用插入排序弄清楚了:
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);
}
}