删除LinkedList最后一个元素的问题

Question

我试图在LinkedList中实现delete()方法，这是链表数据结构的自定义实现。

如果删除第一个元素或中间的元素，下面的代码似乎可以正常工作。但是，如果我试图删除LinkedList中的最后一个元素，它会抛出NullPointerException。

如何解决这个问题?

我的代码:

public class LinkedList implements List {
Node first;
Node last;
int size;

public LinkedList() {
this.first = null;
this.last = null;
this.size = 0;
}

public void add(double element) {
Node newNode = new Node(element);

if (first == null) {
first = newNode;
last = newNode;
} else {
last.next = newNode;
last = newNode;
}
size++;
}

// more methods (unrelated to the problem)

public void delete(double element) {
if (first == null) {
return;
}
if (first.value == element) {
first = first.next;
return;
}

Node current = first;
Node previous = null;

while (current != null && current.next.value != element) {
previous = current;
current = current.next;
}

if (current == null) {
return;
} else {
current.next = current.next.next;
}
}
@Override
public String toString() { 
if (first == null) {
return "[]";
} else {
StringBuffer sb = new StringBuffer();
sb.append("[");
for (Node current = first; current != last; current = current.next) {
sb.append(current.value);
sb.append(",");
}
sb.append(last.value);
sb.append("]");
return sb.toString();
}
}
}

class LinkedListTest {

public static void main(String[] args) {

LinkedList list = new LinkedList();

list.add(5);
list.add(25);
list.add(-7);
list.add(80);

System.out.println(list);
list.delete(80);
System.out.println(list);
}
}

Answer 1

delete()方法的实现有两个问题:

• while-loop中的条件不正确。相反，检查current != null是否需要确保current.next不是null(注意访问current的next属性是安全的，因为迭代开始时current被分配给first，这被证明是非空的)。

• 当要删除的节点是最后一个时，您没有考虑边缘情况。在这种情况下，当控制从while-循环中断开时，current.next将指向lastNode，这意味着last字段应该被重新分配(，因为我们正在删除最后一个节点)。

另外，局部变量previous是多余的。

public void delete(double element) {
if (first == null) {
return;
}
if (first.value == element) {
first = first.next;
return;
}

Node current = first;

while (current.next != null && current.next.value != element) {
current = current.next;
}

if (current.next == last) { // reassign last if the Node to be removed is the current last Node
last = current;
}

if (current.next != null) { // if the Node with given value was found
current.next = current.next.next;
}
}