第一部分: -
我在书中读到 - "Java中的数据结构和算法变得简单",从Linkedlist和Arraylist中删除最后一个元素的时间复杂度是O(n).但是Linkedlist在内部实现了DoublyLinkedlist,因此时间复杂度应为O(1),类似于Arraylist,因为它在内部实现Array,它应该是O(1).
第二部分: -
它还说在链表的末尾插入一个元素的时间复杂度为O(n),但是链表在末尾和前面都保留了指针.那么这句话是否正确？此外,它表示如果数组未满,则在结尾处插入元素的时间复杂度为O(1),如果数组已满,则为O(n).为什么O(n)数组是否已满？
感谢您回答第1部分.任何人都可以请解释第二部分.谢谢 :)
And*_*mas 15
这取决于你所采用的方法.
瞥一眼实施情况表明,如果你正在打电话LinkedList.removeLast(),那就是O(1).LinkedList维护指向列表中第一个和最后一个节点的指针.因此,它不必遍历列表以到达最后一个节点.
LinkedList.remove(index)使用最后一个元素的索引进行调用也是O(1),因为它从最近的一端遍历列表.[用户@andreas在下面的评论中注明.]
但是如果你正在调用LinkedList.remove(Object),那么就会有一个O(n)搜索第一个匹配节点.
类似地,对于ArrayList,如果您使用ArrayList.remove(index)最后一个元素的索引进行调用,那么那就是O(1).对于所有其他索引,有一个System.arrayCopy()可以是O(n)的调用 - 但是完全跳过了最后一个元素.
但是如果你打电话ArrayList.remove(Object),那么再次有一个O(n)搜索第一个匹配节点.