ArrayList
The underlying implementation is an array, which has high efficiency in accessing elements (fast query, slow insertion, modification, and deletion of elements)
Compared to LinkedList, it is efficient, but thread-safe.
ArrayList array is a mutable array that can access all elements including null
The underlying implementation is done using arrays
transient Object[] elementData;
Construction method
private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size; // Construct an empty list public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ; } // Construct an empty list of specified initial capacity public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } // Construct a list of specified Collection elements, which are arranged in the order of iterative return of the Connection elements public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }storage
// The element at the specified position of the list is replaced by element, and the original element at that position is returned public E set(int index, E element) { rangeCheck(index); // Check the array capacity and throw: IndexOutOfBoundsException E oldValue = elementData(index); elementData[index] = element; return oldValue; } // Add the specified element at the end of the list public boolean add(E e) { ensureCapacityInternal(size + 1); // Array expansion elementData[size++] = e; return true; } // Add the element at the specified position of the list public boolean add(E e) { ensureCapacityInternal(size++] = e; return true; } // Add the element at the specified position of the list public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // src: Source array, srcPro: Start position in the source array// dest: Destination array, destPost: Start position of the target array, length: Number of array elements to be copied// Move the elements currently at this position and all subsequent elements back one position System.arraycopy(elementData, index, elementData, index + 1, size - index); // Replace element at index position elementData[index] = element; size++; } // Add the elements in the Connection at the end of the list, and the elements are in the order returned by the Connection iterator public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); // Convert to an array int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount // Increments modCount!! System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } // Add elements in the Connection at the specified position in the list, and the elements are in the order returned by the Connection iterator public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(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; }Read
// Remove the element at the specified position of this list public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } // Remove an element in this list 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; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }Array expansion
Whenever an element is added to an array, it is necessary to check whether the number of elements exceeds the length of the current array after adding elements. If it exceeds the length, the array will be expanded to meet the needs of adding data.
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }Handwritten ArrayList
public class MyArrayList /*implements List<E>*/{ private transient Object[] elementData; private int size; //Number of elements public MyArrayList(){ this(10); } public MyArrayList(int initialCapacity) { if (initialCapacity<0) { try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } elementData = new Object[initialCapacity]; } public int size() { return size; } public boolean isEmpty(){ return size == 0; } //Delete the object according to index public void remove(int index) throws Exception { rangeCheck(index); int numMoved = size-index-1; if (numMoved > 0) { System.arraycopy(elementData, index+1, elementData, index, numMoved); } elementData[--size] = null; } //Delete the object public boolean remove(Object obj) throws Exception { for (int i = 0; i < size; i++) { if (get(i).equals(obj)) { remove(i); } return true; } return true; } //Modify the element public Object set(int index , Object obj ) throws Exception{ rangeCheck(index); Object oldValue = elementData[index]; elementData[index] = obj; return oldValue; } //Insert the element at the specified position public void add(int index,Object obj) throws Exception { rangeCheck(index); ensureCapacity(); System.arraycopy(elementData, index, elementData, index+1, size-index); elementData[index] = obj; size ++; } public void add(Object object) { ensureCapacity(); /*elementData[size] = object; size ++;*/ elementData[size++] = object; //Assign value first, then increase yourself} public Object get(int index) throws Exception { rangeCheck(index); return elementData[index]; } public void rangeCheck(int index) throws Exception { if (index<0 || index >=size) { throw new Exception(); } } //Expand public void ensureCapacity() { //Array expansion and content copy if (size==elementData.length) { //elementData = new Object[size*2+1]; Write this way the content in the original array is lost Object[] newArray = new Object[size*2+1]; //Copy the content in the array/*for (int i = 0; i < newArray.length; i++) { newArray[i] = elementData[i]; }*/ System.arraycopy(elementData, 0, newArray, 0, elementData.length); elementData = newArray; } } // Test public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(3); myArrayList.add("111"); myArrayList.add("222"); myArrayList.add("333"); myArrayList.add("444"); myArrayList.add("555"); try { myArrayList.remove(2); myArrayList.add(3, "New Value"); myArrayList.set(1, "Modify"); } catch (Exception e1) { // TODO Auto-generated catch block e1.printStackTrace(); } System.out.println(myArrayList.size()); for (int i = 0; i < myArrayList.size(); i++) { try { System.out.println(myArrayList.get(i)); } catch (Exception e) { e.printStackTrace(); } } }}