Java Data Structures

Interface List

Exist two most used implementation of this interface it is ArrayList and LinkedList. Let's go deeper about each

ArrayList

From the name of this structure we understand that internal it use simple array.
But this structure have a dynamic sizing. It is allowed by ensureCapacity() method which increase a used simple array. When this methods calls - it check loaded of the used array and if needed create a new array with capacity equals to current + 60% of the current. By the calling System.arraycopy method we copy all elements from the old array to the the new. Getting, removing element takes O(1) - constant time, because we have a simple array. Find by index operation takes O(n) operations, because we must travers for all array.

LinkedList

This structure based on object which have links to the next and previous objects in the list. This structure have only one benefits from ArrayList, inserting at the begin execute faster than it execute at the ArrayList. So, this structure may be good for some tasks, but I have not faced with this tasks.

Stack

This structure provide for us next methods - push, pop, poll. Also, it is implement a LIFO, which means last in - first out. For example if we put a the stack elements 10,2,123 - by call pop or roll we get 123. But pop remove 123 from the stack. Poll not remove element from the stack. At the internal it use a simple array.

Interface Set

This data structures created for store only unique elements. How to check that element is not contained at the collection. For this we have a few implementation. Let's talk about it. First HashSet implementation will be compare elements by calling equals from the object. Second TreeSet may store only elements which implements Comparable interface, or you must be provide an comparator through constructor implementation for your TreeSet.

HashSet

Inside it use HashMap, which may store only unique keys. This structure does not guarantee insertion order, this means which try to traverse this collection we get element at the other order from insertion order. This implementation of have a constant time for basic operation - add, remove, contains, size. It provided by hash function which executed for the constant time.

TreeSet

If HashSet based on the HashMap, then TreeSet based on TreeMap. This data structures guarantee time O(log(n)) for operations such as add, remove and contains. This provided because at the TreeMap uses Tree. This collection guarantee natural ordering. For example:

Set numbers = new TreeSet<>();

numbers.add(2);

numbers.add(1);

for(Integer number : numbers) { System.out.println(number);} 

At the console will be printed

1
2

LinkedHashSet

This collection famous for next - unlike previous implementation it guarantee insertion order. So, by the iterating over this data structure you will see your elements in it's insertion order. Like a previous set implementation, inside using LinkedHashMap. When we try to add element, alredy added to the collection - this action does not affect order of the elements. For the basic operation it provide a contant time O(n) for add, remove, contains operations. Allow to contain null elemnents. For performance of this collection uses two variables - initialCapacity and loadFactor. First describe an initial capacity of the internal used map, second declare when count of the bucket uses at the map must be increased.

EnumSet

This implementation created specially for Enum type. Each mass operation such as containsAll, retainAll will be execute faster if you pass to this method EnumSet instance. When iterate over this set you will be see natural ordering of the element. Returned iterator not throw ConcurrenctModificationException. Also iterator may show modification and may not show modification. All basic operations executed at the contant time.

NavigableSet

This implementation have a good options such as navigation on the set. It means that we may get element which lower or bigger than we provided. Also we may get set of the elements which bigger or lower that we provided. Also we may reversed this collection by calling descendingSet method

Interface Queue

This collection use FIFO mechanism which means that first in, first out. We may store at this collection element before some operations on its. Exist all basic operations such as add, remove. However, this methods exists at the two version. First version thrown exception if operation is failed, another version not thrown exception and return a special value such as null. Permits to add null to this structure. However, LinkedList which implement this interface allow to us insert null elements. This method not provided methods for concurrent access to it. For use queue at the concurrent environment use BlockingQueue which provide method for blocking.

Deque

This implementation allow to us work with both end of the queue - start and finish. DE is acronym for double ended. May created stricted size queue, also may create a dynamic size queue. Also as Queue exist two version of the methods for the basic operations. One version throw exception if operation failed, another version return special value which signal for us that operation is failed. Index access is absent.

ArrayQueue

From the name for us clear understand that this queue based on simple array. Does not bound of the size and ensure capacity of the array if needs. More operations executed for amortizated time.

