
Collections
84. Tell us about iterators and how they are used
Collections is a favorite topic in any Java developer interview. When answers questions about the collection hierarchy, candidates often say that it starts with the Collection interface. But this is not so. There is another interface one level above: Iterable. This interface consists of the iterator() method, which lets you access the Iterator object for the current collection. And what exactly is this Iterator object? The Iterator object provides the ability to move through a collection and iterate over its elements, and the user doesn't need to know the specific implementation details of the collection. In other words, it is a kind of pointer to the collection's elements, as if it is peeking inside at one of them. The iterator has methods such as:hasNext() — returns true if the iteration has another element (this method lets you know when you've reached the end of the collection);
next() — returns the next item in the iteration. If there isn't one, then a NoSuchElementException is thrown. That means that before you use this method, it is best to use the hasNext() method to make sure a next element exists;
remove() — removes from the collection the last element received using the next() method. If next() has never been called, then calling remove() will cause an IllegalStateException to be thrown;
forEachRemaining(<Consumer>) — executes the passed action on each element of the collection (this method appeared in Java 8).
List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
iterator.next();
iterator.remove();
}
System.out.println(list.size());
The console will display the following:
iterator.forEachRemaining(x -> System.out.print(x));
But once we do this, the iterator becomes unsuitable for further use: it has traversed the entire list, and an ordinary iterator has no methods for iterating backwards.
And that makes for a nice segue into a discussion of LinkedList, specifically, its listIterator() method, which returns an enhanced type of iterator: ListIterator.
In addition to the methods of a regular (standard) iterator, this kind has the following:
add(<Element>) — adds a new element to the list;
hasPrevious() — returns true if there is an element located before the next element (if there is a previous element);
nextIndex() — returns the index of the next element;
previous() — returns the previous element (the one before the next element);
previousIndex returns the index of the previous element.
set(<Element>) — replaces the last element returned by next() or previous().

85. What collection hierarchy exists in the Java Collection Framework?
There are two collection hierarchies in Java. The first hierarchy is the Collection hierarchy, which has the following structure:
Set is an interface that describes a set, a data structure that contains unordered unique (non-repeating) elements. This interface has some standard implementations: TreeSet, HashSet, and LinkedHashSet.
List is an interface describing a data structure that stores an ordered sequence of objects. Objects in a List can be inserted and removed by their index in the list (like an array, but with dynamic resizing). This interface also has some standard implementations: ArrayList, Vector (deprecated and not actually used), and LinkedList.
Queue is an interface describing a data structure that stores items in a First In First Out (FIFO) queue. This interface has the following standard implementations: LinkedList (that's right, it also implements Queue) and PriotityQueue.


86. What is the internal structure of an ArrayList?
An ArrayList is like an array, but it can expand dynamically. What does that mean? Under the hood, ArrayList uses an ordinary array, i.e. it stores its elements in an internal array whose default size is 10 cells. Once the internal array is full, a new array is created. The size of the new array is determined by this formula:
<size of the current array> * 3 / 2 + 1
So, if the size of our array is 10, then the size of the new one will be: 10 * 3 / 2 + 1 = 16.
Then all values from the original (old) array are copied into it using the built-in System.arraycopy() method, and the original array is deleted.
In a nutshell, that is how ArrayList implements dynamic resizing.
Let's consider the most popular ArrayList methods:
1. add(<Element>) — adds an element to the end of the array (in the last empty cell), after first checking whether there is an available cell in the array. If not, a new array is created, and the elements are copied into it.
The time complexity of this operation is O(1).
There is a similar add(<Index>, <Elelement>) method. It adds an element not to the end of the list (array), but to the specific cell indicated by the index that came in as an argument.
In this case, the time complexity will vary depending on where you add:- if the add is close to the beginning of the list, then the time complexity will be close to O(N), because all the elements located to the right of the new one will have to be moved one cell to the right;
- if the element is inserted in the middle, then it will be O(N/2), since we only need to shift half of the list items one cell to the right.
87. What is the internal structure of a LinkedList?
An ArrayList contains elements in the internal array, but a LinkedList stores them in a doubly-linked list. This means that each element contains a link to the previous element and to the next element. The first element does not link to a previous element (after all, it is the first). It is also considered the head of the list, and the LinkedList object has a direct reference to it. Similarly, the last element does not have the next element, since it is the tail of the list. The LinkedList object also references it directly. This means that the time complexity of accessing the head or tail of a list is O(1).

- if it is close to the head or tail, the operation will approach O(1), since it will not actually be necessary to iterate over the elements;
- if it is close to the middle, then we will have O(N/2), since the method will search from the head and tail at the same time until the desired element is found.

88. What is the internal structure of a HashMap?
This may be one of the most popular interview questions to ask Java developer candidates. A HashMap works with key-value pairs. How are they stored inside the HashMap itself? A HashMap has an internal array of nodes:
Node<K,V>[] table
By default, the size of the array is 16, and it doubles each time it is filled with elements (that is, when the LOAD_FACTOR is reached; it specifies the threshold for how full the array can get — by default, it is 0.75).
Each of the nodes stores a hash of the key, the key, a value, and a reference to the next element:

- The cell is empty — in this case, the new Node value is stored in it.
- The cell is not empty — in this case, the values of the keys are compared. If they are equal, then the new Node value overwrites the old one; if not equal, then the next is accessed, and its key is compared... And so on, until the new value either overwrites some old value or we reach the end of the singly linked list and then store the new value there as the last element.


GO TO FULL VERSION