Java Data Structures

There are a number of commonly used Java data structures. Here are links to additional documentation and highlights of structural aspects: 

• Array: fixed size, best for primitives 
• List: fixed size, interface, ordered, allows duplicate
• ArrayList: resizable , add to top, preferred unless need the capabilities of another structure
• Vector: resizable, synchronized, add to top
• Stack: LIFO, push/pop
• Queue: FIFO, add to bottom/remove from top, interface
• LinkedList: doubly-linked, push/pop, many other methods
• Set: no duplicates, interface
• HashMap: random access
• TreeMap: sorted, efficient search
• Binary Tree: each node has <=2 children
• Binary Search Tree: sorted, fast lookup/add/remove
• k-d Tree: k dimensional, space-partitioning, nearest neighbor search
• Red-Black Tree: self-balancing, binary search tree, extra bit per node
• Iterator: move forward and backward through data
• Collections: perform operations on collections of data
• Working with Java Lists: methods, iterators, collections
• Data Structure Decisions: change, access, indexing, sizing
• Common Java Array Manipulation Constructs: split, sort, binary search, iteration
• Common Java ArrayList Manipulation Constructs: add, indexOf, remove, sort, binary search, interator
• B-tree and Binary Search Tree Data Structures: like TreeMap
• Sorting Algorithms: Collections sort, exchange, hybrid, insertion, merge
• Big O Notation: O(1), O(log (n)), O(n), O(n log(n))
• Update and Access Overview: The diagram below indicates how elements and values are updated and accessed. This is a broad overview of commonly used data structure classes, interfaces and objects ... please see the links above and below for more details. Some general observations are:
  • Arrays are different than the other structures in that they are accessed using bracketed index [n] references, such as myStringArray[3] instead of methods and can only contain primitives, not objects.
  • ArrayLists are generally preferred over Lists as they allow resizing. It's a very commonly used structure.
  • Vectors are much like ArrayLists with the additional characteristic that they are synchronized.
  • Queues and Stacks are specialized for LIFO and FIFO access.
  • LinkedLists are powerful structures that require more space for storage and time to execute some operations but are efficient for inserting and deleting objects in the existing order.
  • Sets are simple structures that don't allow duplicates.
  • HashMaps are commonly used when rapid, direct access to elements is the primary requirement.
  • TreeMaps are preferred when rapid search is the primary requirement.
  • Iterators and Collections operate on whole data structures.
  • ( ) empty parameter methods generally operate on the ends of a structure.
  • (element | object) only parameter methods generally operate on sets or the ends of structures.
  • (index | key) and (index | key, element | object) parameter methods generally operate on specific places within a structure.

View fullsize