java.util.LinkedList addLast() 性能

Question

java.util.LinkedList 中 addLast()、add() 或 Offer() 等效方法的渐近复杂度是多少？是 O(N) 还是 O(1)？也就是说，LinkedList 内部是保留一个指向其尾部的指针，还是从头部开始遍历链表？

无论哪种方式，您将如何利用 FIFO 队列的具体实现，该实现在 Offer() 方法中效率更高，但仍使用标准库？ (没有自定义队列实现)。 LinkedList 是一个好的选择还是其他选择？

我意识到这个问题之前可能有人问过，但我搜索了很长时间后找不到答案。

Answer 1

是的，列表保留了一个指向尾部的指针，正如您可以在 class JavaDoc 中读到的那样。 .

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.

因此像 addLast() 和 add() 这样的操作需要 O(1) 时间。

文档特别指出 LinkedList 适合队列实现。

Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.