What is the default capacity of
ArrayList and what is the growth algorithm of array list?
Ø
Default
capacity of array list is 10.
/**
* Constructs an empty list with an
initial capacity of ten.
*/
public ArrayList()
{
this(10);
}
However we can also specify initial capacity of an array list.
/**
* Constructs an empty list with the
specified initial capacity.
* @param initialCapacity the initial capacity of the list
* @exception IllegalArgumentException
if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new
IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new
Object[initialCapacity];
}
Where ‘elementData’ is an object array to
which size is initialized.
/**
* The array buffer into which the elements
of the ArrayList are stored.
* The capacity of the ArrayList is the
length of this array buffer.
*/
private
transient Object[] elementData;
Growth algorithm of
ArrayList is:
int newCapacity = (oldCapacity * 3)/2
+ 1;
e.g.:
LET oldCapacity =10
THEN (10*3)/2+1 = 16
SO
newCapacity is 16.
Working of ArrayList:
public class
WorkingOfArrayList {
public static void main(String[]
args) {
ArrayList<String>
aList= new ArrayList<String>();
aList.add("a");
aList.add("b");
aList.add("c");
aList.add("d");
aList.add("e");
aList.add("f");
aList.add("g");
aList.add("h");
aList.add("i");
aList.add("j");
aList.add("k");
//when 11th
element is going to be added in list the capacity of list is resized.
//Growth algo
is: (OLDCAPACITY*3)/2+1 i.e., if oldCapacity is 10 then new capacity is
16.
System.out.println("ArrayList:
"+aList);
System.out.println("Get value
at 1st: "+aList.get(1));
aList.set(4,"abhinav");
System.out.println("ArrayList:
"+aList);
System.out.println("Get value
at 4th: "+aList.get(4));
}
}
Output>
Flow:
Element
‘a’ is added in list using add() method which implementation is given in such a
way that it always ensures the capacity of list and then add the element into
it, if capacity is full then it will automatically add all the elements in the
current array to a new array of
increased size. This is done by using System.arrayCopy(..)
method.
Implementation of add() method:
private int size; // initial size of an array.
private int size; // initial size of an array.
private
int modCount;
private
transient Object[] elementData;// object
array buffer
public boolean add(E e) {
ensureCapacity(size
+ 1); // Increments modCount(how many
times list is structurally modified.)!!
elementData[size++]
= e;
//object array of some size in which
elements are added.
return true;
}
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at
least the number of elements
* specified by the minimum capacity
argument.
*
* @param minCapacity
the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;//
flag to maintain the log of list’s structure modification.
int oldCapacity =
elementData.length;
//This
below block is used when list size met the total capacity of list.
if (minCapacity
> oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2
+ 1;
if (newCapacity < minCapacity)
newCapacity
= minCapacity;
// minCapacity is usually close to size,
so this is a win:
elementData =
Arrays.copyOf(elementData, newCapacity);
//Internally System.arrayCopy() is used to copy all elements from old array to
new size array after growth of list is performed.
}
}
From above example elements (a - j) in the list are added normally
till the size is reached to 10, because default initialization of list gives
size as 10.
When ‘k’ is going to be added in the list it is computed that its size
is full.
(minCapacity > oldCapacity ) i.e., (11> 10), then list is
resized.
Ø
A new
array of capacity 16 is created.
Ø
All
the elements in the old array are copied into the new array using
System.arrayCopy(..).
Ø
New
array of size 16 is calculated by growth algo (oldCapactity(10)*3)/2+1=16;
Implementation of get (int
index) method:
/**
* Returns the element at the specified
position in this list.
*
* @param index index of
the element to return
* @return the element at
the specified position in this list
* @throws IndexOutOfBoundsException
{@inheritDoc}
*/
public E get(int index) {
RangeCheck(index);
//check whether entered range is valid or not
return (E) elementData[index];
}
/**
* Checks if the given index is in
range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately
prior to an array access,
* which throws an
ArrayIndexOutOfBoundsException if index is negative.
*/
private void RangeCheck(int index) {
if (index >= size)
throw new
IndexOutOfBoundsException(
"Index:
"+index+", Size:
"+size);
}
Implementation of set (int
index, Element e) method:
/**
* Replaces the element at the specified
position in this list with
* the specified element.
*
* @param index index of
the element to replace
* @param element
element to be stored at the specified position
* @return the element
previously at the specified position
* @throws IndexOutOfBoundsException
{@inheritDoc}
*/
public E set(int index, E
element) {
RangeCheck(index);//check
whether entered range is valid or not
E
oldValue = (E) elementData[index];
elementData[index] =
element;
return oldValue;
}
No comments:
Post a Comment
Thanks for your comments/Suggestions.