Data Structures

In short: Organised ways of holding data in memory — Java provides ready-made implementations for lists, sets, and mappings via the Collections framework.

In more detail: The choice of data structure significantly determines a program’s performance: an ArrayList allows fast access by index, a LinkedList fast insertion/removal in the middle of the list, a HashSet fast checking for containment. Java arrays (see Arrays) are the simplest but least flexible data structure.

In Depth

Data structure	Access by index	Insert/remove (middle)	Containment check	Duplicates
ArrayList	O(1) fast	O(n) slow	O(n)	allowed
LinkedList	O(n) slow	O(1) fast (at a known position)	O(n)	allowed
HashSet	no index	O(1) on average	O(1) on average	none
HashMap	access by key O(1)	O(1) on average	O(1) on average (key)	keys unique

This table is the actual core of the decision “which data structure do I use”: need frequent access by position → ArrayList. Frequent insertion/removal at known positions (e.g. a queue) → LinkedList or ArrayDeque. Frequent “is X already contained?” with no duplicates → HashSet. Mapping keys to values (e.g. name → phone number) → HashMap. The O(1) values for HashSet/HashMap only hold on statistical average — in the theoretical worst case (many hash collisions) they can drop to O(n), but this is very rare in practice.

How HashMap achieves O(1) internally

The reason for the fast access with HashMap/HashSet lies in the internal structure: every key is mapped to a bucket index via hashCode(), so that a lookup doesn’t have to search the entire structure, but jumps directly to the matching bucket. If two different keys collide in the same bucket (hash collision), they’re managed there internally as a small list or — for many collisions — as a tree, which in the extreme case limits performance to O(log n) instead of O(n) (since Java 8).

Custom data structures vs. standard library

Almost every beginner mistake with data structures consists of building your own, simpler solution (e.g. a manually managed array with your own “is full” logic) instead of the ready-made Collections classes — this costs unnecessary time and is more error-prone, without offering any real advantage. Custom data structures are only worthwhile for very specific requirements that no standard class covers (e.g. a priority queue with dynamically changeable priorities, for which PriorityQueue isn’t directly sufficient).

Memory requirements as another factor

Besides time complexity, memory requirements also play a role: a primitive int[] array needs significantly less memory than an equally sized ArrayList<Integer>, because the latter stores every element as a separate Integer object with object overhead (autoboxing). For very large amounts of data, this difference can be decisive.

See also: Collections, Arrays, Algorithms, HashSet