89. How is an ArrayList different than a LinkedList?This is one of the most popular questions, along with the question about the internal structure of a HashMap. No interview is complete without it, so your answer should readily roll off your tongue. In addition to the obvious (they have different names), they differ in their internal structure. Earlier, we discussed the internal structure of both ArrayList and LinkedList, so I won't dive into their implementation details. I'll just remind you that ArrayList is implemented using an internal array whose size increases dynamically according to this formula:
Additionally, the implementation of a LinkedList uses an internal doubly linked list, that is, each element has a reference to the previous and next elements, except for the elements at the start and end of the list. Interviewers love to ask this question like this, "Which is better, ArrayList or LinkedList?" hoping to catch you. After all, if you say one or the other is better, then you've given the wrong answer. Instead, you should clarify the specific situation you are talking about: accessing elements by index or inserting in the middle of the list. Then, depending on their answer, you can explain which one is better. I previously described how ArrayList and LinkedList work in each situation. Let's summarize this by putting them in a row for comparison: Adding an element (add)
<size of the current array> * 3 / 2 + 1
If an index is not specified, then a new item will be automatically added to the end for both kinds of lists. In a LinkedList, the new element will become the new tail (only a pair of references will be rewritten, so the algorithmic complexity is O(1)).
The add method adds an element to the last empty cell in the array (O(1)).
Adding an item by index usually means inserting it somewhere in the middle of the list. In a LinkedList, the method will first search for the desired location by iterating over the elements from the tail and head (O(n/2)) and will then insert the value by overwriting the references of the elements on both sides of where the new element is inserted (O(1)). The overall algorithmic complexity of this operation will be O(n/2).
In the same situation (adding by index), an ArrayList finds the desired location (O(1)) and then shifts all the elements located to the right (including the element already stored at the specified index) to the right by one (which may require the creation of a new internal array and copying elements to it) (O(n/2)). The overall complexity is O(n/2).
Adding an element to the beginning of a LinkedList is similar to adding an element to the end: the new element becomes the new head (O(1)). But for an ArrayList, that operation requires moving all the elements to the right (O(n)).
90. How an ArrayList different than a HashSet?If we could compare ArrayList and LinkedList on an operation-by-operation basis to determine which one is better, we won't find it so easy to make such a comparison between ArrayList and HashSet, because they are completely different collections. You can compare one dessert with another, but comparing a dessert and a savory dish is a challenge — they are painfully different. Still, I will try to point out some of the differences between them:
ArrayList implements the List interface while HashSet implements the Set interface.
ArrayList lets you access an element by index: the get operation has O(1) algorithmic complexity, but HashSet only lets you access a desired element by iteration, which yields algorithmic complexity ranging from O(1) to O(n).
ArrayList allows duplicate elements. In a HashSet, all the elements are unique: any attempt to add an element that is already present in a HashSet will fail (duplicates are checked by hashcode, hence the name of this collection).
ArrayList is implemented using an internal array, but HashSet is implemented using an internal HashMap.
ArrayList maintains the elements' order of insertion, but HashSet is an unordered set and does not maintain the order of elements.
ArrayList allows any number of null values, but you can only add one null value to a HashSet (after all, the elements must be unique).
91. Why does Java have so many different dynamic array implementations?This is more of a philosophical question. We could also ask why do they come up with so many new and varied technologies? For convenience. And the same thing is true about a large number of dynamic array implementations. None of them can be called the best or ideal implementation. Each has its advantages specific situations. Our job is to know their differences and their strengths/weaknesses in order to be able to use the collection that is most suitable for any given situation.
92. Why does Java have so many different key-value storage implementations?Here the situation is the same as with the dynamic array implementations. There are definitely none that are universally better than the others: each has strengths and weaknesses. And we must make the most of their strengths, of course. Example: the concurrent package, which has many multithreaded classes, has its own Concurrent collections. The ConcurrentHashMap class has an advantage over the standard HashMap in terms of safety when working with data in a multi-threaded environment, but that comes at the cost of slower performance. And implementations that aren't the best choice in any situation gradually cease to be used. For example: Hashtable, which was originally intended to be a thread-safe HashMap, has been forgotten and fallen out of use, because ConcurrentHashMap is even better than Hashtable when working in a multi-threaded environment.
93. How do I sort a collection of elements?The first thing to say is that the class representing collection elements must implement the Comparable interface, which consists of the compareTo method. Or you need a class that implements the Comparator interface, including its compare method. Both methods indicate how to compare objects of a given type. This is critical when sorting, because the sorting algorithm needs to understand what principle to use to compare elements. This is mainly done by implementing Comparable directly in the class that you want to sort. Using Comparator is less common. Suppose you're using a class from some library and it doesn't implement Comparable, but you need to sort a collection of its objects. Since you cannot change the code of this class (except by extending it), you can write an implementation of Comparator that indicates how to compare objects of the class. And one more example. If you need to sort objects of the same type in different ways, then you can write multiple Comparator implementations to use in different situations. As a rule, many out-of-the-box classes, e.g. String, already implement the Comparable interface. That means that you don't need to worry about how to compare these classes. You can just go ahead and use them. The first and most obvious way is to use the TreeSet or TreeMap class. These classes store elements in sorted order based on the comparator implemented by the class elements. Don't forget that TreeMap sorts keys, not values. If you use Comparator instead of Comparable, then you need to pass a Comparator object to the collection's constructor when you create it:
But what if you have a different type of collection? How do you sort it? In this case, the Collections utility class's second way — the sort() method — is suitable. The method is static, so all you need is to prepend the name of the class and then pass in the list to be sorted. For example:
TreeSet treeSet = new TreeSet(customComparator);
If you are using an implementation of Comparator rather than Comparable, then you need to pass it in as the second argument:
This operation will change the internal order of the elements in the passed list: the list will be sorted using the comparator. Note that the passed list must be mutable, otherwise the method will fail and throw an UnsupportedOperationException. A third option is to use the Stream class's sorted method, which sorts the collection's elements. If we're using Comparable:
If we're using Comparator:
someList = someList.stream().sorted().collect(Collectors.toList());
The fourth way is to manually implement a sort algorithm, for example, bubble sort or merge sort.
someList = someList.stream().sorted(customComparator).collect(Collectors.toList());
Object class. equals() and hashCode()
94. Give a brief description of the Object class in Java.In the second part of the review, we already discussed the methods of the Object class. Here I will remind you that the Object class is an ancestor of every class in Java. It has 11 methods, which are in turn inherited by all classes.
95. What are equals() and hashCode() used for in Java?hashCode() is a method of Object class that is inherited by all classes. Its job is to generate a number that represents a specific object. An example of this method in action can be found in HashMap, where it is called on key objects to get the local hashcode, which will determine which bucket (cell of the internal array) the key-value pair will be stored in. Also, this method is generally used in the equals() method as one of its main ways to identify objects. equals() is a method of the Object class whose job is to compare objects and determine whether they are equal. This method is used everywhere we need to compare objects, because the standard == comparison operator is not suitable for objects, since it only compares object references.
96. Tell us about the contract between equals() and hashCode() in Java?First, let me say that in order for the equals() and hashCode() methods to work correctly, they must be overridden correctly. Their new implementations must follow these rules:
- Identical objects for which equals returns true must have the same hash codes.
- Objects with the same hash codes are not necessarily equal.