java - 使用头尾引用的单链表删除元素

Question

我必须为我的项目实现一个单向链表，但我无法使用 remove 方法。我在这里搜索了答案，但找不到任何包含尾部引用的答案。我的项目需要在列表中有一个头部和尾部引用，并且需要在必要时进行更新。这是我的类(class)和删除方法:

public class BasicLinkedList<T> implements Iterable<T> {
public int size;

protected class Node {
    protected T data;
    protected Node next;

    protected Node(T data) {
        this.data = data;
        next = null;
    }
}

protected Node head;
protected Node tail;

public BasicLinkedList() {
    head = tail = null;
}

public BasicLinkedList<T> addToEnd(T data) {
    Node n = new Node(data);
    Node curr = head;
    //Check to see if the list is empty
    if (head == null) {
        head = n;
        tail = head;
    } else {
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = n;
        tail = n;

    }
    size++;
    return this;
}

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    if(head == null){
        head = n;
        tail = n;
    }
    n.next = head;
    head = n;
    size++;
    return this;
}

public T getFirst() {
    if (head == null) {
        return null;
    }
    return head.data;
}

public T getLast() {
    if(tail == null){
        return null;
    }
    return tail.data;
}

public int getSize() {
    return size;
}

public T retrieveFirstElement() {
    // Check to see if the list is empty
    if (head == null) {
        return null;
    }
    Node firstElement = head;
    Node curr = head.next;
    head = curr;
    size--;
    return firstElement.data;

}

public T retrieveLastElement() {
    Node curr = head;
    Node prev = head;
    // Check to see if the list is empty
    if (head == null) {
        return null;
    } else {
        // If there's only one element in the list
        if (head.next == null) {
            curr = head;
            head = null;
        } else {
            while (curr.next != null) {
                prev = curr;
                curr = curr.next;
            }

            tail = prev;
            tail.next = null;
        }
    }
    size--;
    return curr.data;
}

public void remove(T targetData, Comparator<T> comparator) {
    Node prev = null, curr = head;
    while (curr != null) {
        if (comparator.compare(curr.data, targetData) == 0) {
            //Check to see if we need to remove the very first element
            if (curr == head) {
                head = head.next;
                curr = head;
            } 
            //Check to see if we need to remove the last element, in which case update the tail
            else if(curr == tail){
                curr = null;
                tail = prev;
                prev.next = null;
            }
            //If anywhere else in the list
            else {
                prev.next = curr.next;
                curr = curr.next;
            }
            size--;
        } else {
            prev = curr;
            curr = curr.next;
        }
    }
}

public Iterator<T> iterator() {
    return new Iterator<T>() {

        Node current = head;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            if(hasNext()){
                T data = current.data;
                current = current.next;
                return data;
            }
            return null;
        }

        @Override
        public void remove(){
            throw new UnsupportedOperationException("Remove not implemented.");
        }

    };
}

我已经对这种方法进行了多次迭代，每次我要么丢失了头部引用、尾部引用，要么我没有删除该元素，但我都很难弄清楚。作为引用，这里是我正在运行的测试。我什至没有通过测试，它只是说失败痕迹。

public void testRemove(){
            BasicLinkedList<String> basicList = new BasicLinkedList<String>();
    basicList.addToEnd("Blue");
    basicList.addToEnd("Red");
    basicList.addToEnd("Magenta");
    //Blue -> Red -> Magenta -> null
    basicList.remove("Red", String.CASE_INSENSITIVE_ORDER);
    //Blue -> Magenta -> null
    assertTrue(basicList.getFirst().equals("Blue"));
    //getLast() returns the tail node
    assertTrue(basicList.getLast().equals("Magenta"));
    }

编辑:忘记提及删除方法应该从列表中删除目标数据的所有实例。

Answer 1

我只看到 1 个错误。如果您的列表最初为空，则以下方法将导致一个循环，其中您有一个节点的 next 引用自身:

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    // The list was empty so this if is true
    if(head == null){
        head = n;
        tail = n;
    }
    n.next = head;
    // now head == n and n.next == head == n so you've got a circle
    head = n;
    size++;
    return this;
}

你可以这样解决:

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    if(head == null){
        tail = n;
    }
    n.next = head;
    head = n;
    size++;
    return this;
}