PriorityDeque

Main principle work of this queue implementation is when we add new element to the collection will be call sort method for correct order at the collection. What is priority at this context? Simple, as TreeSet you element must be comparable by some attribute which you must choosed or you must be provide comparator for correct order of your elements at this collection. When you call methods poll(not remove from this collection) you got element which have a greatest priority at the current moment. This collection provided logariphm speed for operations such as add/offer, remove/pull and linear time for operations such as contains.

Interface Map

HashMap

From the name clear to us this structure inside use hash function. Also this structure allow to us put null elements as key or value. When iterate over this you will see elements not at the insertion order. For performance of this structure use two parameters which passed to it through constructor. It is load factor and initial capacity. Initial capacity determine count of the buckets. Load factor determine when will be call method for ensure count of the buckets.

ConcurrentHashMap

This map implementation needs for concurrent usage. Instead hash map this is thread-safe implementation of the map. Entity of this map marked as volatile which means that all thread must have actual version of this entity.

NavigableMap

This interface extends SortMap interface and added methods for navigate across map elements - lowerEntry, floorEntry, ceilingEntry, higherEntry. This methods may return null. May traverse at the straight and reversed order by calling descendingMap. Also have navigate method which provide method for extract part of the map such as map. Lower and higher boundaries inclusive at the (sub/head/tail)Map methods. It is have methods for get last and first elements, as at the Queue exist two version of this methods.

TreeMap

It is red-black tree which based on navigable map. Elements are sorted in natural ordering or by the comparator which must be provided across constructor.

Common

All of this structure, exclude ConcurentHashMap is not thread safe. Which means if you would like have a few thread which must have a shared resource. All of this is not suitable for your task.

Also noticed when you try to modify collections at the traverse operation you got ConcurrentModificationException which signal for you that you try change collection at the traverse operation. It is not allowed! For this operation we must use concurrent data structures located at the specially package of the java.

UPD:
Also noticed at the comment ConcurrentModificationException will be thrown when you at the loop for iterate try to remove element. For if you would like remove some elements from the collection at the iteration. Should use iterator:

while(iterator.hasNext()) {
    if (iterator.next() == 1) {
        iterator.remove();
    }
}

Thank for you!

Follow me on the twitter: @VoronyanskyE

Comments

[Martin Häusler]

A nice summary!

One small comment: a ConcurrentModificationException does not only occur when two threads access the same collection. It may also happen that your own (single-threaded) code iterates over a collection, and makes changes to it during the iteration.

For example:

for(Object element : collection){
    collection.remove(element);
}

This snippet will always throw a ConcurrentModificationException (except for empty collections) even though only a single thread is at work. We are mutating the collection while an iterator is still active. Maybe specialized collections, such as the CopyOnWriteArrayList, can survive this loop without throwing an exception, but the general Collection contract specifies that this is an invalid case.

[Yegor Voronianskii]

Thank you, I am update the post

[Hamidur Rahman]

Time complexity of TreeSet guarantees O(log n) not O(n)

[Yegor Voronianskii]

Oh, thank. You are true.

[Hamidur Rahman]

Since LinkedHashSet is designed/implemented on a HashTable Structure it is possible to be O(1) but it can easily be O(n) depending on a hash()

[Yegor Voronianskii]

At the docs.oracle.com/javase/7/docs/api/... we see that is provide contant time for basic operation, and O(n) for iteration over a LinkedHashSet that means next require time proportional to the size of the set

[Hamidur Rahman]

Then I think you meant constant time O(1) for add, contains, and remove. Iteration on any structure is always O(n).

[Yegor Voronianskii]

Yeah! for this operation I meant

[Jan Wedel]

Thanks for the interesting article. Usually, I tend to use LinkedList when I mostly appending a lot of items of which the size I don’t know and/or when I iterate over all elements. When I’m doing a lot of random accesses, I use ArrayList. In your table, both list implementations have O(1), is that still true when the whole array needs to be copied due expansion? And what about actual time? Do you know any benchmarks for different use cases? I really would be interested.