0

In Java Collection Framework, a lot of implmentations mention about their performance in the Javadoc. For example, HashSet's says:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets).

And ArrayList's says:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.

But LinkedList's says nothing about its performance.

I believe pop and push method of LinkedList runs in constant time as linked list in computer science does. But I'm worry that It is okay to suppose that when I implement a method which has a LinkedList parameter.

Does LinkedList has any reason not to say its performance?

npcode
  • 1,370
  • 1
  • 14
  • 29
  • 1
    this is a good response to a similar question: http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – slipperyseal May 18 '15 at 02:30
  • `LinkedList` appears not to say anything about the performance of _any_ of its operations. I don't know why--this isn't just about `pop` and `push`. – ajb May 18 '15 at 03:23

1 Answers1

3

The javadoc for HashMap.get(Object) doesn't guarantee O(1) performance either, yet it is well known for being so.

Javadoc is about the contract, not the implementation. API contracts typically concern themselves with behaviour, not performance SLAs.

Specific implementation choices that impact the contract may be documented in javadoc, but that still falls under the subject of "contract".

Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • 1
    HashMap guarantees that "This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets." So I can suppose the methods run in constant time. – npcode May 18 '15 at 02:52
  • I don't think `HashMap.get(Object)` is truly O(1) anyway. It can be O(1) in practice if used in certain ways. But you're mentioning a _contract_, and IMHO that requires a stricter mathematical assertion than "it's usually O(1) in practice". And that cannot be achieved with a `HashMap`. First, the user could provide a bad hash function. Second, even with a good hash function, when the number of elements greatly exceeds the number of hash buckets, the time clearly becomes proportional to the number of elements (if buckets are implemented linearly), which means it's really O(n). – ajb May 18 '15 at 03:15