Menu
The Java. util. LinkedList. getLast() method is used to fetch or retrieve the last element from a LinkedList or the element present at the tail of the list.
To search a linked list, you are going to iterate over each item in the list. The most time this will take, will be T(n) where n is the length of your list.
For ArrayList , insertion is O(1) only if added at the end. In all other cases (adding at the beginning or in the middle), complexity is O(N), because the right-hand portion of the array needs to be copied and shifted. The complexity of a LinkedList will be O(1) both for insertion at the beginning and at the end.
I have a private LinkedList in a Java class & will frequently need to retrieve the last element in the list. The lists need to scale, so I'm trying to decide whether I need to keep a reference to the last element when I make changes (to achieve O(1)) or if the LinkedList class does that already with the getLast() call.
What is the big-O cost of LinkedList.getLast() and is it documented? (i.e. can I rely on this answer or should I make no assumptions & cache it even if it's O(1)?)
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