The JAVA ArrayList details the of example
- 2020-04-01 02:30:28
- OfStack
Part 1 introduces the ArrayList
An ArrayList is an array queue that ACTS as a dynamic array. Compared to arrays in Java, its capacity can grow dynamically. It is subclassed from AbstractList and implements interfaces such as List, RandomAccess, Cloneable, java.io.Serializable.
ArrayList implements a List by subclassing AbstractList. It is an array queue that provides the functions of adding, deleting, modifying, traversing and so on.
ArrayList implements the RandmoAccess interface, which provides random access. RandmoAccess is implemented by List in Java to provide quick access to List. In the ArrayList, we can quickly obtain the element object by the sequence number of the element. This is fast random access. Later, we'll compare the efficiency of "quick random access" to List versus "access through an Iterator Iterator."
ArrayList implements the Cloneable interface, overrides the clone() function, and can be cloned.
ArrayList implements the java.io.Serializable interface, which means that ArrayList supports serialization and can be transmitted by serialization.
Unlike vectors, the operations in ArrayList are not thread-safe. Therefore, it is recommended to use ArrayList in a single thread, while in multiple threads you can choose a Vector or CopyOnWriteArrayList.
The inheritance relationship of ArrayList
< img SRC = "border = 0 / / files.jb51.net/file_images/article/201311/20131105100536.jpg? 201310510622 ">
The relationship between ArrayList and Collection is as follows:
< img SRC = "border = 0 / / files.jb51.net/file_images/article/201311/20131105100548.jpg? 201310510715 ">
ArrayList constructor
//Default constructor
ArrayList()
//Capacity is the default capacity for ArrayList. When the capacity is insufficient due to increased data, the capacity is increased by half of the previous capacity.
ArrayList(int capacity)
//Create an ArrayList that contains the collection
ArrayList(Collection<? extends E> collection)
The ArrayList API
//The API defined in the Collection
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
//API defined in AbstractCollection
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
//New API for ArrayList
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
Part 2 ArrayList source code analysis
To better understand the principles of ArrayList, the following analysis of the ArrayList source code. ArrayList is implemented through an array, the source code is easier to understand.
package java.util;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//Sequence version number
private static final long serialVersionUID = 8683452581122892189L;
//An array that holds the data in an ArrayList
private transient Object[] elementData;
//The amount of actual data in an ArrayList
private int size;
//ArrayList with the size of the capacity constructor.
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//Create a new array
this.elementData = new Object[initialCapacity];
}
//ArrayList constructor. The default capacity is 10.
public ArrayList() {
this(10);
}
//Create an ArrayList that contains the collection
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
//Set the current capacity value to = the actual number of elements
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
//Determine the capacity of the ArrarList.
//If the capacity of ArrayList is insufficient to hold all the current elements, set the new capacity = "(original capacity x3)/2 + 1"
public void ensureCapacity(int minCapacity) {
//Will "modify statistics" +1
modCount++;
int oldCapacity = elementData.length;
//If the current capacity is insufficient to accommodate the current number of elements, set the new capacity = "(original capacity x3)/2 + 1"
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
//Add element e
public boolean add(E e) {
//Determine the size of the ArrayList
ensureCapacity(size + 1); // Increments modCount!!
//Add e to the ArrayList
elementData[size++] = e;
return true;
}
//Returns the actual size of the ArrayList
public int size() {
return size;
}
//Returns whether the ArrayList contains Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//Returns whether the ArrayList is empty
public boolean isEmpty() {
return size == 0;
}
//Forward lookup returns the index value of the element
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//Reverse the lookup, returning the index value of the element
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//The reverse lookup (starting at the end of the array) returns the index value of the element (o)
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//Returns an array of objects for the ArrayList
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//Returns an array of templates for the ArrayList. Called a template array, that is, you can set T to any data type
public <T> T[] toArray(T[] a) {
//If the size of array a <The number of elements of ArrayList;
//Then create a new T[] array with the size of "the number of elements in the ArrayList" and copy all the "ArrayList" into the new array
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//If the size of array a> = the number of elements of ArrayList;
//Copy all the elements of the ArrayList into array a.
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
//Gets the value of the element at the index position
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
//Set the value of the index position to element
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
//Add e to the ArrayList
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//Adds e to the specified location of the ArrayList
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//Deletes the element at the specified location in the ArrayList
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) 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;
}
//Deletes the specified element of the ArrayList
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//Quickly remove the index element
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
//Starting at "index+1", replace the previous element with the next one.
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//Set the last element to null
elementData[--size] = null; // Let gc do its work
}
//Remove elements
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//To facilitate the ArrayList, find "element o", delete it, and return true.
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//Empty the ArrayList and set all the elements to null
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//Append the collection c to the ArrayList
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//Starting at the index position, add the collection c to the ArrayList
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//Delete all elements between fromIndex and toIndex.
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
//Cloning function
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
//Copy all the elements of the current ArrayList into v
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
//Write to java.io.Serializable
//Writes the "capacity, all element values" of the ArrayList to the output stream
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
//Say "array capacity"
s.writeInt(elementData.length);
//Say "every element of the array"
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//Java.io.Serializable read function: read according to write mode
//Read the "capacity" of the ArrayList first, then the "all element values"
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
//Reading the "capacity" of the ArrayList from the input stream
int arrayLength = s.readInt();
Object[] a = elementData = new Object[arrayLength];
//Read "all element values" from the input stream
for (int i=0; i<size; i++)
a[i] = s.readObject();
}
}
Conclusion:
(01) ArrayList actually stores data through an array. When we construct an ArrayList; If the default constructor is used, the default capacity of the ArrayList is 10.
(02) when the ArrayList capacity is insufficient to hold all the elements, the ArrayList resets the capacity: the new capacity = "(original capacity x3)/2 + 1".
(03) the clone function of ArrayList clones all the elements into an array.
(04) ArrayList implements java.io.Serializable. When writing to the output stream, write capacity first and then each element in turn. When reading the input stream, read capacity first and then each element in turn.
Part 3 the ArrayList traversal method
ArrayList supports three traversals
(01) the first is traversed by iterator. That is, iterating through an Iterator.
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
(02) the second, random access, through the index value to traverse.
Since ArrayList implements the RandomAccess interface, it supports RandomAccess to elements through index values.
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}
(03) third, for loop traversal. As follows:
Integer value = null;
for (Integer integ:list) {
value = integ;
}
Below through an instance, compare the three kinds of efficiency, example code (ArrayListRandomAccessTest. Java) is as follows:
import java.util.*;
import java.util.concurrent.*;
public class ArrayListRandomAccessTest {
public static void main(String[] args) {
List list = new ArrayList();
for (int i=0; i<100000; i++)
list.add(i);
//isRandomAccessSupported(list);
iteratorThroughRandomAccess(list) ;
iteratorThroughIterator(list) ;
iteratorThroughFor2(list) ;
}
private static void isRandomAccessSupported(List list) {
if (list instanceof RandomAccess) {
System.out.println("RandomAccess implemented!");
} else {
System.out.println("RandomAccess not implemented!");
}
}
public static void iteratorThroughRandomAccess(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (int i=0; i<list.size(); i++) {
list.get(i);
}
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughRandomAccess : " + interval+" ms");
}
public static void iteratorThroughIterator(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
iter.next();
}
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughIterator : " + interval+" ms");
}
public static void iteratorThroughFor2(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for(Object obj:list)
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughFor2 : " + interval+" ms");
}
}
Operation results:
IteratorThroughRandomAccess: 3 ms
IteratorThroughIterator: 8 ms
IteratorThroughFor2:5 ms
Thus, random access (that is, access by index number) is the most efficient way to traverse an ArrayList, and iterators are the least efficient!
Part 4: the toArray() exception
When we call the ArrayList toArray (), which may be met throw "Java. Lang. ClassCastException" abnormal situation. Here's how.
ArrayList provides two toArray() functions:
Object [] toArray ()
< T> T [] toArray (T [] contents)
Invoke toArray () function will be thrown "Java. Lang. ClassCastException" exception, but calling toArray (T [] contents) can return to normal T [].
ToArray () throws an exception because toArray () returns the Object [] array, the Object [] converted to other types (such as, the Object [] is converted to an Integer []) will throw "Java. Lang. ClassCastException" exception, because Java does not support downward transition. You can refer to the previous arraylist.java source code introduction section of toArray().
The solution to this problem is to call < T> T[] toArray(T[] contents) instead of Object[] toArray().
The call toArray(T[] contents) returns T[] in the following ways.
//ToArray (T[] contents) calls mode one
public static Integer[] vectorToArray1(ArrayList<Integer> v) {
Integer[] newText = new Integer[v.size()];
v.toArray(newText);
return newText;
}
//ToArray (T[] contents) calls mode two. The most commonly used!
public static Integer[] vectorToArray2(ArrayList<Integer> v) {
Integer[] newText = (Integer[])v.toArray(new Integer[0]);
return newText;
}
//ToArray (T[] contents) calls mode three
public static Integer[] vectorToArray3(ArrayList<Integer> v) {
Integer[] newText = new Integer[v.size()];
Integer[] newStrings = (Integer[])v.toArray(newText);
return newStrings;
}
Part 5 is the ArrayList example
This article introduces the common apis for ArrayList through an example (arraylisttest.java).
import java.util.*;
public class ArrayListTest {
public static void main(String[] args) {
//Create the ArrayList
ArrayList list = new ArrayList();
//Will ""
list.add("1");
list.add("2");
list.add("3");
list.add("4");
//Add the following element to the first location
list.add(0, "5");
//Gets the first element
System.out.println("the first element is: "+ list.get(0));
//Delete "3"
list.remove("3");
//Gets the size of the ArrayList
System.out.println("Arraylist size=: "+ list.size());
//Determine whether the list contains "3"
System.out.println("ArrayList contains 3 is: "+ list.contains(3));
//Set the second element to 10
list.set(1, "10");
//The ArrayList is iterated through the Iterator
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
System.out.println("next is: "+ iter.next());
}
//Converts the ArrayList to an array
String[] arr = (String[])list.toArray(new String[0]);
for (String str:arr)
System.out.println("str: "+ str);
//Empty the ArrayList
list.clear();
//Determines whether the ArrayList is empty
System.out.println("ArrayList is empty: "+ list.isEmpty());
}
}