优化从 Java 中另一个列表定义的列表中删除元素

Question

我的代码正在工作，但复杂性是二次的，我一直在努力弄清楚如何改进它。我必须创建一种方法来从另一个列表中删除列表中包含的元素，最终测试列表长度为 50.000 个元素，要删除的元素列表长度为 100 个。

这是我创建的方法：

public void remove(SingleLinkedList<T> toRemove){
for(int j=0; j<toRemove.size; j++){
Node<T> remC = toRemove.getN(j);
if(toRemove.isEmpty()){
break;
}
for(int i=0; i<size; i++){
Node<T> prev = getN(i-1);
Node<T> cur = getN(i);
Node<T> next = getN(i+1);
if(isEmpty()){
break;
}
if(remC.getValue().equals(cur.getValue())){
if(cur.getValue().equals(getFirst())){
removeFirst();
i--;
}else if(cur.getValue().equals(getLast())){
removeLast();
i--;
}else {
prev.setNext(next); //remove node cur
size--;
i--;
}
}
}
}
}

这是有效的，但超过了 50.000 个元素列表 x 100 个元素删除列表的情况的时间限制，我正在尝试做的是首先 for 循环我保存位置为 j 的节点在 toRemove 列表中，在 seccond for 循环我检查主列表的节点位置 i 是否等于它， 如果是这样，我将其删除，否则我将移动到下一个节点。

有什么想法吗？

Answer 1

我完成了这项工作，正如 Andreas 建议的那样，我摆脱了getN()，但仅凭这一点并不能解决问题，所以我在"i" for外做了一个循环，只是为了摆脱第一个元素，如果它们在toRemove列表中(.contains()用于此(，摆脱了"j" for， 然后在我的 for 循环中，我只需要处理链表中的元素，这个想法是curr node会node 0，充当prev node，所以我会在cur.getNext()周围搜索，因为我确保node 0不在toRemove内，因为第一个循环在for之外。

它工作得很好，不必每次都遍历列表的位置，即使这不是线性的，至少不是二次的，所以对于 50k 列表测试来说已经足够好了。

:)