-
Notifications
You must be signed in to change notification settings - Fork 28
/
Copy pathCollection interface class methods
78 lines (67 loc) · 2.45 KB
/
Collection interface class methods
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
Queston :
What is the time complexity of methods of classes which implements Collection interface
VERY IMP Sources:
http://www.javaexperience.com/time-complexity-of-collection-classes/
http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/
http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-19-data-structures-and-algorithm-complexity/
Solution:
Java ArrayList time complexity :
Read/Search any element O(n). If you know the index then the complexity is O(1)
Update : O(n)
Delete at beginning: O(n)
Delete in middle: O(n)
Delete at end: O(n)
Add at beginning: O(n)
Add in middle: O(n)
Add at end: O(n)
Linked List time complexity : It has elements linked in one direction so as to provide ordered iteration
of elements.
Read/Search any element O(n)
Update : O(n)
Delete at beginning: O(1)
Delete in middle: O(n)
Delete at end: O(n)
Add at beginning: O(1)
Add in middle: O(n)
Add at end: O(n)
HashMap time complexity : The elements are placed randomly as per the hashcode. Here the assumption is
that a good implementation of hashcode has been provided.
Read/Search any element O(1)
Update : O(1)
Delete : O(1)
Add : O(1)
LinkedHashMap time complexity : The elements are placed randomly as with HashMap but are linked together
to provide ordered iteration of elements.
Read/Search any element O(1)
Update : O(1)
Delete : O(1)
Add at beginning: O(1)
Add in middle: O(n)
Add at end: O(n)
HashSet time complexity : The elements are distributed randomly in memory using their hashcode.
Here also the assumption is that good hashcode which generated unique hashcode for different
objects has been provided.
Read/Search any element O(1)
Update : O(1)
Delete : O(1)
Add : O(1)
LinkedHashSet time complexity : It is same as HashSet with the addition of links between the elements of the Set.
Read/Search any element O(1)
Update : O(1)
Delete : O(1)
Add at beginning: O(1)
Add in middle: O(n)
Add at end: O(n)
TreeMap time complexity : Provides natural sorting of elements. Uses equals, compare and compareTo
methods to determine the sorting order.
Read/Search any element O(log n)
Update : O(log n)
Delete : O(log n)
Add : O(log n)
TreeSet time complexity : Internally used an instances of TreeMap with the elements as key and a dummy
value for all entries in the TreeMap.
Read/Search any element O(log n)
Update : O(log n)
Delete : O(log n)
Add : O(log n)