Issue
I have the following code, where getIDs() returns a list of IDs:
List<Long> ids = getIds();
Long neededID = ids.get(ids.size()-1);
Now sonarqube says:
Collection methods with O(n) performance should be used carefully (java:S2250) The time complexity of method calls on collections is not always obvious. For instance, for most collections the size() method takes constant time, but the time required to execute ConcurrentLinkedQueue.size() is O(n), i.e. directly proportional to the number of elements in the collection. When the collection is large, this could therefore be an expensive operation. This rule raises an issue when the following O(n) methods are called outside of constructors on class fields:
I did not find any public link to show you that rule.
So in my understanding the rule says size() has a runtime of O(n) and I could get() an element of the list faster if I would know the last index. So my question is now if there is an way to get the last element of the list faster, without using size().
I have already done some search but the only thing that I found if I search for get last element of list is that you can use list.get(list.size()-1).
Solution
list.get(list.size()-1) would always be O(n) because a linked list is not a random access data structure like a primitive array. To retrieve a value of a given position in the list, you would have to traverse the list starting at the first node until you get to the node of the position you want. So, don't use list.get(index) to retrieve the last element. Many implementation maintain a reference to the last node in the list so that retrieving the last element is O(1). I don't have the code of java.util.LinkedList but I would imagine its method getLast() is O(1).
Answered By - Cheng Thao
Answer Checked By - David Goodson (JavaFixing Volunteer)
