Java collections
The goal of this document is to describe when to use the most used java collection data structures
For all data structures in order to work properly is very important synchronization between methods: equals, compareTo, hashCode
when obj1.equals(obj2)==true then should be obj1.compareTo(obj2)==0 and obj1.hashCode()==obj2.hashCode()
|
Interface |
Implementation |
When to use |
||||||||
|
List
An ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position)
|
Algorithm: |
When you do not expect frequent insertion and removal of elements, but expect to add new elements at the end or use the items index.
Performance:
|
||||||||
|
Adding elements in LinkedList is very fast - regardless of the number of elements. We can add fast at the beginning and end of the list (unlike the ArrayList <T>). Search and delete is slow
Performance:
|
||||||||||
|
Set
A set is a collection that cannot contain duplicate elements |
Algorithm: Hash Table |
Elements are not ordered. Fast for add, search and remove
Performance:
|
||||||||
|
Algorithm: Balanced Tree |
The elements in a set are sorted, but slower on add, search and remove because needs to perform sorting every time there is change
Performance:
|
|||||||||
|
Algorithm: Linked List |
Between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1). Slow on inserted or deleted
|
|||||||||
|
Map
An object that maps keys to values. A Map cannot contain duplicate keys. Each key can map to at most one value
|
Fast add, search, delete but not ordered
Performance:
|
|||||||||
|
Algorithm: Balanced Tree |
Ordered elements but slower for add, search, delete(О(log(N)))
Performance:
|
Implementation algorithm
- Hash Table - data structure used to implement an associative array, a structure that can map keys to values. For each key object using a hash function is computed an index, from which the desired value can be found.
- Resizeable Array - could choose the initial array capacity, doubling the size each time the internal array is full
- Balanced Tree - Red-Black tree algorithm is used. wiki
- Linked List - linked data structure that consists of a set of sequentially linked records called nodes.Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.wiki
|
Interfaces |
||||
|
Set |
||||
|
List |
||||
|
Map |
Performance matrix
- O(1) - For performing an operation required constant number of steps (e.g., 1, 5, 10 or another number), and this number does not depend on the amount of input data.
- O(log(N)) - To perform an operation on the N elements are necessary number of steps of the order of log (N), wherein the base of the logarithm is the most commonly 2.
- O(N) - To perform an operation on N elements needed approximately as many steps as are the elements.
structure
add
search
delete
Index access
Array
O(N)
O(N)
O(N)
О(1)
LinkedList
О(1)
O(N)
O(N)
O(N)
ArrayList
О(1)
O(N)
O(N)
O(1)
Stack
О(1)
-
О(1)
-
Queue
О(1)
-
О(1)
-
HashMap
О(1)
О(1)
О(1)
-
TreeMap
О(log(N))
О(log(N))
О(log(N))
-
HashSet
О(1)
О(1)
О(1)
-
TreeSet
О(log(N))
О(log(N))
О(log(N))
-
- O(1) - For performing an operation required constant number of steps (e.g., 1, 5, 10 or another number), and this number does not depend on the amount of input data.
- O(log(N)) - To perform an operation on the N elements are necessary number of steps of the order of log (N), wherein the base of the logarithm is the most commonly 2.
- O(N) - To perform an operation on N elements needed approximately as many steps as are the elements.
|
structure |
add |
search |
delete |
Index access |
|
Array |
O(N) |
O(N) |
O(N) |
О(1) |
|
LinkedList |
О(1) |
O(N) |
O(N) |
O(N) |
|
ArrayList |
О(1) |
O(N) |
O(N) |
O(1) |
|
Stack |
О(1) |
- |
О(1) |
- |
|
Queue |
О(1) |
- |
О(1) |
- |
|
HashMap |
О(1) |
О(1) |
О(1) |
- |
|
TreeMap |
О(log(N)) |
О(log(N)) |
О(log(N)) |
- |
|
HashSet |
О(1) |
О(1) |
О(1) |
- |
|
TreeSet |
О(log(N)) |
О(log(N)) |
О(log(N)) |
- |