Open source - Java 2 source Interpretation: java.util.ArrayListsource

Java 2 source Interpretation: java.util.ArrayList

Related source download:
Java.util.ArrayList
Java.util.AbstractList
Java.util.List

ArrayList List interface is a variable length arrays to achieve. List all the interface to achieve the operation, and allows storage null value. In addition to no synchronization, ArrayList basic equivalent to Vector. Vector in almost all of the methods have been conducted simultaneously, but only writeObject ArrayList readObject and a synchronization, such as add other (Object), remove (int) are not synchronized.

1. Storage

ArrayList use an Object array storage elements.
Private transient Object elementData [];
ArrayList realized java.io.Serializable interface, the transient marker here do not automatically attribute this sequence of. Below will writeObject () method explained in detail why do so.

2.add and remove

Public boolean add (Object o) (
EnsureCapacity (size + 1) / / Increments modCount!
ElementData [size + +] = o;
Return true;
)

Note here ensureCapacity () method, and its role is to ensure that elementData the length of the array can accommodate a new element. In the "automatic variable length mechanism" will be explained in detail.
Public Object remove (int index) (
RangeCheck (index);
ModCount + +;
Object oldValue = elementData [index];
Int numMoved = size - index - 1;
If (numMoved> 0)
System.arraycopy (elementData, index +1, elementData, index,
NumMoved);
ElementData [- size] = null; / / Let gc do its work
Return oldValue;
)

RangeCheck () to the role of border checkpoints. As ArrayList object array with a storage element, an element in the need to remove the element behind the advancement. Delete only one element of the array elements in elementData quoted in the home as null, the destruction of specific targets by the garbage collector is responsible for.
ModCount role will be in the following "iterator () synchronization," stated.
Note: The use of the advancement of the System to provide a practical method: arraycopy (), in this case we can see that System.arraycopy () method can be carried out with an array of operation, this method is a native method, if operate with an array, the first from the source to a temporary copy of the array, the array elements of the temporary copy to the target location.

3. Automatic variable length mechanism

In the case of an ArrayList, you can specify an initial capacity. This capacity is elementData the initial length of the array. If you use:
ArrayList list = new ArrayList ();

Using the default capacity: 10.
Public ArrayList () (
This (10);
)

ArrayList offers four add () method,

Public boolean add (Object o)
Public void add (int index, Object element)
Public boolean addAll (Collection c)
Public boolean addAll (int index, Collection c)

In each of the add () method, a first call ensureCapacity (int miniCapacity) method, this method guarantees elementData not less than the length of the array miniCapacity. ArrayList automatic variable length mechanism is in the method to achieve.
Public void ensureCapacity (int minCapacity) (
ModCount + +;
Int oldCapacity = elementData.length;
If (minCapacity> oldCapacity) (
Object oldData [] = elementData;
Int newCapacity = (oldCapacity * 3) / 2 + 1;
If (newCapacity <minCapacity)
NewCapacity = minCapacity;
ElementData = new Object [newCapacity newCapacity];
System.arraycopy (oldData, 0, elementData, 0, size);
)
)

In this method can be seen in the ArrayList each expansion, expanded to the original size of 1.5 times.
Each add () method is the realization of similar Below is add (Object) method to achieve:
Public boolean add (Object o) (
EnsureCapacity (size + 1) / / Increments modCount!
ElementData [size + +] = o;
Return true;
)

4.iterator () Synchronization

AbstractList father in the category in the definition of an int type attributes: modCount record ArrayList structural change in the number.
Protected transient int modCount = 0;

ArrayList all involved in the structural changes in the method of modCount increased value, including: add (), remove (), addAll (), removeRange () and clear () method. Call each one of these methods, the value of the Canadian modCount 1.
Note: add () and addAll () method is the value of the modCount call in which the ensureCapacity () method increased.

AbstractList the iterator () method (ArrayList directly inherited this method) using the internal members of a private Itr, generate a Itr object (Iterator interface) return:
Public Iterator iterator () (
Return new Itr ();
)

Itr realized Iterator () interface, which also defines an int type attributes: expectedModCount, this attribute in the type initialization Itr was given ArrayList object modCount the value of the attribute.
Int expectedModCount = modCount;

Note: members of the internal Itr is also a member of ArrayList class, it can access all the properties and methods AbstractList. Understand this point, the realization of Itr categories can be easily understood.

In Itr.hasNext () method:
Public boolean hasNext () (
Return cursor! = Size ();
)

Calling the AbstractList the size () method, compared the current cursor position is cross-border.

In Itr.next () method, also called Itr defined in the AbstractList get (int) method, the current cursor to return to the elements:
Public Object next () (
Try (
Object next = get (cursor);
CheckForComodification ();
LastRet = cursor + +;
Return next;
) Catch (IndexOutOfBoundsException e) (
CheckForComodification ();
Throw new NoSuchElementException ();
)
)

Note that in the next () method calls the checkForComodification () method, the synchronization of the revised inspection:
Final void checkForComodification () (
If (modCount! = ExpectedModCount)
Throw new ConcurrentModificationException ();
)

ModCount expectedModCount now and the role should be very clear. In a collection object or operation of generation at the same time, do not set targets to limit the operation of the elements, some of these operations, including possible errors or substituting the add () or remove (), and dangerous operation. AbstractList in, the use of a simple mechanism to circumvent these risks. This is modCount expectedModCount and the role of the host.

5. Sequence of support

ArrayList realized java.io.Serializable interface, it can ArrayList object to the sequence of persistent storage medium. ArrayList the main attributes are defined as follows:

Private static final long serialVersionUID = 8683452581122892189L;
Private transient Object elementData [];
Private int size;

SerialVersionUID size can be seen and will automatically sequence of the medium, but elementData is defined as an array of objects of the transient. In other words ArrayList of all these elements will not be automatic serialization of the media. Why should we achieve this? ElementData array storage because the "elements" In fact, only one of these elements used is not really the target sequence of the application of an object is meaningless, because of the sequence-to-sequence, when you - Sequence of, the application of these objects have been impossible at the original object. So here the need for manual ArrayList elements of the operation sequence. This is writeObject () role.
Private synchronized void writeObject (java.io.ObjectOutputStream s)
Throws java.io.IOException (
/ / Write out element count, and any hidden stuff
S.defaultWriteObject ();
/ / Write out array length
S.writeInt (elementData.length);
/ / Write out all elements in the proper order.
For (int i = 0; i <size; i + +)
S.writeObject (elementData [i]);
)

ElementData such elements in the array element object can be so correct sequence of the storage medium to.
Corresponding readObject () in accordance with writeObject () method in the order read from the input stream:
Private synchronized void readObject (java.io.ObjectInputStream s)
Throws java.io.IOException, ClassNotFoundException (
/ / Read in size, and any hidden stuff
S.defaultReadObject ();
/ / Read in array length and allocate array
Int arrayLength = s.readInt ();
ElementData = new Object [arrayLength];
/ / Read in all elements in the proper order.
For (int i = 0; i <size; i + +)
ElementData s.readObject [i] = ();
)