第 1 部分:-
我在书上读到“数据结构和算法在 Java 中变得简单”，从 Linkedlist 和 Arraylist 中删除最后一个元素的时间复杂度是 O(n)。但是 Linkedlist 内部实现了 DoublyLinkedlist，所以时间复杂度应该是 O(1)，同样对于 Arraylist，因为它内部实现了 Array，它应该是 O(1)。
第二部分:-
它还说，在链表的末尾插入一个元素的时间复杂度为 O(n)，但链表在末尾和前端都维护指针。那么这个说法正确吗？此外，它表示如果数组未满，则在末尾将元素插入数组列表的时间复杂度为 O(1)，如果数组已满，则为 O(n)。为什么 O(n) 如果数组已满？
感谢您回答第一部分。任何人都可以解释第二部分。谢谢:)
最佳答案
这取决于您调用的方法。
看一眼实现就会发现，如果您调用 LinkedList.removeLast()，那就是 O(1)。 LinkedList 维护指向列表中第一个和最后一个节点的指针。因此它不必遍历列表即可到达最后一个节点。
用最后一个元素的索引调用LinkedList.remove(index)也是O(1)，因为它从最近的一端开始遍历列表。 [用户@andreas 在下面的评论中指出。]
但是如果您正在调用 LinkedList.remove(Object)，那么第一个匹配节点的搜索时间为 O(n)。
类似地，对于 ArrayList，如果您使用最后一个元素的索引调用 ArrayList.remove(index)，则为 O(1)。对于所有其他索引，有一个可以是 O(n) 的 System.arrayCopy() 调用——但对于最后一个元素，它被完全跳过了。
但是如果您调用 ArrayList.remove(Object)，那么第一个匹配节点的搜索时间也是 O(n)。
关于java - 从 arraylist 和 linkedlist 中删除最后一个元素时的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43145395/