双链表 - RemoveFirst方法

Question

我需要以下代码的帮助：

public boolean remove(Integer value) {

    if (isEmpty()) {
        throw new NoSuchElementException();
    }
    if (!isEmpty()) {
        if (head == tail) {
            head = tail = null;
        }
    } else {


    }

    size--;

    return false;
}

这是我的任务：

“从此列表中删除第一次出现的指定值”

这是一个双向链表的方法。

到目前为止，我认为我做对了，但我仍然错过了“其他”部分，我不知道该放什么内容......

我还有一个带有构造函数和getter和setter方法的类。

这是我的节点类：

public class ListElement {

    private Integer value;
    private ListElement next;
    private ListElement prev;

    public ListElement(ListElement prev, Integer value, ListElement next) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }

    public Integer getValue() {
        return value;
    }

    public ListElement getNext() {
        return next;
    }

    public ListElement getPrev() {
        return prev;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public void setNext(ListElement next) {
        this.next = next;
    }

    public void setPrev(ListElement prev) {
        this.prev = prev;
    }

}

Answer 1

我通过函数签名假设您要删除具有特定值的元素。您需要找到该节点并将其删除：

public boolean remove(Integer value) {

    if (isEmpty()) {
        throw new NoSuchElementException();
    }
    ListElement found = head;
    // Try to find it
    while (null != found && !found.value.equals(value)) {
         found = found.next;
    }
    // Not found?
    if (null == found) {
        throw new NoSuchElementException();
    }
    // Found. Unlink
    if (found.prev != null) found.prev.next = found.next;
    else head = found.next;
    if (found.next != null) found.next.prev = found.prev;
    else tail = found.prev;

    size--;

    return true;
}

Answer 2

首先，这个if应该被删除，因为你已经测试了空

if (!isEmpty()) {
    if (head == tail) {
        head = tail = null;
    }
} else {


}

然后你可以处理如下：

public boolean remove(Integer value) {
    if (isEmpty()) {
        throw new NoSuchElementException();
    }

    if (head == tail) {
        if (head.getValue() == value) {
            head = tail = null;
        } else  {
            // Not found, return false
            size--;
            return false;
        }
    }

    ListElement current = head;
    while (current != null) {
        if (current.getValue() == value) {
            // Found
            if (current.getPrev() == null) {
                // current node is head node
                head = current.getNext();
                current.setPrev(null);
            } else if (current.next() == null) {
                // current node is tail node
                tail = current;
                current.setNext(null);
            } else {
                // Current node is in the middle
                ListElement prev = current.getPrev();
                ListElement next = current.getNext();
                prev.setNext(next);
                next.setPrev(prev);
            }
            size--;
            return true;
        }
    }
    // Not found
    size--;
    return false;
}