What is the time complexity of a size() call on a LinkedList in Java?

JavaSizeLinked ListTime Complexity

Java Problem Overview

As the title asks, I wonder if the size() method in the LinkedList class takes amortized O(1) time or O(n) time.

Java Solutions

Solution 1 - Java

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.

Solution 2 - Java

O(1) as you would have found had you looked at the source code...

From LinkedList:

private transient int size = 0;


 * Returns the number of elements in this list.
 * @return the number of elements in this list
public int size() {
   return size;


All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionMartin AnderssonView Question on Stackoverflow
Solution 1 - JavaGreenieMeanieView Answer on Stackoverflow
Solution 2 - JavaKrisView Answer on Stackoverflow