This is the 25th day of my participation in the August Challenge

I recently learned the source code of Java 8 ArrayList, and found that many designs are of great learning value. In particular, ArrayList has become one of the most frequently asked and basic interview questions in the interview process. Through the source code of ArrayList, I can sum up the hot functions and ideas in the source code, which has a high learning value.

1. Data structure of ArrayList

The data structure inside an ArrayList is the simplest Object array. Because of the nature of arrays, they are more suitable for use in the scenario of many queries and few additions and deletions. To be clear, ArrayList is not thread-safe. So in multithreaded environments, it’s best to use Vector (which, to be honest, few people use anymore), or CopyOnWriteArrayList in JUC packages.

2. Several important parameters of ArrayList

  • DEAFULT_CAPACITY: Default DEAFULT_CAPACITY, 10
  • ModCount: Keeps track of the number of changes to the collection, which increases by 1 each time it is added or removed

3. Capacity expansion mechanism of ArrayList

When an element is added and the original array is already full, the expansion mechanism is triggered. Expansion will increase the length of the original array by 1.5 times, the code uses bit operations for processing.

4. ModCount role

ArrayList is designed to be asynchronous, so when we use a for loop to delete operation will be an error (ArrayIndexOutOfBoundsException). ModCount is used to count the number of operations in the for loop. If you use remove(int index) remove(Object O) remove(int fromIndex,int toIndex) add of ArrayList, modCount will be changed. The need to keep single-threaded operations unique during iteration, and if inserts or deletions occur during iteration, they will be checked by the iterator, resulting in runtime exceptions

5. Advantages, disadvantages and usage scenarios of ArrayList and LinkedList

ArrayList

  • Advantages: Good performance of random access set elements
  • Disadvantages: expensive to add, delete and element

LinkedList:

  • Advantages: Add and delete operations cost little
  • Disadvantages: Poor performance of random access to collection elements

Usage Scenarios:

  • ArrayList: A program makes random accesses to element data many times.
  • LinkedList: The application adds and deletes element data multiple times.