Data Structures

[lveay2]

Arrays

• Arrays.asList() convert from array to List
• Arrays.sort()

Stack

• last-in-first-out
• push, pop, peek, search

Queue (Priority Queue)

• first-in-first-out
• add, offer, remove, pool, element, peek

List (ArrayList, LinkedList, Vector)

• ordered collection
• allow duplicate element
• allow null element
• add, get, remove
• List list = Collections.synchronizedList(new ArrayList());

Set (*HashSet, TreeSet, LinkedHashSet)

• not duplicate element
• at most one null element
• add, remove
• contains
• Set s = Collections.synchronizedSet(new HashSet(...));

Map(*HashMap, TreeMap, LinkedHashMap, HashTable)

• key-value pair data structure
• cannot contain duplicate keys
• each key can map to at most one value
• put, remove, get
• entrySet, keySet
• containsKey, containsValue
• Map m = Collections.synchronizedMap(new HashMap());

Collections make data structure thread safe

• Collection c = Collections.synchronizedCollection(myCollection);

Thread-safe Data Structures

• Vector
• CopyOnWriteArrayList
• CopyOnWriteArraySet
• ConcurrentHashMap
• PriorityBlockingQueue
• ArrayBlockingQueue
• LinkedTransferQueue
• CopyOnWriteArrayList
• CopyOnWriteArraySet

[lveay2]

关于Java集合的小抄 http://calvin1978.blogcn.com/articles/collection.html [Java基础要义]HashMap、LinkedHashMap元素遍历机制探讨 http://blog.csdn.net/luanlouis/article/details/43017071 深入理解 hash 函数、HashMap、LinkedHashMap、TreeMap http://blog.csdn.net/zq602316498/article/details/39351363 教你透彻了解红黑树 https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

[lveay2]

Arrays

• Set, Check element at a particular index: O(1)
• Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used,
• As pointed out by Aivean, there is no Delete operation available on Arrays. We can symbolically delete an element by setting it to some specific value, e.g. -1, 0, etc. depending on our requirements
• Similarly, Insert for arrays is basically Set as mentioned in the beginning

ArrayList:

• Add: Amortized O(1)
• Remove: O(n)
• Contains: O(n)
• Size: O(1)

Linked List:

• Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)

Doubly-Linked List:

• Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)

Stack:

• Push: O(1)
• Pop: O(1)
• Top: O(1)
• Search (Something like lookup, as a special operation): O(n) (I guess so)

Queue/Deque/Circular Queue:

• Insert: O(1)
• Remove: O(1)
• Size: O(1)

Binary Search Tree:

• Insert, delete and search: Average case: O(log n), Worst Case: O(n)
• Red-Black Tree:
• Insert, delete and search: Average case: O(log n), Worst Case: O(log n)

Heap/PriorityQueue (min/max):

• Find Min/Find Max: O(1)
• Insert: O(log n)
• Delete Min/Delete Max: O(log n)
• Extract Min/Extract Max: O(log n)
• Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST

HashMap/Hashtable/HashSet:

• Insert/Delete: O(1) amortized
• Re-size/hash: O(n)
• Contains: O(1)

Reference: https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures