Java中LinkedList实现remove()方法与Iterator.remove()返回类型冲突问题

问题背景 #

我需要实现一个LinkedList<E>类，它必须实现自定义的List<E>接口，接口中包含一个remove()方法，定义如下：

/**
 * Removes the head (first element) from the list and returns it.
 * @return the removed element from the head of the list, null if the list is empty
 */
E remove();

我已经编写了Node<E>类用于表示链表节点，LinkedList类包含int size（节点数量）和Node<E> head（头节点引用）两个实例变量。但我写的remove()方法一直报错。

错误信息 #

Error: The return type is incompatible with java.util.Iterator<E>.remove().

当前的remove()方法代码 #

public E remove() {
    if (head == null) {
        return null;
    } else {
        Node<E> current = head;
        Node<E> previous = null;
        while (current.getNext() != null) {
            previous = current;
            current = current.getNext();
        }
        Node<E> previousNext = previous.getNext();
        E currentData = current.getData();
        previousNext = null;
        size--;
        return currentData;
    }
}

完整LinkedList类代码 #

import java.util.Iterator;

public abstract class LinkedList<E> extends LinkedListIterator<E> implements List<E>{

    private int size;
    private Node<E> head;

    public LinkedList() {
        size = 0;
        head = null;
    }

    public LinkedList(E[] elements) {
        //creates a LinkedList from elements in array (idk yet)
    }

    public Node<E> getHead() {
        return head;
    }

    public void add(E element) {
        Node<E> node = new Node(element);
        if (head == null) {
            head = node;
        } else {
            Node<E> current = head;
            while(current.getNext() == null) {
                current = current.getNext();
            }
            current = node;
        }
        size += 1;
    }

    public void add(int index, E element) {
        Node<E> node = new Node<E>(element);
        Node<E> nextNode = node.getNext();
        Node<E> current = null;
        Node<E> currentNode = current.getNext();
        Node<E> temp = head;
        if (index >= 0 && index <=size) {
            int i = 0;
            while (temp != null && i < index) {
                current = temp;
                temp = temp.getNext();
                i++;
            }
            if (current == null) {
                nextNode = head;
                head = node;
            } else {
                currentNode = node;
                nextNode = temp;
            }
            size += 1;
        }
    }
    
    public E remove(int index) {
        Node<E> current = head;
        E currentData = current.getData();
        Node<E> previous = null;
        Node<E> previousNode = previous.getNext();
        if (index >= 0 && index < size) {
            int i = 0;
            while (current != null && i < index) {
                previous = current;
                current = current.getNext();
                i++;
            }
            if (previous == null) {
                current = current.getNext();
            } else {
                previousNode = current.getNext();
            }
            size--;
        }
        return currentData;
    }

    public E remove(E element) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current != null && !(current.getData().equals(element))) {
            previous = current;
            current = current.getNext();
        }
        if (current == null) {
            current = current.getNext();
        } else{
            previous = current.getNext();
            size--;
        }
        return element;
    }

    public E remove() {
        if (head == null) {
            return null;
        } else {
            Node<E> current = head;
            Node<E> previous = null;
            while (current.getNext() != null) {
                previous = current;
                current = current.getNext();
            }
            Node<E> previousNext = previous.getNext();
            E currentData = current.getData();
            previousNext = null;
            size--;
            return currentData;
        }
    }

    public E get(int index) {
        Node<E> current = head;
        E currentData = current.getData();
        if (index >= 0 && index < size){
            int i = 0;
            while (current != null && i < index) {
                current = current.getNext();
                i++;
            }
        }
        return currentData;
    }

    public boolean contains(E element) {
        Node<E> current = head;
        boolean result = false;
        while (current != null) {
            if (current.getData().equals(element)) {
                result = true;
            }
            current = current.getNext();
        }
        return result;
    }

    public E set(int index, E element) {
        Node<E> current = head;
        E currentData = current.getData();
        if (index >= 0 && index < size) {
            int i = 0;
            while (current != null && i < index) {
                current = current.getNext();
                i++;
            }
            currentData = element;
        }
        return currentData;
    }

    public void clear() {
        size = 0;
        head = null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
    
    public void removeDuplicates() {
        Node<E> temp = head;
        while (temp != null) {
            Node<E> temp2 = temp.getNext();
            int i = 0;
            while (temp2 != null) {
                if (temp2.getData().equals(temp.getData())) {
                    remove(i);
                } else {
                    i++;
                    temp2 = temp2.getNext();
                }
            }
            temp = temp.getNext();
        }
    }

    public E[] toArray() {
        E[] arr = (E[]) new Object[size];
        Node<E> current = head;
        int i = 0;
        while (current != null) {
            arr[i++] = current.getData();
            current = current.getNext();
        }
        return arr;
    }

    public Iterator<E> iterator() {
        return new LinkedListIterator<E>();
    }
}

问题原因分析 #

1. 方法签名冲突：你的LinkedList类继承了LinkedListIterator<E>，而LinkedListIterator应该实现了java.util.Iterator<E>接口。Iterator接口中的remove()方法返回类型是void，但你在LinkedList中定义的remove()方法返回E，这违反了Java方法重写规则——子类重写的方法返回类型必须和父类方法兼容，这里E和void完全不兼容，因此报错。
2. 逻辑错误：当前的remove()方法实际是移除链表的尾节点，但List接口要求的是移除头节点，和接口定义的功能不符。

修复方案 #

1. 解决继承冲突问题 #

不要让LinkedList直接继承LinkedListIterator，迭代器应该作为LinkedList的内部类，或者让LinkedListIterator独立实现Iterator接口，LinkedList只需要通过iterator()方法返回该迭代器的实例即可。因为List接口继承了Iterable，你只需要正确实现iterator()方法，不需要继承迭代器类。

修改类定义：

// 去掉继承LinkedListIterator
public class LinkedList<E> implements List<E>{
    // ... 其余代码不变
}

2. 修正remove()方法逻辑 #

按照接口要求，实现移除头节点的功能：

public E remove() {
    // 空列表返回null
    if (head == null) {
        return null;
    }
    // 保存头节点的数据
    E removedElement = head.getData();
    // 将头指针移动到下一个节点
    head = head.getNext();
    // 节点数量减一
    size--;
    return removedElement;
}

其他代码问题补充 #

除了remove()方法，你的代码还有一些逻辑错误需要修复：

• add()方法：当前的while(current.getNext() == null)条件错误，应该是while(current.getNext() != null)，用来找到链表的最后一个节点；并且最后应该用current.setNext(node)将新节点添加到链表末尾，而不是current = node。
• remove(int index)方法：previous初始为null时调用previous.getNext()会触发空指针异常，需要先判断previous是否为null再操作；同时返回的currentData应该是被移除节点的数据，而不是初始头节点的数据。
• remove(E element)方法：找到目标节点后，应该修改前一个节点的next引用，而不是直接给previous赋值；如果目标节点是头节点，需要单独处理。

内容的提问来源于stack exchange，提问作者chhscs