以下是我的链接列表的类定义。我运行一个测试程序,创建一个新的 LinkedList 并插入数字“3,2,1”,然后打印该列表。这很好用。但是,当我尝试删除“3”或“2”时,删除方法永远不会完成。当我尝试删除“1”时,它只是打印出完整列表,就好像没有删除任何内容一样。
public class LinkedListTest implements LinkedList {
private Node head;
public LinkedListTest(){
head = new Node();
}
public void insert(Object x){
if (lookup(x).equals(false)){
if (head.data == null)
head.data = x;
else{
//InsertLast
Node temp = head;
while (temp.next != null){
temp = temp.next;
}
Node NewNode = new Node();
NewNode.data = x;
NewNode.next = null;
temp.next = NewNode;
}
}
//Runtime of insert method will be n, where n is the number of nodes
}
public void delete(Object x){
if (lookup(x).equals(true)){
if (head.data == x)
head = head.next;
else{
Node temp = head;
while (temp.next != null){
if ((temp.next).data == x)
temp.next = (temp.next).next;
else
temp = temp.next;
}
}
}
}
public Object lookup(Object x){
Node temp = head;
Boolean search = false;
if (head.data == x)
search = true;
while (temp.next != null){
if (temp.data == x){
search = true;
}
else{
temp = temp.next;
}
}
return search;
}
public boolean isEmpty(){
if (head.next == null && head.data == null)
return true;
else
return false;
}
public void printList(){
Node temp = head;
System.out.print(temp.data + " ");
while (temp.next != null){
temp = temp.next;
System.out.print(temp.data + " ");
}
}
}
编辑:这是节点类:
public class Node {
public Object data;
public Node next;
public Node(){
this.data = null;
this.next = null;
}
}
最佳答案
这里有一些问题。
第一个大问题是,在您的 lookup()
和 delete()
方法中,当成功条件发生时,您不会跳出循环。这就是你的程序挂起的原因;它处于无限循环中。
还值得注意的是,在所有 if/else 语句中不使用大括号是一种非常糟糕的做法。没有理由不这样做,而且如果不这样做,很容易引入错误。
在lookup()
中你应该有:
if (head.data == x) {
search = true;
} else {
while (temp.next != null){
if (temp.data == x){
search = true;
break;
} else {
temp = temp.next;
}
}
}
以及在delete()
中:
if (head.data == x) {
head = head.next;
} else {
Node temp = head;
while (temp.next != null) {
if (temp.next.data.equals(x)) {
temp.next = temp.next.next;
break;
} else {
temp = temp.next;
}
}
}
现在这将产生您所期望的结果:
public static void main( String[] args )
{
LinkedListTest llt = new LinkedListTest();
llt.insert(1);
llt.insert(2);
llt.insert(3);
llt.printList();
System.out.println();
llt.delete(2);
llt.printList();
}
输出:
1 2 3
1 3
但是,这并没有暴露你的第二个更大的问题。在查看节点的数据
时,您使用==
来比较引用值。
由于自动装箱小整数值的副作用,目前此“有效”;您将获得相同的对象引用。 (由于字符串池,字符串文字也可以“工作”)。有关这方面的更多信息,请查看How do I compare Strings in Java和 When comparing two integers in java does auto-unboxing occur
让我们看看这个:
public static void main( String[] args )
{
LinkedListTest llt = new LinkedListTest();
llt.insert(1000);
llt.insert(2000);
llt.insert(2000);
llt.insert(3000);
llt.printList();
System.out.println();
llt.delete(2000);
llt.printList();
}
输出:
1000 2000 2000 3000
1000 2000 2000 3000
lookup()
停止工作,允许插入重复项。 delete()
也停止工作。
这是因为 int
值超过 127 个自动装箱到唯一的 Integer
对象而不是缓存的对象(请参阅上面链接的 SO 问题以获取完整说明)。
任何使用 ==
来比较 data
所保存的值的地方都需要更改为使用 .equals()
。
if (temp.data.equals(x)) {
解决了这些技术问题后,您的程序就可以运行了。不过,您还应该考虑其他事情。直接跳出来的两个是:
lookup
应返回一个boolean
。- 无需在
delete()
中调用lookup()
作为一个单独的方法, lookup
本身是一种相当低效的方法;插入会迭代整个列表两次。
关于java - 链表删除方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21802195/