Question: What is time complexity of different ArrayList operations in terms of big o notation?
|Get||O(1)||FAST:Since ArrayList uses array as underline data structure and array is index based data structure searching in array using array.get(index) will take O(1)|
|Add||O(n)||SLOW:Add operations is slow consider the case if underlying Array is full, we need to copy contents to new array which makes inserting an element into ArrayList of O(n) in worst case, while ArrayList also needs to update its index if you insert something anywhere except at the end of array|
|Contains||O(n)||SLOW: Same reason as above, we need to iterate all the values in order to find the one we are looking for . But it will be 0(1) if the value we are looking for is the first value in the arrayList|
|Remove||O(n)||SLOW: Again we need to iterate the whole arrayList to find the value we want to remove.|
How to describe Array Lists in interview?
How does the size of Arraylist increases automatically? Could you share the code?This is the most trickiest one and many were unable to answer this one. The trick here is the fact that when someone tries to add an object to the arraylist, Java checks to ensure that there is enough capacity in the existing array to hold the new object. If not, a new array of a greater size is created, the old array is copied to new array using Arrays.copyOf and the new array is assigned to the existing array. Look at the code below (taken from
Pay attention to the fact that a new array is created; Objects from old array is copied to the new array and the new array is assigned to the existing array member variable.
6) How do you check whether the given element is present in an ArrayList or not?
ensureCapacity() method is used to increase the current capacity of an ArrayList. However, capacity of an ArrayList is automatically increased when we try to add more elements than the current capacity. To manually increase the current capacity, ensureCapacity() method is used.
We can use indexOf() and lastIndexOf() methods to find out the position of a given element in an ArrayList. indexOf() method returns index of first occurrence of a specified element where as lastIndexOf() method returns index of last occurrence of a specified element in an ArrayList. If element is not found, they will return -1.
add() method which takes index and an element as arguments can be used to insert an element at a particular position of an ArrayList. The elements at the right side of that position are shifted one position right i.e indices of right side elements of that position are increased by 1.
set() method replaces a particular element in an Arraylist with the given element. This method takes two arguments. One is the index of the element to be replaced and another one is the element to be placed at that position.
Question: Are arrayLists thread safe ?If not then how can we make it thread safe?
ArrayList are non- synchronized and therefore are not suited for multithreading environments.
But There are two ways to synchronize an ArrayList explicitly: