为什么我的方法无法按字母顺序排序链接列表?
问题描述:
public class doubleLinkedList {
class Node {
String value;
Node prev;
Node next;
Node(String val, Node p, Node n) {
value = val;
prev = p;
next = n;
}
Node(String val) {
value = val;
prev = null;
next = null;
}
}
Node first;
Node last;
public doubleLinkedList() {
first = null;
last = null;
}
public boolean isEmpty() {
if (first == null)
return true;
else
return false;
}
/**The size method returns the length of the linked list
* @return the number of element in the linked list
*/
public int size() {
int count = 0;
Node traverse = first;
while (traverse != null) {
count++;
traverse = traverse.next;
}
return count;
}
public void add(String element) {
if (isEmpty()) {
first = new Node(element);
last = first;
} else {
Node p = first;
Node elementTobeAdded;
while (((p.value).compareTo(element)) > 0 && p.next != null) {
p = p.next;
}
if (p.next != null) {
elementTobeAdded = new Node(element, p, p.next);
p.next.prev = elementTobeAdded;
p = elementTobeAdded.prev;
} else {
elementTobeAdded = new Node(element, p, null);
p.next = elementTobeAdded;
elementTobeAdded.next = null;
last = elementTobeAdded;
}
}
}
public void printForward() {
Node printNode = first;
while (printNode != null) {
System.out.print(printNode.value + ", ");
printNode = printNode.next;
}
}
}
public class test {
public static void main(String[] args) {
doubleLinkedList car = new doubleLinkedList();
car.add("Jeep");
car.add("benz");
car.add("Honda");
car.add("Lexus");
car.add("BMW");
car.printForward();
}
}
我的add方法试图按照字母顺序将节点添加到列表中。我的printForward方法打印列表中的每个元素。 在我的主要方法,它打印出“吉普,奔驰,本田,宝马,”这是不是按字母顺序。为什么我的方法无法按字母顺序排序链接列表?
答
它不是一个链表...你写了某种排队(有可能使它成为排队)。
关于你的问题 - 你的'添加'方法有错误 - 至少你不检查是否有必要前进。这可能是你有另一种错误,但为时已很难读这样的风格来源(请修正你的问题的格式)...
答
更改不是空的情况下,你的add方法从这个
Node p = first;
Node elementTobeAdded;
while(((p.value).compareTo(element)) > 0 && p.next != null)
{
p = p.next;
}
if(p.next != null)
{
elementTobeAdded = new Node(element,p,p.next);
p.next.prev = elementTobeAdded;
p = elementTobeAdded.prev;
}
else
{
elementTobeAdded = new Node(element, p, null);
p.next = elementTobeAdded;
elementTobeAdded.next = null;
last = elementTobeAdded;
}
对此:
Node p = first;
while (p.value.compareTo(element) < 0 && p.next != null) {
p = p.next;
}
if (p.value.compareTo(element) > 0) {
Node toAdd = new Node(element, p.prev, p);
p.prev = toAdd;
if (toAdd.prev != null) {
toAdd.prev.next = toAdd;
}else {
first = toAdd;
}
}else {
Node toAdd = new Node(element, p, p.next);
p.next = toAdd;
if (toAdd.next != null) {
toAdd.next.prev = toAdd;
}else {
last = toAdd;
}
}
这里有很多错误。最大的问题是,你从来没有检查过应该在列表开头插入新元素的情况。一个新的元素总是插在第一个元素之后,即使它应该先到达。
请注意,“benz”的结尾是因为String.compareTo
方法将大写字母视为小写字母。
你用调试器通过了你的代码吗? –
https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – David