Data Structures

A Pure Computer Science Excursion

Stack

LIFO - Last In, First Out

Simple data structure
You can only see what is on top (peek)
You can only get what is on top (pop)
You only add to the top (push)
No random access
java.util.Stack

Array

Simplest block of data

Simple data structure
Random access by index
Index starts with 0
Fixed size
Limited insert or remove
Primitive type in Java: int[], String[], Object[]...

List

Enhanced array, often called dynamic array

Can be array based
Random access by index
Index starts with 0
Able to grow
Insert and remove supported
Only an interface in Java: java.util.List

Array List

Java implementation name of a regular array list

Array based
Random access by index
Index starts with 0
Able to grow
Insert and remove supported
Insert and remove expensive
java.util.ArrayList

Linked List

Special list for inexpensive insert, move, remove

No random access, no index
Able to grow easily
Insert and remove supported
Insert and remove inexpensive
Random access expensive
Can only read in one direction
java.util.LinkedList

Double Linked List

Special version of linked list for enhanced navigation

No random access, no index
Able to grow easily
Insert and remove supported
Insert and remove inexpensive
Random access expensive
Able to read in both directions
java.util.LinkedList, yeah that is already double linked

Queue

FIFO data structure

No random access, no index
First in, first out
Able to grow easily
Can be size limited
No remove or insert except at both ends
No random access
java.util.Queue

Tree

Search friendly structure

No random access, no index
Always ordered
Expensive navigation
Efficient search
java.util.TreeMap, not a pure tree, but a map with a tree

Hash Map

Key-Value data structure for key access

Random access by key only
You need to know what is in it to get it
Not sorted
Does not support duplicate keys
Very efficient access
java.util.HashMap plus a bunch of similar alternatives with different characteristics

Set

Storage without duplicates

Imagine a set as map without values
Random access by key only
You need to know what is in it to get it
You can test for membership
Not sorted
Does not support duplicate keys
Very efficient access
java.util.HashSet