Java collections cheat sheet

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

This is a small cheat sheet and rules of thumb for using Java Collections Framework

License

nlharri/JavaCollectionsFrameworkCheatSheet

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Java Collections Framework Cheat Sheet

This is a small cheat sheet and rules of thumb for using Java Collections Framework.

All the Java Collections Framework classes implement the Collection interface.

Lists implement the List interface:

• ArrayList
• Vector
• LinkedList (this one implements the Queue and Deque interface as well)

Basic rules of thumb for ArrayList and LinkedList :

• ArrayList is like an array. Meaning that removing entries from the end is fast — internally only the length of the array is shortened. But adding or removing entries from the beginning is slow — internally this means copying all the remaining entries to a new array. If you only want to add or remove items in the end of your list, use ArrayList . ArrayList manages array internally. Accessing elements by index is very fast. Adding item at the beginning takes long time because the items need to be shifted. Near to the end it is faster, because less elements need to be shifted.
• LinkedList : this is based on doubly linked list data structure. If you want to add or remove items anywhere in the list, also in the middle, use LinkedList . If you add items near the end of the list, ArrayList can be more efficient than LinkedList . In LinkedList , each element stores a reference to the previous and to the next element. To get an item at a particular index can be slower, because the list needs to iterate until that item. But adding an item anywhere is fast, because the links need to be changed, but shifting is not needed.
• Vector : it is very similar to ArrayList . The main differences are:
  • Vector is synchronized, ArrayList is not
  • handling of growth of the stored data is different

  Internally, both the ArrayList and Vector hold onto their contents using an Array . When an element is inserted into an ArrayList or a Vector , the object will need to expand its internal array if it runs out of room. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.

  If multiple threads access an ArrayList concurrently then we must externally synchronize the block of code which modifies the list either structurally or simply modifies an element. Structural modification means addition or deletion of element(s) from the list. Setting the value of an existing element is not a structural modification.

  (https://stackoverflow.com/questions/2986296/what-are-the-differences-between-arraylist-and-vector)

  Maps store key-value pairs. Implement the Map interface.

  • HashMap : Does not maintain order.
  • LinkedMap : Behind this there is a doubly linked list. This maintains the order.
  • TreeMap : Will sort the keys in natural order.

  Sets contain elements uniquely. (The same element cannot be in the set more than once.)

  • HashSet : does not retain order
  • LinkedHashSet : keeps the order of insertion
  • TreeSet : Sorts in natural order Set operations like intersection, difference are implemented for sets ( retainAll , removeAll ).
  • LinkedList also implements Queue interface
  • ArrayBlockingQueue has a fix size which can be specified in the constructor
  • Classical way: Iterator
    • Can remove elements during iteration
    • Navigation forward only ( next() method)
    • Cannot change the list during iteration
    • Can change the list during iteration ( remove() , set() , add() )
    • More methods (for example, hasPrevious , previous )

    About

    This is a small cheat sheet and rules of thumb for using Java Collections Framework

    Источник

    Java — Collection Interfaces and Implementations

    This is a quick walk-through tutorial of Java Collections interfaces and their implementations.

    Collection Interfaces

    

    Collection Operations

    It’s good to know what methods each interface offer:

    

    Note that Set doesn’t have get(int index) method because no order is maintained with Set so elements don’t have fixed index.

    Collection Implementations

    Making a Decision in choosing a Collection

    

    Making a decision regarding choosing a Queue implementation is quite straight forward and is not relevant in above diagram. Whenever we need to hold elements prior to processing and just need the method remove() to get and remove elements at the same time we are going to use queues. Also there’s no index based operation to be performed when using queues. If we want to order queue elements in some order then use PriorityQueue, otherwise use ArrayDeque.

    EnumSet is also very straight forward i.e. whenever we want to hold certain elements of an enum we will use it. We can also use other collections for the same purpose but remember EnumSet is very very efficient comparatively.

    Synchronization

    It’s not recommended to use legacy collections. One advantage of using them might seem to be that they are synchronized. java.util.Collections provides methods to wrap any collection around a new collection which is synchronized. These methods are:
    Collection synchronizedCollection(Collection c)
    Set synchronizedSet(Set s)
    SortedSet synchronizedSortedSet(SortedSet s)
    NavigableSet synchronizedNavigableSet(NavigableSet s)
    List synchronizedList(List list)

    Read Only Collections

    java.util.Collections provides methods to wrap any collection and return a new Collection which are read only. Attempts to modify (calling mutative methods), directly or via iterators will cause UnsupportedOperationException . Followings are the methods:
    Collection unmodifiableCollection(Collection c)
    Set unmodifiableSet(Set s)
    SortedSet unmodifiableSortedSet(SortedSet s)
    NavigableSet unmodifiableNavigableSet(NavigableSet s)
    List unmodifiableList(List list)

    In next topics we will explore concurrent collections and then maps.

    Источник

    iSergius / Java Collections Complexity cheatsheet

    This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

    Below are the Big O performance of common functions of different Java Collections.

    List | Add | Remove | Get | Contains | Next | Data Structure

    ———————|——|———|——|———-|——|—————

    ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array

    LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List

    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array

    Set | Add | Remove | Contains | Next | Size | Data Structure

    ———————-|———-|———-|———-|———-|——|————————-

    HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table

    LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List

    EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector

    TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree

    CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array

    ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List

    Queue | Offer | Peak | Poll | Remove | Size | Data Structure

    ————————|———-|——|———-|———|——|—————

    PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap

    LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array

    ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List

    ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List

    ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array

    PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap

    SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None!

    DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap

    LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List

    Map | Get | ContainsKey | Next | Data Structure

    ———————-|———-|————-|———-|————————-

    HashMap | O(1) | O(1) | O(h / n) | Hash Table

    LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List

    IdentityHashMap | O(1) | O(1) | O(h / n) | Array

    WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table

    EnumMap | O(1) | O(1) | O(1) | Array

    TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree

    ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables

    ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List

    Источник

    Читайте также:  Constructor for enum java