Why is ArrayList dynamic?

Anyone who has learned ArrayList systematically should have basic knowledge that ArrayList is a List based on dynamic array. You don’t have to worry about errors like ‘ArrayOutOfBoundary’, because the length, or size, is not static,unless you give it a boundary,or capacity when you initialize an ArrayList. How do Java achieve this function? Talk is cheap, read the code.


Before that, I believe it’s fairly essential to distinguish the differences between Capacity and size.
Capacity in numbers return the length of the Array, putting the null elements into consideration;
Size returns how many non-null elements the array contains.
For example:

int[] a = new int[10];
for(int i=0;i<5;i++){
    a[i]=i;
}
/*
The size of a is 5,while the capacity is 10,which never changes once you new it.
*/

Reading Comprehension Time!

//The default_capacity of ArrayList
private static final int DEFAULT_CAPACITY = 10;

//Empty Array Elements
transient Object[] elementData;

//default initial capacity
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private int size;

//When using the default constructor
public ArrayList() {
    this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//size=10 if you just new the ArrayList using default constructor; 
public boolean add(E e) {
    ensureCapacityInternal(size +1);// modCount incremented
    elementData[size++] = e;
    return true;
}

/*initialize the ArrayList size to 10;
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

/*Why spend so much on pursing minimum capacity at the cost of
 *making the code so complicated?
 *To save the precious memory, I guess.
 */


//When the programmer use the constructor with parameters that limits the size;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity)
            /*if the size is smaller than 10, it's no big deal if you create a 10 one,
            *since you can trim it;
            *but this is not the case when it's the opposite.
            */
             }
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//modCount is to record how many times the capacity has changed;
        if (minCapacity - elementData.length > 0)
            /*if the size of Array at present is larger than the capacity of Array;
             *it works well even when minCapacity is set negative
             */
            grow(minCapacity);//literally, grow:)
    }


// There's a upper limit of the size of ArrayList
//Why MAX_VALUE-8? Because an array need a 8 bytes(size of an int)of memory 
//to store the size of itself
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


private void grow(int minCapacity) {
    int oldCapacity = elementData.length;//oldCapacity is size
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //The new capacity is the 1.5 times larger than the old one
    if (newCapacity - minCapacity < 0)
        //make sure capacity is the smallest
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //Of course, if the array is too big...
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
    //create an object array(a new one!) with all value from
    //elementData and a capacity of newCapacity 

    }

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        // Capacity can't be a negative number,anyway
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        //if capacity is too big
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Both remove(int index) and remove(Object o) calls fastRemove(int index):

 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
    }

As you can see, capacity of array does not change when elements are removed. This is because if you clear the unused memory immediately, then you need to take extra time to allocate them when you eventually decide to use them, which is low-efficient.

Conclusion:

Concrete and detailed analysis is in annotation of the code above.

Three core private methods of ArrayList, ensureCapacityInternal(), ensureExplicitCapacity(), and grow() (all parameters ignored) explain why it is dynamic. Capacity in the very beginning is 0 after newed by defualt constructor until add() is called. When the programmer calls either add(int index, Object o) or add(Object o), and it happens that the size of the list is larger than the present capacity, ensureCapacityInternal() will be called. It first decides how much memory to allocate , then JVM calls ensureExplicitCapacity(), and finally grow() method is called. Method grow() directly expands the capacity by 1.5 times and in the end System.copyOf() copy everything of the array with small capacity to the new 1.5 larger one, and returns the new array to programmers. Since these core methods are private and encapsulated, ArrayList shows up in a dynamic appearance.

Magic Methods in Python

This first post of programming is about Python’s Magic Method


Magic Method is not marked as an essential point in the book Python Crash Course, which actually is. To distinguish it from other ordinary methods, magic methods start with two underscores.

Magic Methods are mainly used in a class. The magic methods I use frequently(and recently) are those below:

def __init__(self): It is just like the Constructor in Java,the use of which is to initialize the attribute of the class.

Keep in mind that there is no this keyword in Python.Instead of this, Python use self keyword.You cannot claim an attribute outside like Java do. Claim it in the method.

Here’s an example:

class Car():
    def __init__(self,brand):
        self.brand=str(brand)

Here’s the Java’s way of doing this:

class Car{
    private String brand;
    public Car(String brand){
        this.brand=brand;
    }
}

 

def __str__(self):The method is just like the toString() method in Java,enabling you to print the object in your customized way.You should override it when you need it.

Still taking the class car as example:

class Car():
    def __init__(self,brand):
        self.brand=str(brand)
    def __str__(self):
        return "The brand of the car is %s."%self.brand

And it’s rather obvious when you run the file and make the parameter brand to Toyota,you get the result The brand of the car is Toyota.

 

Don’t miss this one:__dict__

The method is not put in the class. This function returns a dictionary of a certain entity (or instance in Java terms).

class Car():
    def __init__(self,brand,price):
        self.brand=str(brand)
        self.price=int(price)
    def __str__(self):
        return "This %s car costs about $%d "%(self.name,self.price)
    
myCar=Car("Toyota",3000)
print(myCar.__dict__)

The result will be:

{'brand':'Toyota','price':3000}

This is a super useful method.