Java 链表删除方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21802195/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Linked List Delete Method
提问by Christian Baker
The following is a class definition for my Linked List. I run a test program that creates a new LinkedList and inserts the numbers "3, 2, 1" and then prints the list. This works fine. However, when I try and delete "3" or "2," the delete method never completes. When I try and delete "1," it just prints out the complete list as if nothing had been deleted.
以下是我的链表的类定义。我运行一个测试程序，它创建一个新的 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 + " ");
}
}
}
EDIT: Here is the node class:
编辑：这是节点类：
public class Node {
public Object data;
public Node next;
public Node(){
this.data = null;
this.next = null;
}
}
采纳答案by Brian Roach
There are a few issues here.
这里有几个问题。
The first big issue is that in your lookup()and your delete()methods, you don't break out of your loops when a successful condition occurs. This is why your program is hanging; it's in an infinite loop.
第一个大问题是，在您lookup()和您的delete()方法中，当成功条件发生时，您不会跳出循环。这就是你的程序挂起的原因；它处于无限循环中。
It's also worth noting a this point is that it's an incredibly bad practicenot to use curly braces with all if/else statements. There's no reason not to do so, and it can introduce bugs easily when you don't.
还值得注意的是，在所有 if/else 语句中不使用花括号是一种非常糟糕的做法。没有理由不这样做，如果您不这样做，它很容易引入错误。
in lookup()you should have:
在lookup()你应该有：
if (head.data == x) {
search = true;
} else {
while (temp.next != null){
if (temp.data == x){
search = true;
break;
} else {
temp = temp.next;
}
}
}
and in delete():
并在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;
}
}
}
Now this will produce what you expect:
现在这将产生您期望的结果：
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();
}
Output:
输出：
1 2 3
1 3
1 2 3
1 3
However, that doesn't expose your second, larger issue. You're comparing reference valuesusing ==when looking at the node's data.
但是，这不会暴露您的第二个更大的问题。你比较基准值使用==看着节点的时候data。
This "works" at the moment because of a side-effect of auto-boxing small integer values; you're getting the same object references. (String literals would also "work" because of the string pool). For more info on this, look at How do I compare Strings in Javaand When comparing two integers in java does auto-unboxing occur
由于自动装箱小整数值的副作用，这目前“有效”；你得到相同的对象引用。（由于字符串池，字符串文字也可以“工作”）。有关这方面的更多信息，请查看如何比较 Java 中的字符串和比较Java 中的两个整数时是否会发生自动拆箱
Let's look at this:
让我们看看这个：
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();
}
Output:
输出：
1000 2000 2000 3000
1000 2000 2000 3000
1000 2000 2000 3000
1000 2000 2000 3000
lookup()stopped working, allowing a duplicate to be inserted. delete()stopped working as well.
lookup()停止工作，允许插入重复项。delete()也停止工作了。
This is because intvalues over 127 auto-box to unique Integerobjects rather than cached ones (see the linked SO question above for a full explanation).
这是因为int超过 127 的值自动装箱到唯一Integer对象而不是缓存对象（有关完整说明，请参阅上面的链接 SO 问题）。
Anywhere you're using ==to compare the value held by dataneeds to be changed to use .equals()instead.
您==用来比较所持有的值的任何地方都data需要更改为使用.equals()。
if (temp.data.equals(x)) {
With those technical issues solved, your program will work. There's other things that you should consider though. The two that jump right out are:
解决了这些技术问题后，您的程序就可以运行了。不过，您还应该考虑其他一些事情。直接跳出来的两个是：
lookupshould return aboolean.- There's no need to call
lookup()indelete() lookupitself is a fairly inefficient approach as a separate method; An insert iterates through the entire list twice.
lookup应该返回一个boolean.- 有没有必要打电话给
lookup()在delete() lookup作为一种单独的方法，它本身是一种相当低效的方法；插入遍历整个列表两次。
回答by daniel451
I think you got quite some things wrong.
我认为你做错了很多事情。
First of all, when you use LinkedList all of the functionality you tried to implement already exists.
首先，当您使用 LinkedList 时，您尝试实现的所有功能都已经存在。
Furthermore your style is relatively bad. For example, why do you use the WrapperClass Boolean for lookup?
而且你的风格比较差。例如，为什么要使用 WrapperClass 布尔值进行查找？
Combining functionality like containswith something like getin one method is not a good idea. Split this up in two methods, let containsjust return a boolean and test if an element exists in the list. Let get search and return for an element.
将contains 之类的功能与一种方法中的get 之类的功能相结合并不是一个好主意。将其拆分为两种方法，让包含只返回一个布尔值并测试列表中是否存在元素。让 get 搜索并返回一个元素。
In addition to this you try to compare the Objects via equal. If you have not overwritten equals you can not delete anything ever, because equals needs reference equality which is not given most times.
除此之外，您尝试通过相等来比较对象。如果您没有覆盖 equals，则永远无法删除任何内容，因为 equals 需要引用相等性，但大多数情况下都不会给出。
I would highly recommend that you buy a java book or something to improve your overall knowledge..
我强烈建议你买一本 java 书或其他东西来提高你的整体知识。
回答by Indigo
First of all why does lookup return an object? change it to boolean.
also your "while" loop in lookup()doesn't advance. you need to remove the "else".
your delete function seems fine though.
首先为什么lookup会返回一个对象？将其更改为布尔值。您的“while”循环lookup()也不会前进。您需要删除“其他”。不过，您的删除功能似乎没问题。
