java - 如何删除双链表中的特定条目？

Question

它向我显示“线程“main”java.lang.NullPointerException 中出现异常”，错误位于“instead.prev.next =rather.next;”中在这里。

这是我编写的完整代码

import javax.xml.soap.Node;

public class LinkedSet<T> {
private class DLNode {
    public T data;
    public DLNode prev, next;

    // Can add constructors and other methods
    public DLNode(T dataValue, DLNode PREV, DLNode NEXT) {
        data = dataValue;
        prev = PREV;
        next = NEXT;
    }
}

private DLNode head;
private int numberOfEntries;
private boolean initialized = false;

public LinkedSet() {
    head = null;
    numberOfEntries = 0;
    initialized = true;
}
// Add at beginning of linked list
public boolean add(T newEntry) {
    checkInitialization();
    DLNode doubleLinked = new DLNode (newEntry, null,head);


    head = doubleLinked;
    numberOfEntries++;
    return true;
}
public T[] toArray() {
    @SuppressWarnings("unchecked")
    T[] result = (T[]) new Object[numberOfEntries]; 

    int index = 0;
    DLNode currentNode = head;
    while((index < numberOfEntries)&& (currentNode != null)) {
        result [index] = currentNode.data;
        currentNode = currentNode.next;
        index ++;
    }
    return result;
}
public boolean isEmpty() {
    return numberOfEntries == 0;
}
public int getCurrentSize() {
    return numberOfEntries;
}
public boolean contains(T anEntry) {
    checkInitialization();
    int index = 0;

    DLNode currentNode = head;

    if(isEmpty()) {
        return false;
    }
    else {
    while ((currentNode.next.data!= null) && index > numberOfEntries) {
        if (currentNode.data.equals(anEntry))
        {

            return true;}
        else {
            index ++;
            currentNode = currentNode.next;
        }
    }
    }
    return false;
}



public void clear() {
    head = null;
    numberOfEntries = 0;
}
// remove in-place. That is, do not rearrange elements in the array.

public DLNode find (T anEntry) {
    DLNode currentNode = head;
    while (currentNode != null) {

        if (currentNode.data.equals(anEntry)) {
            return currentNode;

        }
        currentNode = currentNode.next;
    }return null;

}

public boolean remove(T anEntry) {
    DLNode instead = find(anEntry);
    if (isEmpty()) {
        return false;
    }
    else {
        if(instead ==null) {
        return false;
        }
        else {
            if (numberOfEntries ==1) {
                clear();

            }
            else {
        instead.prev.next = instead.next;
        if (instead.next != null) {
            instead.next.prev = instead.prev;
        }
        numberOfEntries--;


        }
        }return true;
    }
}
private void checkInitialization() {
    if (!initialized) {
        throw new SecurityException("Uninitialized object used " + "to call an ArrayBag method.");
    }
}
// Don't change this.
public int getCapacity() {
    return numberOfEntries;
}

public static void main(String[] args) {
    LinkedSet <String> abag = new LinkedSet<>();
    abag.add("A");
    abag.add("B");
    abag.add("C");
    abag.add("D");
    displayBag(abag);
    System.out.println(abag.isEmpty());
    System.out.println(abag.getCurrentSize());
    System.out.println(abag.contains("A"));
    abag.clear();
    displayBag(abag);
    abag.add("A");
    abag.add("B");
    abag.add("C");
    abag.add("D");

    displayBag(abag);
    System.out.println(abag.remove("C"));
}

private static void displayBag(LinkedSet<String> aBag) {
    System.out.println("The bag contains the following string(s):");
    Object[] bagArray = aBag.toArray();
    for (int index = 0; index < bagArray.length; index++) {
        System.out.print(bagArray[index] + " ");
    } // end for

    System.out.println();
}

}要求我们不能更改该数组中元素的顺序。但我不知道为什么“instead.prev.next=instead.next;”是错误的。

Answer 1

在 add 方法中，您执行 DLNode doubleLinked = new DLNode(newEntry, null, head);，因此，您不提供对先前条目的引用。这就是为什么在 remove 中，当您执行 instead.prev.next 时，因为 instead.prev 为 null，您会得到 NPE。

使用调试器很容易检测到这一点。

这就是您的 add 方法的外观:

public boolean add(T newEntry) {
    checkInitialization();
    DLNode doubleLinked = new DLNode(newEntry, null, head);
    //code I added
    if (head != null) {
        head.prev = doubleLinked;
    }

    head = doubleLinked;
    numberOfEntries++;
    return true;
}