Data structure ArrayList Java
|
ArrayList arguably would be the most used collection along with the HashMap. Many of us programmers whip up code everyday which contains atleast one of these data structures to hold objects. I have already discussed how HashMap works internally in Java, in this post I'll try to explain how ArrayList internally works in Java. Show As most of us would already be knowing that ArrayList is a Resizable-array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it. So let's try to get clear idea about the following points-
Note - Code of ArrayList used here for reference is from Java 10. Where does ArrayList internally store elementsBasic data structure used by Java ArrayList to store objects is an array of Object class, which is defined as follows- transient Object[] elementData;I am sure many of you would be thinking why transient and how about serializing an ArrayList then? What happens when ArrayList is createdArrayList class in Java provides 3 constructors to create an ArrayList.
How does ArrayList grow dynamicallyWhen we add an element to an ArrayList it first verifies whether it has that much capacity in the array to store new element or not, in case there is not then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that much capacity (Actually uses Arrays.copyOf which returns the original array increased to the new length). Code in the Java ArrayList implementation is like this- public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }Where DEFAULT_CAPACITY is defined as- private static final int DEFAULT_CAPACITY = 10; private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }You can see here it is determined if there is a need to increase the size of the array, if yes then grow method is called. private void grow(int minCapacity) { // overflow-conscious code 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); }Note that till Java 6 the new capacity calculation used to be like this- int newCapacity = (oldCapacity * 3)/2 + 1;Which is changed in Java 7 to use right shift operator. With right shift operator also it will grow
by 50% of old capacity. Output 5If the default capacity was 10 then int newCapacity = oldCapacity + (oldCapacity >> 1);will return 15. What happens when an element is removed from ArrayListWhen elements are removed from an ArrayList in Java using either remove(int i) (i.e using index) or remove(Object o), gap created by the removal of an element has to be filled in the underlying array. That is done by Shifting any subsequent elements to the left (subtracts one from their indices). System.arrayCopy method is used for that. System.arraycopy(elementData, index+1, elementData, index, numMoved);Here index+1 is the source position and index is the destination position. Since element at the position index is removed so elements starting from index+1 are copied to destination starting from index. Points to note
Recommendations for learning (Udemy courses) That's all for this topic How ArrayList Works Internally in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks! Related Topics You may also like- Certain data structures in Java can be created by you (yes you). In this example, we’ll go ahead and create an ArrayList data structure that has some of the methods that the built-in ArrayList class has. We’ll create 2 constructors: We’ll also create a number of methods: I encourage you not to look at the ArrayList built-in class. See if you can figure it out on your own. The only other restriction will be to store the Objects in an array data field. Create a test class to test the ArrayList class. Name your ArrayList class ArrayList.java so that it overwrites the built in class. Read the notes above each method. There is a precondition that states the requirements that you’ll need to abide by before the method is called. For example, if the method requires an array of integers to be passed to it, you will need to have an array of integers ready. After the method is called, there is the post-condition. This explains what the expected output of the method will be and the steps the method takes to achieve that output. We’ll start off with the ArrayList class. The methods that were outlined above will be added to this class. What good is the code if you’re not going to test it. We’ll create a Driver class that’s going to test the ArrayList code. And that’s really all their is too it. With basic Java skills, you too can create your ArrayList data structure. |
