链表删除方法 [英] Linked List Delete Method

问题描述

以下是链接列表"的类定义.我运行一个测试程序，该程序创建一个新的LinkedList并插入数字"3、2、1"，然后打印该列表.这很好.但是，当我尝试删除"3"或"2"时，删除方法永远不会完成.当我尝试删除"1"时，它只会打印出完整的列表，就像没有删除任何内容一样.

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.

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()方法中，成功发生条件时不会中断循环.这就是您的程序挂起的原因.它处于无限循环中.

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.

这一点也值得注意，是一个非常糟糕的习惯，不要在所有if/else语句中都使用花括号.没有理由不这样做，如果不这样做，它很容易引入错误.

It's also worth noting a this point is that it's an incredibly bad practice not 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.

在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;
        }
    }
}

现在，这将产生您期望的结果:

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();
}

输出:

1 2 3
1 3

1 2 3
1 3

但是，这不会暴露出您的第二个更大的问题.在查看节点的data时，您正在使用==比较参考值.

However, that doesn't expose your second, larger issue. You're comparing reference values using == when looking at the node's data.

由于自动装箱小整数值的副作用，此操作目前有效.您将获得相同的对象引用. (由于字符串池，字符串文字也将起作用").有关更多信息，请参见如何比较Java中的字符串和在Java中比较两个整数时会自动取消装箱发生

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 Java and 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

1000 2000 2000 3000
1000 2000 2000 3000

lookup()停止工作，允许插入重复项. delete()也停止工作.

lookup() stopped working, allowing a duplicate to be inserted. delete() stopped working as well.

这是因为int将127个以上的自动装箱值赋给唯一的Integer对象，而不是缓存的对象(有关完整说明，请参见上面的链接的SO问题).

This is because int values over 127 auto-box to unique Integer objects rather than cached ones (see the linked SO question above for a full explanation).

使用==来比较data所保存的值的任何地方都需要更改为使用.equals().

Anywhere you're using == to compare the value held by data needs to be changed to use .equals() instead.

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:

• lookup应该返回boolean.
• 无需在delete()
中调用lookup()
• lookup本身作为单独的方法是一种效率很低的方法.插入将遍历整个列表两次.

• lookup should return a boolean.
• There's no need to call lookup() in delete()
• lookup itself is a fairly inefficient approach as a separate method; An insert iterates through the entire list twice.

这篇关于链表删除方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！