preface
We know ArrayList is a dynamic array with an array-based and scalable base, so how does it work? Now go into the source code to understand.
This article is based on JDK 1.8 and will follow the standard List interface approach.
Before we do that, let’s take a look at some of the main ArrayList member variables:
// Initialize the array capacity by default
private static final int DEFAULT_CAPACITY = 10;
// Empty arrays to save memory, used in different constructors
private static final Object[] EMPTY_ELEMENTDATA = {};
// Empty array to save memory, used in different constructors, distinguished from above
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// The array itself that actually loads the data
transient Object[] elementData;
// The number of elements held by the current ArrayList (non-elementData)
private int size;
Copy the codeThose who are confused about EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be explained later, and the common methods will be dissected.
1. add(E) & add(int, E)
public boolean add(E e) {
// Expansion logic
ensureCapacityInternal(size + 1);
// Appends the element to the end of the array and increments size by one
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// Check whether the index is valid, 0<=index<=size for add, 0<=index<=size for other operations
rangeCheckForAdd(index);
// Expansion logic
ensureCapacityInternal(size + 1);
// To make space for the index, move the index and the following elements back one space
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// Add the element to the array
elementData[index] = element;
/ / the size plus one
size++;
}
Copy the codeThere are two types of add logic: add to the end of the array and insert to the middle (or head) of the array based on the incoming index. As you can see, ensureCapacityInternal() is a method that uses size + 1, which means at least size + 1 is needed for the current add operation. Go inside and take a look at the expansion logic.
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Copy the codeInside ensureCapacityInternal() you can see that ensureExplicitCapacity() and calculateCapacity() are called again, so let’s look at calculateCapacity(), In calculateCapacity() we see the empty array mentioned in the introduction, If elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA select the largest of DEFAULT_CAPACITY(10) and minCapacity, otherwise minCapacity is returned.
DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used for the first time in a constructor with no arguments. All constructors are listed here and explained one by one, as follows:
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if((size = a.length) ! =0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else{ elementData = Arrays.copyOf(a, size, Object[].class); }}else {
// replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the code- ArrayList() : Direct elementData to DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- ArrayList(int initialCapacity) : Pass in the specified capacity. If the specified capacity is greater than 0, create an array with the corresponding capacity. If the specified capacity is equal to 0, point elementData to EMPTY_ELEMENTDATA.
- ArrayList(Collection
c) : Implements an array if the passed collection is not 0, otherwise makes elementData point to EMPTY_ELEMENTDATA.
So the question is, why do I need two empty arrays? Can’t you just use one? I’ll leave it here for the time being, but it’ll all be clear when the expansion logic comes back.
Back to ensureCapacityInternal(), now that we’ve analyzed calculateCapacity(), we’re on to ensureExplicitCapacity(), where you can see that minCapacity is checked, Make sure it is larger than the array before you can go to grow() (the real expansion operation).
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the codeGrow () : the new capacity is equal to the old capacity +(old capacity /2), which is 1.5 times the original capacity. MinCapacity is used if the calculated new capacity is less than minCapacity. If the current array capacity is too small, the calculated new capacity will be too small, such as 0 or 1.
Two empty array problems:
MinCapacity is either size + 1 or DEFAULT_CAPACITY. DEFAULT_CAPACITY is used in only one case. If the capacity is smaller than DEFAULT_CAPACITY, the capacity is directly raised to DEFAULT_CAPACITY to avoid multiple capacity expansion in a short period of time.
When we create an ArrayList with our own specified capacity, that means we are doing it consciously, and we don’t want to go straight to DEFAULT_CAPACITY if the capacity is small.
If you only use an empty array, you will not be able to distinguish between the different processing of the expansion logic. You can either go to the normal 1.5 times capacity expansion or increase the small capacity to DEFAULT_CAPACITY first.
Ps: addAll is actually similar, so I don’t want to join it.
2. remove(int) & remove(Object)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
Copy the codeIf the element is not the end of the array, all the elements in the index need to be moved forward one bit. FastRemove () ¶ fastRemove() ¶ fastRemove() ¶ fastRemove() ¶ fastRemove() ¶
3. get(int)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the code4. indexOf(Object)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codeSimilar to removing, it handles both cases, then iterates through the set of comparison objects to see if they are equal and returns the index, -1 if not found.
5. clear()
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the codeTraversal sets the element to null and size to 0.
6. trimToSize()
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the codeIn addition to scaling up and, of course, scaling down, ArrayList provides scaling up, but not dynamically, as an option. Calling this method shortens the array to size.
The other ones are pretty simple, so I won’t analyze them.
At the end
As you can see, ArrayList is pretty conventional except for adding a lot of logic. After all, the core of ArrayList is dynamic expansion, and dynamic expansion happens during the process of adding elements.
ArrayList can also be optimized. Since it is time-consuming to move array elements during adding and deleting, it can be transformed into a circular dynamic array, adding a first pointer to represent the first element, and writing a simple version of Kotlin as follows:
class RingArrayList<E> : AbstractList<E> {
companion object {
private const val DEF_CAPACITY = 8
}
private varitems: Array<E? >private var first = 0
private var _size = 0
override val size: Int
get() = _size
constructor() : this(DEF_CAPACITY)
constructor(capacity: Int) {
val safeCapacity = when {
capacity <= 0 -> DEF_CAPACITY
else -> capacity
}
items = arrayOfNulls<Any>(safeCapacity) as Array<E?>
}
override fun add(index: Int, item: E): Boolean {
checkIndexForAdd(index)
ensureCapacity(size + 1)
val items = items
val size = size
if (index < size shr 1) {
// index is less than size/2, the element moves forward, and the first pointer is reset
for (i in 0 until index) {
items[mapIndex(i - 1)] = items[mapIndex(i)]
}
first = mapIndex(-1)}else {
// index is greater than or equal to size/2
for (i in (size - 1) downTo index) {
items[mapIndex(i + 1)] = items[mapIndex(i)]
}
}
items[mapIndex(index)] = item
_size++
return true
}
private fun ensureCapacity(capacity: Int) {
val items = items
if (capacity <= items.size) {
return
}
val newCapacity = max(capacity, capacity + (capacity shr 1))
migrate(newCapacity)
}
override fun remove(item: E): Boolean {
val index = indexOf(item)
if (index < 0) {
return false
}
removeAt(index)
return true
}
override fun removeAt(index: Int): E {
checkIndex(index)
val items = items
val oldVal = items[mapIndex(index)]
if (index >= size shr 1) {
// index is greater than or equal to size/2, and the element moves forward
for (i in index until size - 1) {
items[mapIndex(i)] = items[mapIndex(i + 1)]
}
items[mapIndex(size - 1)] = null
} else {
// index is less than size/2, the element is moved back, and the first pointer is reset
for (i in index downTo 1) {
items[mapIndex(i)] = items[mapIndex(i - 1)]
}
items[first] = null
first = mapIndex(1)
}
_size--
if (_size == 0) {
first = 0
}
return oldVal as E
}
override fun set(index: Int, item: E): E {
checkIndex(index)
val mapped = mapIndex(index)
val oldVal = items[mapped]
items[mapped] = item
return oldVal as E
}
override fun get(index: Int): E {
checkIndex(index)
return items[mapIndex(index)] as E
}
private fun checkIndexForAdd(index: Int) {
if (index < 0 || index > size) {
throw IndexOutOfBoundsException(errorMsg(index))
}
}
private fun checkIndex(index: Int) {
if (index < 0 || index >= size) {
throw IndexOutOfBoundsException(errorMsg(index))
}
}
private fun errorMsg(index: Int): String {
return "Index: $index, Size: $size"
}
override fun indexOf(item: E): Int {
for (i in 0 until _size) {
if (items[mapIndex(i)] == item) {
return i
}
}
return -1
}
override fun clear(a) {
for (i in 0 until _size) {
items[mapIndex(i)] = null
}
_size = 0
}
private fun mapIndex(index: Int): Int {
var mapped = first + index
val arraySize = items.size
if (mapped < 0) {
mapped += arraySize
} else {
mapped = if (mapped < arraySize) mapped else mapped - arraySize
}
return mapped
}
fun trimToSize(a) {
migrate(size)
}
private fun migrate(capacity: Int) {
if(first ! =0) {
val newArray = arrayOfNulls<Any>(capacity)
for (i in 0 until _size) {
newArray[i] = items[mapIndex(i)]
}
this.items = newArray asArray<E? > first =0
} else {
this.items = items.copyOf(capacity)
}
}
override fun toString(a): String {
return items.contentToString()
}
}
Copy the code