ArrayList how does the size increase

Question

I have a basic question on Java ArrayList   When ArrayList is declared and initialized using the default constructor  memory space for 10 elements is created  Now  when I add an 11th element  what happens  Will new memory space be created with 20  or more  element capacity  this requires copying elements from 1st memory location to new location  OR some thing else   I checked here  But I didn t find an answer   Please share the knowledge   Thanks

User · Answer

Context java 8

I give my answer here in the context of Oracle java 8 implementation, since after reading all the answers, I found that an answer in the context of java 6 has given by gmgmiller, and another answer has been given in the context of java 7. But how java 8 implementes the size increasement has not been given.

In java 8, the size increasement behavior is the same as java 6, see the grow method of ArrayList:

   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);
    }

the key code is this line:

int newCapacity = oldCapacity + (oldCapacity >> 1);

So clearly, the growth factor is also 1.5, the same as java 6.

User · Answer

ArrayList does increases the size on load factor on following cases     Initial Capacity  10 Load Factor  1  i e  when the list is full  Growth Rate  current size   current size 2      Context   JDK 7     While adding an element into the ArrayList  the following public ensureCapacityInternal calls and the other private method calls happen internally to increase the size  This is what dynamically increase the size of ArrayList   while viewing the code you can understand the logic by naming conventions  because of this reason I am not adding explicit description  public boolean add E paramE            ensureCapacityInternal this size   1           this elementData  this size       paramE          return true         private void ensureCapacityInternal int paramInt            if  this elementData    EMPTY ELEMENTDATA              paramInt   Math max 10  paramInt           ensureExplicitCapacity paramInt         private void ensureExplicitCapacity int paramInt            this modCount    1          if  paramInt - this elementData length  lt   0              return          grow paramInt          private void grow int paramInt        int i   this elementData length      int j   i    i  gt  gt  1       if  j - paramInt  lt  0          j   paramInt      if  j - 2147483639  gt  0          j   hugeCapacity paramInt       this elementData   Arrays copyOf this elementData  j

User · Answer

The default size of the arraylist is 10  When we add the 11th     arraylist increases the size  n 2   The values stored in old arraylist are copied into the new arraylist whose size is 20

User · Answer

when a ArrayList is declared and initialized using default  constructor  memory space for 10 elements will be created  now  when i add 11 th element  what happens is  ArrayList create a new object with the following size  i e  OldCapacity 3 2 1   10 3 2 1  16

User · Answer

Size of ArrayList increases with n n 2 1 always

User · Answer

Default capacity of ArrayList is 10  Once the Capacity reaches its maximum capacity  Size of the ArrayList will be 16  once the capacity reaches its maximum capacity of 16  size of the ArrayList will be 25 and keep on increasing based on Data size       How  Here is the Answer and Formula  New capacity    Current Capacity   3 2    1   So  if the default capacity is 10  then   Current Capacity   10 New capacity    10   3 2    1 Output is 16

User · Answer

oldSize   3  2   1  If you are using default constructor then initial size of ArrayList will be 10 else you can pass the initial size of array while creating the object of ArrayList   Example  In case default constructor  List lt String gt  list   new ArrayList lt  gt     list size     Example  In case parameterized constructor  List lt String gt  list   new ArrayList lt  gt  5   list size

User · Answer

Typically  the memory for ArrayList type containers is increased by doubling it  Thus  if you initially had space for 10 items and you added 10  the eleventh item will be added to a new  internal  array of 20 items  The reason for this is that the incremental cost of adding items is reduced from O n 2  if the array had been incremented in fixed size increments to a nice O n  when doubling the size each time the internal array is full

User · Answer

When we try to add an object to the arraylist    Java checks to ensure that there is enough capacity in the existing array to hold the new object  If not  a new array of a greater size is created  the old array is copied to new array using Arrays copyOf and the new array is assigned to the existing array    Look at the code below  taken from Java ArrayList Code at GrepCode com           Edit    public ArrayList   Constructs an empty list with an initial capacity of ten   public ArrayList int initialCapacity  we can specify initial capacity   public ArrayList Collection c  Constructs a list containing the elements of the specified collection  in the order they are returned by the collection s iterator   Now when we use ArrayList   constructore we get a ArrayList with Size 10 On adding 11th element in the list new Arraylist is created inside ensureCapacity   method   Using following formula     int newCapacity   oldCapacity   3  2  1

User · Answer

When ArrayList is declared and initialized using the default constructor  memory space for 10 elements is created     NO  When ArrayList is initialized  memory allocation is made for an empty array  Memory allocation for default capacity  10  is made only upon addition of first element to ArrayList           The array buffer into which the elements of the ArrayList are stored     The capacity of the ArrayList is the length of this array buffer  Any    empty ArrayList with elementData    EMPTY ELEMENTDATA will be expanded to    DEFAULT CAPACITY when the first element is added      private transient Object   elementData    P S  Don t have enough reputation to comment on question  so I am putting this as an answer as nobody pointed out this incorrect assumption earlier

User · Answer

Up to JDK 6 the the capacity grow with formula newCapacity    oldCapacity   3 2    1    In JDK 7 and above the formula changes to newCapacity   oldCapacity    oldCapacity  gt  gt  1    So if initial capacity is 10 then new capacity will be 16 in JDK6 and 15 in above JDK7

User · Answer

From JDK source code  I found below code  int oldCapacity   elementData length  int newCapacity   oldCapacity    oldCapacity  gt  gt  1

