Java Data Structures Reference

Question

Can anyone give me references of a web site containing a summary of the main Java data structures, and their respective complexity in time (for some given operations like add, find, remove), e.g. Hashtables are O(1) for finding, while LinkedLists are O(n). Some details like memory usage would be nice too

This would be really helpful for thinking in data structures for of algorithms.

Thanks in advance,

Answer 1

I don't believe there is any single website outlining this (Sounds like a good idea for a project though). I think part of the problem is that an understanding in how each of the algorithms runs is very important. For the most part, it sounds like you understand Big-O, so I would use that as your best guesses. Follow it up with some benchmarking/profiling to see what runs faster/slower.

And yes the java docs should have much of this information in java.util

http://java.sun.com/javase/6/docs/api/

Answer 2

The most comprehensive Java Collections overview is here

http://en.wikiversity.org/wiki/Java_Collections_Overview

Answer 3

Is there a reason to think that Java's implementation is different (in terms of complexity) than a generic, language agnostic implementation? In other words, why not just refer to a general reference on the complexity of various data structures:

http://www.itl.nist.gov/div897/sqg/dads/

But, if you insist on Java-specific:

http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/

http://www.coderfriendly.com/2009/05/23/java-collections-cheatsheet-v2/

Answer 4

Time and space complexities for the main collection classes should correspond to data structures known time complexity - I don't think there's anything java specific about it, e.g. ( as you say ) hash lookup should be O(1). You could look here or here.