据说LinkedList的复杂性删除和添加操作是O(1).在的情况下,ArrayList它是O(n).
计算大小为"M"的ArrayList:如果我想删除第N个位置的元素,那么我可以一次性使用索引直接进入第N个位置(我不必遍历直到第N个索引)然后我可以删除元素,直到这一点复杂度为O(1)然后我将不得不移动其余的元素(MN移位),所以我的复杂性将是线性的,即O(M-N + 1).因此最后删除或插入会给我最好的表现(如N~M),并且在开始时删除或插入将是最差的(如N~1).
现在大小为"M"的LisnkedList:因为我们无法直接到达LinkedList中的第N个元素,要访问第N个元素,我们必须遍历N个元素,因此LinkedList中的搜索比ArrayList更昂贵...但删除在LinkedList的情况下,add操作被认为是O(1),因为在LinkedList中不涉及Shift,但是有涉及rigth的遍历操作？所以复杂度应该是O(n)的顺序,其中最差性能将在尾节点处,并且最佳性能将在头节点处.
任何人都可以解释一下为什么我们在计算LinkedList删除操作的复杂性时不考虑遍历成本？
所以我想了解它在java.util包中的工作原理.如果我想在C或C++中实现相同的,我将如何在LinkedList中实现随机删除和插入的O(1)？
java collections linked-list time-complexity data-structures