ArrayList
The ArrayList in Java is backed by an array.
This implementation of the List interface is very useful when working with multi-threaded applications.
LinkedList is a linear data structure which consists of nodes holding a data field and a reference to another node
-K Himaanshu Shuklaa..
The ArrayList in Java is backed by an array.
- add() takes O(1) time
- add(index, element) in average runs in O(n) time
- get() is always a constant time O(1) operation
- remove() runs in linear O(n) time. We have to iterate the entire array to find the element qualifying for removal
- indexOf() also runs in linear time. It iterates through the internal array and checking each element one by one. So the time complexity for this operation always requires O(n) time
- contains() implementation is based on indexOf(). So it will also run in O(n) time
This implementation of the List interface is very useful when working with multi-threaded applications.
- add() depends on the position we add value, so the complexity is O(n)
- get() is O(1) constant time operation
- remove() takes O(n) time
- contains() likewise, the complexity is O(n)
LinkedList is a linear data structure which consists of nodes holding a data field and a reference to another node
- add() supports O(1) constant-time insertion at any position
- get() searching for an element takes O(n) time
- remove() removing an element also takes O(1) operation, as we provide the position of the element
- contains() also has O(n) time complexity.
LIST
|
Add at last index
|
Add at specific
index
|
Remove by value/
index
|
Get
|
Contains
|
Data Structure
|
|
ArrayList
|
O(1)
|
O(n)
|
O(n)
|
O(1)
|
O(n)
|
Array
|
|
LinkedList
|
O(1)
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
Linked List
|
|
CopyonWriteArrayList
|
O(n)
|
O(n)
|
O(1)
|
O(n)
|
Array
|
||
SET
|
Add/Remove
|
Contains
|
Next
|
Data Structure
|
HashSet
|
O(1)
|
O(1)
|
O(h/n)
|
Hash Table
|
LinkedHashSet
|
O(1)
|
O(1)
|
O(1)
|
Hash Table + Linked
List
|
EnumSet
|
O(1)
|
O(1)
|
O(1)
|
Bit Vector
|
TreeSet
|
O(log n)
|
O(log n)
|
O(log n)
|
Red-black tree
|
CopyonWriteArraySet
|
O(n)
|
O(n)
|
O(1)
|
Array
|
ConcurrentSkipList
|
O(log n)
|
O(log n)
|
O(1)
|
Skip List
|
QUEUE
|
Offer
|
Peak
|
Poll
|
Size
|
Data Structure
|
PriorityQueue
|
O(log n )
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
ArrayDequeue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Linked List
|
ConcurrentLinkedQueue
|
O(1)
|
O(1)
|
O(1)
|
O(n)
|
Linked List
|
ArrayBlockingQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Array
|
PriorirityBlockingQueue
|
O(log n)
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
SynchronousQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
None!
|
DelayQueue
|
O(log n)
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
LinkedBlockingQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Linked List
|
MAP
|
Get
|
Contains
|
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
|
No comments:
Post a Comment