Java Data Structures Reference

java data-structures time-complexity summary
Samuel Carrijo picture Samuel Carrijo · Aug 13, 2009 · Viewed 20.8k times · Source

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 algorithms.

Answer

Matthew Nizol picture Matthew Nizol · Aug 13, 2009

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:

NIST Dictionary of Algorithms and Data Structures

But, if you insist on Java-specific:

Java standard data structures Big O notation

Java Collections cheatsheet V2 (dead link, but this is the first version of the cheatsheet)

Related questions

What are the time complexities of various data structures?

I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, but I guess some of us are …

Read More
LRU cache in Java with Generics and O(1) operations

This is a question that comes up a lot in job interviews. The idea is to define a data structure instead of using Java's built in LinkedHashMap. An LRU cache deletes the least recently used entry to insert a new …

Read More
How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More