The article is a translation of the article
" Top 10 questions about Java Collections " . Below are the most popular questions about collections in Java, asked and discussed on Stackowerflow. Before you look at these questions, it would be good to look at the class hierarchy diagram.
1. When to use LinkedList instead of ArrayList?
An ArrayList is in fact an array; its elements can be accessed directly by index. If the array overflows, a new one with more space becomes necessary. Placing and moving all elements will take O(n) time. Also, adding and removing elements is necessary to move existing elements in the array. This is perhaps the biggest inconvenience of using ArrayList. LinkedList is a double list of element links. Thus, to access the element in the center, you have to search from the very beginning to the end of the sheet. On the other hand, adding and removing an element in a LinkedList is faster because these operations only change the list itself. The worst times are compared below:
| Method |
Arraylist |
LinkedList |
| get(index) |
O(1) |
O(n) |
| add(E) |
O(n) |
O(1) |
| add(E, index) |
O(n) |
O(n) |
| remove(index) |
O(n) |
O(n) |
| Iterator.remove() |
O(n) |
O(1) |
| Iterator.add(E) |
O(n) |
O(1) |
Despite the running time, memory usage must be considered individually for large lists. In a LinkedList, each node must have at least two additional pointers to link the previous and next nodes, while in an ArrayList, only an array of elements is needed. More comparisons of ArrayList, LinkedList and Vector
lists .
2. Efficient equivalent for removing elements during collection iteration The only correct way to modify (remove elements) a collection during iteration is to use
Iterator.remove() . For example: The most common error is: You will get
a ConcurrentModificationException while running the code above. This happens because the iterator was generated to move through the entire list, but at the same time the sheet is changed by calling Iterator.remove(). As written in the documentation for this exception,
Iterator
itr = list.iterator(); while(itr.hasNext()) { // do something itr.remove(); }
for(Integer i: list) { list.remove(i); }
"it is not generally permissible for one thread to modify a collection while another thread is iterating over it."
In general, it is unacceptable for one thread to modify a collection while another thread is traversing it.
3. How to convert List to int[] array? The easiest way to do this is to use
ArrayUtils , located in the
Apache Commons Lang library .
int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0])); There is no shortcut for this expression in the JDK. Remember that you can't use List.toArray() because this expression converts List to Integer[] (which is
not a primitive type). The correct way would be the following option:
int[] array = new int[list.size()]; for(int i=0; i < list.size(); i++) { array[i] = list.get(i); }
4. How to convert an int[] array to a List? The easiest way is also to use
ArrayUtils in the
Apache Commons Lang library , as above.
List list = Arrays.asList(ArrayUtils.toObject(array)); Also, there is no shortcut for this expression in the JDK.
5. What is the best way to filter the collection? You can use third party packages such as
Guava or
Apache Commons Lang to increase functionality. Both of these packages have a filter() method (in the
Collections2 class from Guava and
CollectionUtils from Apache). The filter() method will return elements that match the given Predicate. In JDK everything is more complicated. The good news is that predicates will be added in Java 8
, but for now you need to use Iterator to iterate through the entire collection. Of course, you can imitate the path followed by Guava and Apache by becoming familiar with the new Predicate interface. Now we can use the following code to filter the collection:
6. How to easily convert List to Set? There are two ways to do this, depending on how you want to define equality. The first piece of code puts the list into a HashSet. The duplicate in this case is determined mainly by hashCode(). Typically this will work. But if you need to take into account the comparison path, then it would be better to use the second part of the code, where you can define your own comparator.
7. How can I remove duplicate elements from an ArrayList? This question is somewhat related to the question above. If the order of the elements in the ArrayList does not matter to you, a smart move would be to place the sheet in a Set to remove duplicates, and then return it back to the List. Below is an example. If the order of the elements matters to you, then the order can be ensured by placing the list in
a LinkedHashSet , which is in the standard JDK.
8. Sorted collection
int[] array = {1,2,3,4,5}; List
list = new ArrayList
(); for(int i: array) { list.add(i); }
Iterator
itr = list.iterator(); while(itr.hasNext()) { int i = itr.next(); if (i > 5) { // filter all ints bigger than 5 itr.remove(); } }
public interface Predicate
{ boolean test(T o); } public static
void filter(Collection
collection, Predicate
predicate) { if ((collection != null) && (predicate != null)) { Iterator
itr = collection.iterator(); while(itr.hasNext()) { T obj = itr.next(); if (!predicate.test(obj)) { itr.remove(); } } } }
filter(list, new Predicate
() { public boolean test(Integer i) { return i <= 5; } });
Set
set = new HashSet
(list);
Set
set = new TreeSet
(aComparator); set.addAll(list);
ArrayList** list = ... // initial a list with duplicate elements Set
set = new HashSet
(list); list.clear(); list.addAll(set);
There are several ways to support a sorted collection in Java. All of them provide a collection in natural order or by a specified comparator. In the case of natural order, you also need to implement the
Comparable interface on the element.
- Collections.sort() can sort a List. As stated in the Java documentation, this sort is stable and guarantees n log(n) performance.
- PriorityQueue provides an orderly queue. The difference between PriorityQueue and Collections.sort() is that PriorityQueue maintains the order of the queue all the time, but you can only get the first element of the queue. You can't randomly access an element like PriorityQueue.get(4).
- If there are no duplicates in the collection, you can select TreeSet . Also like PriorityQueue, TreeSet maintains an ordered set at all times. You can get the smallest or largest element from a TreeSet, but you still cannot have random access to the elements.
Simply put, Collections.sort() provides a one-time ordered list. PriorityQueue and TreeSet maintain an ordered collection at all times, at the cost of lack of indexed access to elements.
9. Collections.emptyList() or new instance The same question applies to emptyMap() and emptySet(). Both methods return an empty list, but Collections.emptyList() is an immutable list. This means that you
cannot add new elements to an "empty" list. In the background, each call to the Collections.emptyList() method does not actually create a new instance of the empty list. Instead, it will reuse the already existing empty instance. If you are familiar with Singleton as a
design pattern, you should understand what is meant. This should give you
better performance if called frequently.
10 Copying a collection, Collections.copy() There are two ways to copy a source list to a destination list. One way is to use the ArrayList constructor. Another way is to use the
Collections.copy() method . Notice on the first line: we're allocating a list that is at least the same length as the original list's length, because the Java documentation about collections says:
ArrayList
dstList = new ArrayList
(srcList);
The destination list must be at least as long as the source list.
Which means the final list must be no shorter than the original one. Both methods are shallow copying. So what's the difference between these two methods? First, Collections.copy() will not reallocate the capacity of the dstList collection, even if the dstList does not have enough space to contain all the elements from the srcList. Instead, it will throw
IndexOutOfBoundsException . One might ask if there is any benefit to this. The reason is that this ensures that the method runs linearly in time. This is also suitable when you want to reuse arrays rather than re-allocate memory in the ArrayList constructor.
Instead of a conclusion If after reading the article you still have questions, feel free to ask them in the comments. Also, if you find any inaccuracy in the translation or any other error, then write to the PM, it will be corrected, and you will be thanked.
Original.
ArrayList
dstList = new ArrayList
(srcList.size()); Collections.copy(dstList, srcList);
GO TO FULL VERSION