User · Answer

Arraylist default capacity is 10    1 2 3 4 5     10   if you want to increase the size of Arraylist in java  you can apply this  formula-  int newcapacity  current capacity   newcapacity    current capacity 3 2  1   arralist will be  1 2 3 4 5     10 11  and arraylist capacity is 16

User · Answer

What happens is a new Array is created with n 2 spaces  then all items in the old array are copied over and the new item is inserted in the first free space   All in all  this results in O N  add time for the ArrayList   If you re using Eclipse  install Jad and Jadclipse to decompile the JARs held in the library   I did this to read the original source code

User · Answer

In Jdk 1 6  New capacity    Current Capacity   3 2    1   In Jdk 1 7   int j   i    i    1   this is same as  New capacity    Current Capacity   1 2    Current Capacity   ex size will increase like  10-- 15-- 22-- 33

User · Answer

static int getCapacity ArrayList lt   gt  list  throws Exception               Field dataField   ArrayList class getDeclaredField  elementData                dataField setAccessible true               return   Object    dataField get list   length          use the above method to check the size when the arraylist is being modified

User · Answer

It will depend on the implementation  but from the Sun Java 6 source code   int newCapacity    oldCapacity   3  2   1    That s in the ensureCapacity method  Other JDK implementations may vary

User · Answer

Lets look at this code  jdk1 8    Test     public void testArraySize   throws Exception           List lt String gt  list   new ArrayList lt  gt             list add  ds            list add  cx            list add  cx            list add  ww            list add  ds            list add  cx            list add  cx            list add  ww            list add  ds            list add  cx            list add  last            1 Put break point on the line when  last  is inserted   2 Go to the add method of ArrayList You will see  ensureCapacityInternal size   1       Increments modCount           elementData size      e    3  Go to ensureCapacityInternal method this method call ensureExplicitCapacity  4    private void ensureExplicitCapacity int minCapacity            modCount                overflow-conscious code         if  minCapacity - elementData length  gt  0              grow minCapacity                     return true    In our example minCapacity is equal to 11 11-10  gt  0 therefore  You need grow method  5   private void grow int minCapacity               overflow-conscious code         int oldCapacity   elementData length          int newCapacity   oldCapacity    oldCapacity  gt  gt  1           if  newCapacity - minCapacity  lt  0              newCapacity   minCapacity          if  newCapacity - MAX ARRAY SIZE  gt  0              newCapacity   hugeCapacity minCapacity              minCapacity is usually close to size  so this is a win          elementData   Arrays copyOf elementData  newCapacity           Lets describe each step   1  oldCapacity   10 because we didn t put this param when ArrayList was init  therefore it will use default capacity 10   2  int newCapacity   oldCapacity    oldCapacity  gt  gt  1   Here newCapacity is equal to oldCapacity plus oldCapacity with right shift by one  oldCapacity is 10 this is the binary representation 00001010 moving one bit to right we will get 00000101 which is 5 in decimal therefore newCapacity is 10   5   15   3    if  newCapacity - minCapacity  lt  0                  newCapacity   minCapacity    For example your init capacity is 1  when you add the second element into arrayList newCapacity will be equal to 1 oldCapacity    0  moved to right by one bit    1 In this case newCapacity is less than minCapacity and elementData array object inside arrayList  can t hold new element therefore newCapacity is equal to minCapacity  4    if  newCapacity - MAX ARRAY SIZE  gt  0              newCapacity   hugeCapacity minCapacity     Check if array size reach MAX ARRAY SIZE  which is Integer MAX - 8  Why the maximum array size of ArrayList is Integer MAX VALUE - 8   5  Finally it copy old values to the newArray with length 15

User · Answer

A new array is created and the contents of the old one are copied over  That s all you know at the API level  Quoting from the docs  my emphasis       Each ArrayList instance has a capacity  The capacity is the size of the array used to store the elements in the list  It is always at least as large as the list size  As elements are added to an ArrayList  its capacity grows automatically  The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost    In terms of how it actually happens with a specific implementation of ArrayList  such as Sun s   in their case you can see the gory details in the source  But of course  relying on the details of a specific implementation isn t usually a good idea

User · Answer

ArrayList in Java grows by 50  of its original capacity once it is full

User · Answer

Sun s JDK6   I believe that it grows to 15 elements  Not coding it out  but looking at the grow   code in the jdk   int newCapacity then   10    10    1    15          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 grow int minCapacity           overflow-conscious code     int oldCapacity   elementData length      int newCapacity   oldCapacity    oldCapacity  gt  gt  1       if  newCapacity - minCapacity  lt  0          newCapacity   minCapacity      if  newCapacity - MAX ARRAY SIZE  gt  0          newCapacity   hugeCapacity minCapacity          minCapacity is usually close to size  so this is a win      elementData   Arrays copyOf elementData  newCapacity       From the Javadoc  it says this is from Java 2 and on  so its a safe bet in the Sun JDK    EDIT   for those who didn t get what s the connection between multiplying factor 1 5 and int newCapacity   oldCapacity    oldCapacity  gt  gt  1     gt  gt  is right shift operator which reduces a number to its half  Thus  int newCapacity   oldCapacity    oldCapacity  gt  gt  1      int newCapacity   oldCapacity   0 5 oldCapacity      int newCapacity   1 5 oldCapacity

[java] ArrayList: how does the size increase?

Examples related to java

Examples related to arrays

Examples related to arraylist

Examples related to collections