PS: If you like the page or have any questions, feel free to comment at end of the page.
Collections in Java offer some of the most comprehensive suites of built-in Data structures. Often this is the most common topic amongst interviewers. Good foundation and understanding of java collections help developer in building efficient programs.
Q1) What is the difference between an ArrayList and a vector?
Ans)
Synchronization - ArrayList is not thread-safe whereas Vector is thread-safe. In Vector class each method like add(), get(int i) is surrounded with a synchronized block, thus making Vector class thread-safe.
Data growth - Internally, both the ArrayList and Vector hold onto their contents using an Array. This means that the collection is of fixed size. When the collection is coming to near it's max capacity it dynamically resizes itself. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.
Performance - Since Vector is thread-safe, the performance is slower than ArrayList.
Q2) How can an ArrayList be synchronized without using Vector?
Ans) Arraylist can be synchronized using:
Collections.synchronizedList(List list)
//Other collections can be synchronized:
Collections.synchronizedMap(Map map)
Collections.synchronizedCollection(Collection c)
Q3) If an Employee class is present and its objects are added in an ArrayList. Now I want the list to be sorted on the basis of the employeeID of Employee class. What are the steps?
One way to achieve is by using Comparable interface. Implement Comparable interface to the Employee class and override the compareTo(Object obj) method in which compare the employeeID.
class Employee implements Comparable<Employee> {
private int id;
private String name;
public int compareTo(Employee e1) {
return this.id == e1.id;
}
}
Now call Collections.sort() method and pass the list as an argument.
Now consider that Employee class is a jar file.
Since Comparable interface cannot be implemented, create Comparator and override the compare(Object obj, Object obj1) method.
Call Collections.sort() on the list and pass comparator as an argument.
class EmployeeComparator implements Comparator<Employee> {
public int compare(final Employee e1, final Employee e2) {
return this.e1.id == e2.id;
}
}
//some class
List<Employee> employees = new ArrayList();
//add employee to employees
//sort the employees
Collections.sort(employess, new EmployeeComparator());
Q4)What is the difference between HashMap and HashTable?
Ans) Both collections implements Map. Both collections store value as key-value pairs.
The key differences between the two are:
Hashmap is not synchronized in nature but hashtable is(thread-safe). This means that in a multithreaded application, only one thread can get access to a hashtable object and performs an operation on it. Hashmap doesn't guarantee such behavior and is not used in multithreaded environment.
Hashmap is traversed using an iterator, hashtable can be traversed by enumerator or iterator.
Iterator in hashmap and hashtable is fail fast but enumerator in hashtable isfail safe.
HashMap permits null values and only one null key, while Hashtable doesn't allow key or value as null.
Since hashtable is synchronized, it is relatively slower in performance than hashmap
Q5) What are the classes implementing the List interface?
Ans) There are three implementations of the List interface:
ArrayList : It is a resizable array implementation. The size of the ArrayList can be increased dynamically also operations like add, remove and get can be formed once the object is created. It also ensures that the data is retrieved in the manner it was stored. The ArrayList is not thread-safe.
Vector: It is the thread-safe implementation of ArrayList. The methods are wrapped around a synchronized block.
LinkedList: the LinkedList implements Queue interface too and provide FIFO (First In First Out) which mean than element is always removed from the head of the list and element is added at the end of the list. It is faster than ArrayList for add and remove operation as time complexity is O(1). But for searching or getting an element the average time complexity is O(n) where n is the size of the list.
Q6) Which all classes implement the Set interface ?
Ans) A Set is a collection that contains no duplicate elements. More formally, a set contains no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. HashSet, SortedSet and TreeSet are the commonly used class which implements Set interface.
SortedSet - It is an interface which extends Set. As the name suggests, the interface allows the data to be iterated in the ascending order or sorted on the basis of Comparator or Comparable interface. All elements inserted into the interface must implement Comparable or Comparator interface.
TreeSet - It is the implementation of SortedSet interface. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). The class is not synchronized. The class uses Red-Black tree data structure.
HashSet: This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets
Q7) What is the difference between List and a Set?
A list can contain duplicate values but Set doesn't allow duplicates.
A list allows retrieval of data to be in same order of insertion but Set doesn't ensures the order in which the elements can be retrieved.(Except HashSet)
Q8) What is the difference between Arrays and ArrayList ?
Arrays are created of fix size whereas ArrayList is dynamic in nature and can vary its length. Also the size of an array cannot be incremented or decremented. But ArrayList has the ability to dynamically increase its capacity and insert more elements.
Once the array is created elements cannot be added or deleted from it. But with ArrayList the elements can be added and deleted at runtime.
List list = new ArrayList();
list.add(1);
list.add(3);
list.remove(0) // will remove the element from the 1st location.
ArrayList is one-dimensional but an array can be multidimensional.
int[][][] intArray= new int[3][2][1]; // 3 dimensional array
An Array can contain objects of a single data type or class. ArrayList if not used with generic can contain objects of different class types.
Q9) When to use ArrayList or LinkedList ?
Insertion: Adding new elements is pretty fast for either type of list. Inserting an element to the start of end of the ArrayList takes O(1). Inserting in middle of an ArrayList is operation of O(n). Inserting an element in Linkedlist takes O(1).
Access: For the ArrayList, getting an element from the index i is faster O(1) because each element has an index and can be accessed directly with an index but for LinkedList lookup time complexity isO(n). It's slow because elements are accessed in an sequential manner and always access starts from the head of the list.
Deletion:Time complexity of deletion in arraylist is O(n). This is because all remaining elements in the underlying array of Object instances must be shifted to the left after each remove operation. Linkedlist has time complexity of O(1) because deletion can be done by updating the pointers of prev and next elements.
So an ArrayList works best for cases where you're doing random access on the list and a LinkedList works better if you're doing a lot of editing in the middle of the list.