插入代码似乎一直工作得很好，直到最后一次插入，它没有按顺序添加它，而是将它放在列表的末尾。
public void insert(Comparable item)
{
if ( this.first == null || item.compareTo(this.first.data) <= 0)
{
addFirst(item);
}
else if( item.compareTo(this.first.data) > 0 )
{
addLast(item);
}
else
{
Node oldFirst = this.first;
this.first = this.first.next;
insert(item);
this.first = oldFirst;
}
}
这是它产生的输出。。。
6 Item(s)
5
16
21
22
45
23
remove方法在删除项目后停止编译，我不知道为什么。
public Comparable remove(Comparable item)
{
if( this.first == null )
{
return null;
}
Node oldFirst = this.first;
if( this.first.next == null && this.first.data.equals(item) )
{
Comparable found = this.first.data;
this.first = null;
return found;
}
this.first = this.first.next;
if( this.first.data.equals(item) )
{
Comparable found = this.first.data;
oldFirst.next = this.first.next;
this.first = oldFirst;
return found;
}
Comparable foundIt = remove(item);
return foundIt;
}
这是remove方法的输出。。。。
at List.remove(List.java:164)
Removed: 21. List has: 4 Item(s)
at List.remove(List.java:164)
16
at List.remove(List.java:164)
22
45
at TestRecursion.main(TestRecursion.java:87)
我注意到，如果项大于第一个元素，则调用addLast。这不会给你一个排序列表。
考虑使用1、4、2、3调用insert。输出将完全按照这个顺序。1、4、2、3。
至于为什么删除会崩溃。。。
//what if its last item, and the data !.equals(item)?
if( this.first.next == null && this.first.data.equals(item) )
{
Comparable found = this.first.data;
this.first = null;
return found;
}
this.first = this.first.next;
//first could be null here if you are at end of list.
if( this.first.data.equals(item) )
{
Comparable found = this.first.data;
oldFirst.next = this.first.next;
this.first = oldFirst;
return found;
}
我建议您使用调试器。应该很快就能解决问题。
您的插入方法最后加了23，因为
item.compareTo(this.first.data) > 0
23实际上是您的第一个元素。
public void insert(Comparable item)
{
first = insertRecursively(first, item);
}
private static Node insert(Node node, Comparable item)
if ( node == null || item.compareTo(node.data) <= 0)
{
Node created = new Node(item);
created.next = node;
return created;
}
else
{
node.next = insertRecursively(node.next, item);
return node;
}
}
递归地执行此操作需要更改刚刚检查的first/next。