Java 链表操作的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18679248/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Linked List time complexity for its operations
提问by Jim
I am implementing a Linked list in terms of stock market program.
我正在实施股票市场计划方面的链接列表。
It has and operation - Buy
它有和操作 - 购买
For Buy the code is
对于购买代码是
//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
}
This operation addLast is for a Linked list obvious adds the given element to a new position at the end of a current list.
此操作 addLast 用于链接列表，显然将给定元素添加到当前列表末尾的新位置。
So for example if I have a list that has lets say the following data
因此，例如，如果我有一个列表，其中包含以下数据
//Stock, price, stock, price etc...
[100, 50, 5000, 30, 8000, 60]
If I addLastis the Linked List search for the last element and then adding and therefore the time complexity would be O(n) (In terms of Big Oh only). Or is it indexing to the end of the list, realizing that the end of the list is say stocks[5]then inserting a new node referencing the new data at the end of the list?
如果 IaddLast是链接列表搜索最后一个元素然后添加，因此时间复杂度将为 O(n)（仅就 Big Oh 而言）。或者它是否索引到列表的末尾，意识到列表的末尾是说stocks[5]然后在列表的末尾插入一个引用新数据的新节点？
So my question is, is addLast()operation for a linked list time complexity of O(n) or O(1)?
所以我的问题是，addLast()链表时间复杂度是 O(n) 还是 O(1)？
Post below for any clarifications
在下面发布任何说明
采纳答案by nasser-sh
If you read the javadocfor the LinkedList class, it states: "All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index."
如果您阅读LinkedList 类的javadoc，它会指出：“所有操作都按照双向链接列表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近者为准到指定的索引。”
This means that it is O(1)
这意味着它是 O(1)
Edit
编辑
If you want a better implementation of your Stock name, price list, I think it would be better to create a class containing the description of the stocks:
如果您想要更好地实现您的股票名称、价目表，我认为最好创建一个包含股票描述的类：
public class Stock {
private int stockName;
private int stockPrice;
// other methods, properties, constructor
}
And then create a LinkedList<Stock>
然后创建一个 LinkedList<Stock>
回答by Stephen C
The complexity of add()or addLast()is O(1)on the length of the list. This is obvious from reading the LinkedListsource code.
在复杂add()或者addLast()是O(1)对列表的长度。从阅读源代码中可以明显看出这一点LinkedList。
(Since this aspect of the behaviour is not specified precisely in the javadoc1, it could be changed ... in theory. However, we can confidently exclude this possibility. Even if it made sense (which it doesn't!), such a change would break many, many existing applications. That alone is sufficient reason to rule it out as implausible.)
（因为行为的这方面在 javadoc 1 中没有精确指定，它可以改变......理论上。但是，我们可以自信地排除这种可能性。即使它是有道理的（它没有！），例如更改会破坏许多现有的应用程序。仅此一项就足以将其排除为不合理的理由。）
1 - I would argue that the javadoc sentence "[o]perations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index"does not unambiguouslyapply to this method. You could argue that the add/ addLastmethod does not indexinto the list.
1 - 我认为 javadoc 句子“[o] 索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准”并不明确适用于这种方法。您可能会争辩说add/addLast方法没有索引到列表中。
回答by claydiffrient
Looking at the source for the LinkedList class it appears that addLastactually calls a method called linkLastwhich is:
查看 LinkedList 类的源代码，它似乎addLast实际上调用了一个名为的方法linkLast：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
The relevant portion is where lastis declared in the class transient Node<E> last;it appears that the class holds a "pointer" to the last node. It then updates with the new node given. So, it should be O(1) regardless of the size of the list.
相关部分是在last类中声明的位置，该类transient Node<E> last;似乎持有指向最后一个节点的“指针”。然后使用给定的新节点进行更新。因此，无论列表的大小如何，它都应该是 O(1)。
