About Java Collections
Difference between ArrayList and LinkedList
ArrayList and LinkedList both implements List interface and maintains insertion order. Both are non synchronized classes.
But there are many differences between ArrayList and LinkedList classes that are given below.
ArrayList
1) ArrayList internally uses dynamic array to store the elements.
2) Manipulation with ArrayList is slow because it internally uses array.
3) ArrayList class can act as a list only because it implements List only.
4) ArrayList is better for storing and accessing data.
5>Array List search operation is quicker than Linked List bcoz it is Index based system.
6)Removal or deletion in Linked List is quicker than ArrayList.
7)When huge amount of elements we are using it is better to adopt ArrayList.
8)In Linked List it takes Memory consumption for storing the pointers.
LinkedList:
- LinkedList internally uses doubly linked list to store the elements.
- If any element is removed from the array, all the bits are shifted in memory. Manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory.
- LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
When to Use:
a)ArrayList can be used for high acessing,Inserting and low manipulation.
b)LinkedList can be used for high manipulation and low accessing elements.
ABOUT STACK:
1)Stack follows the LIFO(Last in First Out)
2)peek,pop,push are the methods used in stack.
3)used for calculating postfix and prefix expressions.
4)
Map:
1)To get the elements we use entrySet()method.
2)In Map <k,v> type follows
3)we can set Map collection into anothercollection class easily by setting like
eg:set<Entry<key,value>> then it must take <k,v> in to a single value.
4)keySet()is used to display keys only.
5)For iteration HashMap must be as follows
Eg: for(Map.Entry entry:CollectionObject.entrySet()) to iterate.
HashMap:
1)It consists of <k,v> value pairs they must be stored.
2)hashMap is unSynchronized .
3)It allows only one null key and multiple null values.
4)Insertion order is not preserved up to java 1.7.
LinkedHashMap:
1)it implements Map Interface and extends HashMap Class.
2)Insertion order is maintained in LinkedHashMap.
3)Searching an element is quick in Linked Hashmap.
iteration in index order, allowing duplicates.
ArrayList should be used for random access get(i) or set(i,o) by index.
HashMap are good default choices when random access by element or keyis needed,and sequential access in element or key order is not needed.
Operation LinkedList ArrayList HashMap LinkedHashMap TreeMap
Add(o)(last) O(1) O(1)a
Add(i,o) O(d) O(n-i)a
addFirst(o) O(1)
Put(k,v) O(1)a O(log n)
Remove(o) O(n) O(n) O(1) O(log n)
Remove(i) O(d) O(n-i)
removeFirst() O(1)
Contains(o) O(n) O(n)
ContainsKey(o) O(1) O(log n)
ContainsValue(o) O(n) O(n)
indexOf(o) O(n) O(n)
Get(i) O(d) O(1)
Set(i,o) O(d) O(1)
Get(o) O(1) O(log n)
About this table tells the:
o(1): It is the constant time to complete the operation or task.
o(log n): Time Proportional to the logarthm of n means it takes to insert 2 elements in 1sec (or) 1 element in 2sec. the time taken directly propotional to the data set
not so direct proprtional we dont tell how much it takes to do operation.
o(n): Suppose we take 2 elements it takes 2 sec for 100 elements it takes 100 seconds it depends on the dataset we are giving.
o(d): d is the distance from an index i to the nearest end of the list, that is min(i,n-i), for linked list adding and removing is fast bcoz their d is small.
In ArrayList is fast for only the neat back end. where n-i is small.
o(1)a : Amortized Complexity means over a long sequence of operations the average time it takes o(1), for single operation it could take o(n).
