1. What do you understand about ArrayList?

The underlying data structure of an ArrayList is an array, and its apis encapsulate the underlying access to arrays. For example, the process of the add method is… (See the add process in ArrayList source code analysis for details.)

Similarly, the LinkedList is understood in the same way.

2. Capacity expansion related problems

2.1 ArrayList is constructed without an argument constructor. Now add a value to it. What is the size of the array at this time?

A: The size of the array is 1, and the maximum available size before the next expansion is 10, because the first expansion of the ArrayList has a default value of 10, and the first time you add a value, the available size of the array is increased to 10.

2.2 What is the size of the array when the list is incremented to the 11th value?

When the size of the array is increased to 11, we want the size of the array to be 11, but in fact, the maximum size of the array is only 10, so we need to expand the size. The formula for expansion is as follows: OldCapacity + (oldCapacity>> 1), oldCapacity indicates the existing size of the array. The current calculation formula is: 10 + 10/2 = 15. Then we find that 15 is sufficient, so the array size will be expanded to 15.

2.3 Array initialization: After adding a value, what is the size of the array if 15 values are added at once using the addAll method?

In the previous question, we have calculated that the actual size of the array is 1 after adding a value, and the maximum available size is 10. Now we need to add 15 values at once, so we expect the size of the array to be 16. At this time, the maximum available size of the array is 10, which is obviously not enough. 10 + 10/2 = 15, at this time found that the size of the expansion is still less than our expected value of 16, at this time there is a strategy in the source code as follows:

// newCapacity Specifies the size of the array to be expanded
// If the value after the expansion is less than our expected value, our expected value is equal to the size of the expansion
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
Copy the code

So the final array size is 16. See grow method for ArrayList source code analysis for more details.

2.4 Now there is a large array that needs to be copied. The size of the original array is 5K. How can I copy it quickly?

A: Because the original array is large, if you do not specify the size of the array when creating a new array, it will be frequently expanded. Frequent expansion will cause a large number of copies, resulting in poor copy performance. Therefore, when creating a new array, you can specify the size of the new array as 5K.

2.5 Why Does capacity expansion Cost performance?

A: The System. Arraycopy method is used for capacity expansion, which copies all the data in the original array to the new array. Therefore, the performance consumption is serious.

2.6 What can be learned from the source code expansion process?

A: There are two points:

  • Expansion ideas worth learning, through the way of automatic expansion, let the user need not care about the underlying data structure changes, packaged well, 1.5 times the rate of expansion, can let the expansion speed in the slowly rising, in the later growth faster, most of the work required in an array by the values and is not very big, so the early growth is beneficial to save resources, In the later period when the growth rate is fast, it can also be rapidly expanded.
  • During capacity expansion, the size of the array overflow is aware. For example, the size of the expanded array must not be smaller than 0 or larger than the maximum value of an Integer.

3. Delete related questions

For (int I =0; for (int I =0; i<list.size (); I++) to delete the element whose value is 3. What was the result of the final deletion, and why? Delete the code as follows:

List<String> list = new ArrayList<String>() {{
  add("2");
  add("3");
  add("3");
  add("3");
  add("4");
}};
for (int i = 0; i < list.size(); i++) {
  if (list.get(i).equals("3")) { list.remove(i); }}Copy the code

Answer: It cannot be completely deleted. The final result is 2, 3, and 4, and there is a 3 that cannot be deleted. The reason is as follows:As can be seen from the figure, after each deletion of an element, the element behind the element will move forward, while the I of the loop keeps increasing. Finally, the 3 after each deletion of 3 will be omitted, resulting in the deletion of 3.

We can delete the ArrayList array by enhancing the for loop.

Answer: No, an error will be reported. Because the enhanced for loop actually calls the next () method of the iterator, when you call list.remove () to delete, the modCount value is +1, while the value of the expectedModCount in the iterator does not change, Causes expectedModCount! The next time the iterator executes the next () method. = modCount would quote ConcurrentModificationException error.

Iterator.remove () : iterator.remove () : iterator.remove () : iterator.remove () : iterator.remove ()

A: Yes, because the iterator.remove () method assigns the latest modCount to the expectedModCount so that the modCount and the expectedModCount will be equal in the next loop.

3.4 Do the above three questions have the same result for LinkedList?

A: Yes, although the LinkedList underlying structure is a two-way list, the result is the same as ArrayList for the above three problems.

4. Questions to compare with LinkedList

4.1 How is an ArrayList different from a LinkedList?

A: You can start with the underlying data structure and work your way through it, for example:

  • The biggest difference is the underlying data structure. ArrayList is an array, while LinkedList is a two-way LinkedList
  • The difference in data structure between the two also leads to the difference in API implementation of the operation. For example, ArrayList calculates and decides whether to expand, and then assigns the new data directly to the array, while LinkedList only needs to change the pointing position relation of the inserted node and the nodes before and after it.

4.2 What is the difference between ArrayList and LinkedList?

A:

  • Arraylists are better for quick lookup matches than for frequent additions and deletions, such as those in which elements are often queried for matches at work
  • LinkedList is better suited to scenarios where additions and deletions are frequent and queries are rare.

4.3 Do ArrayList and LinkedList have maximum capacity?

A:

  • The ArrayList has the maximum capacity, the maximum value of an Integer, beyond which the JVM will not allocate memory for the array
  • The underlying LinkedList is a two-way LinkedList that could theoretically be infinitely large. The size of the LinkedList is an int, which means that the LinkedList must not exceed the maximum value of an Integer or overflow will occur.

4.4 How do ArrayList and LinkedList handle null values?

A:

  • ArrayList allows null values to be added and deleted. Delete the element whose first value is NULL from the beginning
  • LinkedList additions and deletions are allowed without special validation for null values.

5. Thread safety issues

5.1 Are ArrayList and LinedList thread safe and why?

A:

  • There are no thread-safety issues when they are non-shared variables, such as only local variables in a method, and only thread-safety issues when they are shared variables.
  • The main problem is that in multithreaded environments, arrays and linked lists can be manipulated by all threads at any time, which can lead to overwriting of values and even confusion. Just as the elementData, size, and modConut of The ArrayList itself are not locked, and their types are not volatile, so if multiple threads operate on these variables, they can be overwritten.

If there is a thread safety issues, in the process of iteration, frequently reported ConcurrentModificationException mistakes, means in the process of my current loop, an array or list structure is modified by other threads

5.2 How Can I Solve the Thread Safety Problem?

A: SynchronizedList; Collections#synchronizedList; synchronized lock; synchronized lock; synchronized lock; synchronized lock Arrays and linked lists can only be modified by a thread, but performance is greatly reduced, specific implementation source code:

public boolean add(E e) {
    synchronized (mutex) {Synchronized is a lightweight lock, and mutex represents a current SynchronizedList
        returnc.add(e); }}Copy the code

Alternatively, JUC’s CopyOnWriteArrayList concurrency List can be used to solve this problem.