为什么不使用ListIterator进行完整的LinkedList操作？

Question

我的主要问题是ListIterator或Iterator类是否减少了从给定LinkedList中删除元素所花费的时间，并且可以说是在使用上述以下任何一种类在同一给定LinkedList中添加元素时说的相同。使用LinkedList类本身的内置函数有什么意义？当我们可以使用ListIterator函数以获得更好的性能时，为什么还要通过LinkedList函数执行任何操作？

Answer 1

ListIterator实际上，A 可以有效地删除其所在的节点。因此ListIterator，您可以创建一个，使用next()两次移动光标，然后立即删除该节点。但是很明显，在实际删除之前您做了很多工作。

如果需要构造迭代器，使用ListIterator.remove“删除时间复杂度”并没有消除“时间复杂度” LinkedList.remove(int index)。该LinkedList.remove方法需要O（k）时间，其中k是您要删除的项目的索引。使用删除此元素具有ListIterator相同的时间复杂度，因为：（a）我们创建一个ListIterator固定时间；（b）我们调用.next() k次，每个操作在O（1）中；（c）我们.remove()再次调用O（1）。但是由于调用了.next() k次，因此这也是O（k）运算。

.add(..)在任意位置（“插入”）也会发生类似的情况，只是我们这里当然要插入一个节点，而不是删除一个节点。

现在，由于这两个对象具有相同的时间复杂度，因此您可能想知道为什么a首先LinkedList具有这样的remove(int index)对象。主要原因是程序员的方便。mylist.remove(5)与创建迭代器，使用循环移动五个位置然后调用remove相比，调用更为方便。此外，链表上的方法可以防止某些不利情况，例如负索引等。通过手动执行此操作，您可能会结束删除第一个元素的操作，而这可能不是预期的行为。最后，有时会多次读取编写的代码。如果将来的读者阅读mylist.remove(5)，他们会理解它删除了第五个要素，因此使用循环的解决方案将需要一些额外的大脑循环才能了解该部分在做什么。

正如@Andreas所说，该List接口还定义了这些方法，因此LinkedList<T>应该实现这些方法。