Data Structures

Last edited: September 26, 2024 - 4 minutes read

Description

Data Structures in Java

Content

Overview of the most useful data structures from the Java Collections API

Note: In order to make any of the following collections thread safe, you can use:

List<E> list = Collection.synchronizedList(list);
Set<E> set = Collection.synchronizedSet(set);
Map<K, V> map = Collection.synchronizedMap(map);

Arrays

Array

E[] array = new E[10];
int n = array.length;

E element = array[0];
array[0] = element;

Arrays.sort(array);
Arrays.sort(array, Collections.reverseOrder());
Arrays.sort(array, (E e1, E e2) -> e1.compareTo(e2));

int index = Arrays.binarySearch(array, element);

Running times:

OperationTime Complexity
AccessO(1)
UpdateO(1)
IterationO(n)

Lists

ArrayList

ArrayList<E> list = new ArrayList<>();
int n = list.size();

list.add(element);
list.add(index, element);
list.addAll(collection);
list.addAll(index, collection);

E element = list.get(index);

E removed = list.remove(index);
list.clear();

boolean isEmpty = list.isEmpty();
boolean contains = list.contains(element);
int index = list.indexOf(element);

int min = Collections.min(list)
int max = Collections.max(list)

int count = Collections.frequency(list, element);

Collections.sort(list);
Collections.sort(list, Collections.reverseOrder());
Collections.sort(list, (E e1, E e2) -> e1.compareTo(e2));

int index = Collections.binarySearch(list, element);

Collections.shuffle(list);

Running times:

OperationTime Complexity
GetO(1)
IndexOfO(n)
AddO(1)
RemoveO(n)
IterationO(n)

Stacks

ArrayDeque

ArrayDeque<E> stack = new ArrayDeque<>();

stack.push(element);
E top = stack.peek();
E popped = stack.pop();

boolean isEmpty = stack.isEmpty();
int size = stack.size();

Running times:

OperationTime Complexity
PushO(1)
PeekO(1)
PopO(1)

Queues

ArrayDeque

ArrayDeque<E> queue = new ArrayDeque<>();

queue.offer(element);
E head = queue.peek();
E removed = queue.poll();

boolean isEmpty = queue.isEmpty();
int size = queue.size();

Running times:

OperationTime Complexity
OfferO(1)
PeekO(1)
PollO(1)

PriorityQueue (Heap Implementation)

PriorityQueue<E> priorityQueue = new PriorityQueue<>();
PriorityQueue<E> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<E> priorityQueue = new PriorityQueue<>((E e1, E e2) -> e1.compareTo(e2));
int size = priorityQueue.size();

priorityQueue.offer(element);
E head = priorityQueue.peek();
E removed = priorityQueue.poll();

boolean isEmpty = priorityQueue.isEmpty();
boolean contains = priorityQueue.contains(element);

Running times:

OperationTime Complexity
OfferO(log n)
PeekO(1)
PollO(log n)

Sets

HashSet

HashSet<E> set = new HashSet<>();
int n = set.size();

set.add(element);

set.remove(element);
set.clear();

boolean isEmpty = set.isEmpty();
boolean contains = set.contains(element);

Running times:

OperationTime Complexity
AddO(1) (degrades to O(n) with hash collisions)
RemoveO(1) (degrades to O(n) with hash collisions)
ContainsO(1) (degrades to O(n) with hash collisions)
IterationO(n)

TreeSet

TreeSet<E> set = new TreeSet<>();
TreeSet<E> set = new TreeSet<>(Collections.reverseOrder());
TreeSet<E> set = new TreeSet<>((E e1, E e2) -> e1.compareTo(e2));
int n = set.size();

set.add(element);

E first = set.first();
E last = set.last();

E before = set.lower(element);
E after = set.higher(element);

set.remove(element);
set.clear();

SortedSet<E> sub = set.subSet(fromElement, fromInclusive, toElement, toInclusive);
SortedSet<E> tail = set.tailSet(fromElement, inclusive);
SortedSet<E> head = set.headSet(toElement, inclusive);

boolean isEmpty = set.isEmpty();
boolean contains = set.contains(element);

Running times:

OperationTime Complexity
AddO(log n)
RemoveO(log n)
ContainsO(log n)
IterationO(n)

LinkedHashSet

LinkedHashSet<E> set = new LinkedHashSet<>();
int n = set.size();

set.add(element);
set.remove(element);
set.clear();

boolean isEmpty = set.isEmpty();
boolean contains = set.contains(element);

// insertion order iteration
for (E e : set) {

}

Running times:

OperationTime Complexity
AddO(1) (degrades to O(n) with hash collisions)
RemoveO(1) (degrades to O(n) with hash collisions)
ContainsO(1) (degrades to O(n) with hash collisions)
IterationO(n)

Maps

HashMap

HashMap<K, V> map = new HashMap<>();
int n = map.size();

map.put(key, value);

V value = map.get(key);

map.remove(key);
map.clear();

boolean isEmpty = map.isEmpty();
boolean containsKey = map.containsKey(key);
boolean containsValue = map.containsValue(value);

Running times:

OperationTime Complexity
PutO(1) (degrades to O(n) with hash collisions)
GetO(1) (degrades to O(n) with hash collisions)
RemoveO(1) (degrades to O(n) with hash collisions)
ContainsKeyO(1) (degrades to O(n) with hash collisions)
ContainsValueO(n)
IterationO(n)

TreeMap

TreeMap<K, V> map = new TreeMap<>();
TreeMap<K, V> map = new TreeMap<>(Collections.reverseOrder());
TreeMap<K, V> map = new TreeMap<>((K k1, K k2) -> k1.compareTo(k2));
int n = map.size();

map.put(key, value);

V value = map.get(key);

K firstKey = map.firstKey();
K lastKey = map.lastKey();

K beforeKey = map.lowerKey(key);
K afterKey = map.higherKey(key);

map.remove(key);
map.clear();

NavigableMap<K, V> sub = map.subMap(fromKey, fromInclusive, toKey, toInclusive);
NavigableMap<K, V> tail = map.tailMap(fromKey, inclusive);
NavigableMap<K, V> head = map.headMap(toKey, inclusive);

boolean isEmpty = map.isEmpty();
boolean containsKey = map.containsKey(key);
boolean containsValue = map.containsValue(value);

Running times:

OperationTime Complexity
PutO(log n)
GetO(log n)
RemoveO(log n)
ContainsKeyO(log n)
ContainsValueO(n)
IterationO(n)

LinkedHashMap

LinkedHashMap<E> map = new LinkedHashMap<>();
LinkedHashMap<E> map = new LinkedHashMap<>(Collections.reverseOrder());
LinkedHashMap<E> map = new LinkedHashMap<>((E e1, E e2) -> e1.compareTo(e2));
int n = map.size();

map.add(element);
map.remove(element);
map.clear();

boolean isEmpty = map.isEmpty();
boolean contains = map.contains(element);

// insertion order iteration
for (Map.Entry<K, V> entry : map.entrySet()) {
  K key = entry.getKey();
  V value = entry.getValue();
}

Running times:

OperationTime Complexity
PutO(1) (degrades to O(n) with hash collisions)
GetO(1) (degrades to O(n) with hash collisions)
RemoveO(1) (degrades to O(n) with hash collisions)
ContainsKeyO(1) (degrades to O(n) with hash collisions)
ContainsValueO(n)
IterationO(n)
< Prev Posts