java - Java Queue Implementation中pop如何在O(1)中执行？

Question

我已阅读 here Java 的队列在 O(1) 中弹出。

We know that push and pop are constant time operations [O(1) to be precise (Do you know why?)].

我不明白的是 - 如何理解？如果它是一个链表，那么它就不能是 O(1)，因为它必须保存最后一项。如果它是一个双向链表，那么它可以。但它是双向链表吗？

Answer 1

引用自 Java 7 API:

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

所以是的，它是双向链接的。