java - 链表删除方法

标签 java list

以下是我的链接列表的类定义。我运行一个测试程序,创建一个新的 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 JavaWhen 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/

相关文章:

Java - LWJGL - OS X 视网膜支持

java - org.apache.kafka.common.errors.UnknownTopicOrPartitionException : This server does not host this topic-partition 错误

java.lang.IndexOutOfBoundsException :Invalid index x, 大小为 x

python - python 中大型列表操作的性能更高

java - 使用泛型时如何解决这个未经检查的转换错误?

javascript - jquery 隐藏/显示来自 ul 的列表元素

java - 我如何删除没有belongs的grails中有很多关系

java - 如何使用spring在响应消息头中将内容类型设置为text/xml

java - 了解 Android 上下文 : (null object reference)

python - 按某个键的值对列表中的字典进行分组