Menu
As the title asks, I wonder if the size() method in the LinkedList class takes amortized O(1) time or O(n) time.
733
In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).
LinkedList. size() method is used to get the size of the Linked list or the number of elements present in the linked list. Parameters: This method does not take any parameter. Return Value: This method returns the size or the number of elements present in the LinkedList.
For all of the listed methods, we have O(1) for HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap and ConcurrentHashMap.
As Linked List elements are not contiguous, each element access incur a Time Complexity of O(√N).
It's O(1). You can google for the source code and you will come to such:
From http://www.docjar.com/html/api/java/util/LinkedList.java.html
All of the Collection classes I have looked at store a the size as a variable and don't iterate through everything to get it.
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
