据说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
我正在实施股票市场计划的关联清单.
它有和操作 - 买
对于购买代码是
//Stocks is a linked List like so
//LinkedList<Integer> stocks = new LinkedList<Integer>();
public void buy(int q, int p) {
stocks.addLast(q); //add number of stocks
stocks.addLast(p); //for i stocks i +1 = price of stock
}
此操作addLast用于链接列表,显然将给定元素添加到当前列表末尾的新位置.
因此,例如,如果我有一个列表,让我们说下面的数据
//Stock, price, stock, price etc...
[100, 50, 5000, 30, 8000, 60]
如果我addLast是最后一个元素的链接列表搜索然后添加,因此时间复杂度将是O(n)(仅就Big Oh而言).或者它是否索引到列表的末尾,意识到列表的末尾是说stocks[5]然后插入引用列表末尾的新数据的新节点？
所以我的问题是,addLast()操作链表时间复杂度为O(n)还是O(1)？
发布以下任何说明
Java中是否有一个类可以从数据结构书中实现Stack的概念，即LIFO，pop为O（1）并推入O（1）？
我读了一点代码，java.util.Stack似乎push不是O（1）-push可以调用Vector.grow（）并且可以使用O（n）（我知道它摊销了O（1），但我看起来对于总是推O（1））
而且我想了解为什么java.util.Stack是按原样设计的，而不是按栈的理论原理设计的