Java

Collection Questions

Q: ArrayList v/s Vector

A: Vector and ArrayList both uses Array internally as data structure. They are dynamically resizable. Difference is in the way they are internally resized. By default, Vector doubles the size of its array when its size is increased. But, ArrayList increases by half of its size when its size is increased.

http://stackoverflow.com/questions/2986296/what-are-the-differences-between-arraylist-and-vector

Basis Vector ArrayList
Synchronization  Yes, it’s all methods are synchronized It’s not thread safe
Performance Slow Fast
Automatic Increase in Capacity It doubles its size It increases its size by 50 %
Enumerator Yes, both Iterator and Enumerator Only Iterator

 

Q: LinkedList V/s ArrayList

A:LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.Advantage:LinkedList’s ability to insert and delete elements in the middle of the list relatively quickly, once you’ve navigated there with a ListIterator.

ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Basis LinkedList ArrayList
get(int index) O(n) O(1) à main benefit of ArrayList<E>
add(E element) O(1) O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) O(n) O(n – index) amortized, but O(n) worst-case
remove(int index) O(n) O(n – index) (i.e. removing last is O(1))
Iterator.remove() O(1) à main benefit O(n – index)
ListIterator.add(E element) O(1) à main benefit O(n – index)

 

Q: What is natural ordering?

“Natural” ordering is the ordering implied by the implementation of the Comparable interface by the objects used as keys in the TreeMap. Essentially, RBTree must be able to tell which key is smaller than the other key, and there are two ways to supply that logic to the RBTree implementation:

1.Implement Comparable interface in the class(es) used as keys to TreeMap, or

2.Supply an implementation of the Comparator that would do comparing outside the key class itself.

Natural ordering is the order provided by the Comparable interface .If somebody puts the key that do not implement natural order then it will throw ClassCastException.

 

Q: Which data structure you will prefer in your code: HashMap or TreeMap?

HashMap is faster while TreeMap is sorted .Thus we choose them according to their advantage.

If you do not want to sort the elements but just to insert and retrieve the elements then use HashMap.

But if you want to maintain the order of the elements then TreeMap should be preferred because the result is alphabetically sorted .While iterating HashMap there is no ordering of the elements,on the other hand, TreeMap iterates in the natural key order.

 

Q:What happens if the TreeMap is concurrently modified while iterating the elements? 

The iterator fails fast and quickly if structurally modified at any time after the iterator is created (in any way except through the iterator’s own remove method). We already discussed the difference between Fail-fast and Fail safe iterators.

 

Q: Why java’s Treemap does not allow an initial size?

HashMap reallocates its internals as the new one gets inserted while TreeMap does not reallocate nodes on adding new ones. Thus, the size of the TreeMap dynamically increases if needed, without shuffling the internals. So it is meaningless to set the initial size of the TreeMap.

 

Q: Which copy technique (deep or shallow) is used by the TreeMapclone() method?

clone() method returns the shallow copy of the TreeMap instance . In shallow copy object B points to object A location in memory. In other words, both object A and B are sharing the same elements .The keys and values themselves are not cloned.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s