ArrayList

This class inherits the AbstractList class. AbstractList is a subclass of the List interface. AbstractList is an abstract class, adapter design pattern.

Using array structure storage, increase, delete slow, find fast

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

1. Construction method

• Arraylist() - > the default initial capacity is 10 to 11. The original length of 10 will be discarded. A new length of 15 (1.5 times the capacity expansion) will be created. If a large amount of data is needed, the following parametric construction method will be used as much as possible to avoid space waste. The type used in construction needs to use class, and basic data type cannot be used

ArrayList<Integer> data = new ArrayList<>();

The source code is as follows: DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}, so the actual length when constructing a new array is 0, but why the initial capacity in the document is 10 is related to the capacity expansion algorithm

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

• ArrayList (int initialCapacity) constructs an empty list with the specified initial capacity
• ArrayList (collection <? Extensions E > C) constructs a list containing the specified collection elements

2. Method

Add element

• public boolean add (E) appends the specified element to the end of this list.
• public void add (int index, E element) inserts the specified element into the specified position in this list. Moves the element of the current location (if any) and any subsequent elements to the right (adds them to the index).
• public boolean addAll (int index, collection <? Extensions E > C) inserts all elements in the specified collection into this list from the specified location. Moves the current element (if any) and any subsequent elements to the right (increases their index).
• public boolean addAll​(Collection<? extends E> c)

add (E) source code analysis:

public boolean add(E e) {
    modCount++;
    //Add (insert element, array data, length of valid data)
    add(e, elementData, size);
    //true will be returned regardless of success or failure!!!
    return true;
}

private void add(E e, Object[] elementData, int s) {
    //If the existing amount of data reaches the maximum length of the array, call the grow() capacity expansion algorithm
    if (s == elementData.length)
        elementData = grow();
    //If there is still space, it is added directly to the end, and the effective data length is added by 1
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    //Add at least 1 length
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    //Arrays.copyof() copies the new length array to the original array
    return elementData = Arrays.copyOf(elementData,
                                        newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //Oldcapacity > > 1, the binary number is shifted to the right by one bit and reduced by half, that is, the capacity is expanded by 1.5 times. Note: the array expansion of empty array and 1 element is invalid
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    //After capacity expansion, the space is still less than the minimum required space, that is, it is not enough
    if (newCapacity - minCapacity <= 0) {

        //If the original array is empty (i.e. stored for the first time), defaultcopy_ EMPTY_ Elementdata = {}, return DEFAULT_CAPACITY=10 and the maximum required space
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);

        //When the minimum length exceeds the maximum value of int, the overflow becomes negative and a memory overflow exception is thrown
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();

        //If it is neither the first time to add data nor overflow, that is, when adding a group of data, if the capacity expansion of 1.5 times cannot be met, the minimum required length will be returned
        return minCapacity;
    }

    //The new length after capacity expansion is sufficient, and if it is less than MAX_ARRAY_SIZE=int, max. - 8, return the new length, otherwise jump to hugeCapacity(minCapacity)
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    //First, there is no overflow
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //If the required length is greater than int, the maximum value is - 8
    return (minCapacity > MAX_ARRAY_SIZE)
    //Returns the maximum value of int
        ? Integer.MAX_VALUE
    //Otherwise, the maximum value of int - 8 is returned
        : MAX_ARRAY_SIZE;
}

use:

ArrayList<Integer> data = new ArrayList<>();
data.add(100);
data.add(99);
data.add(98);
System.out.println(data.toString());
//[100, 99, 98]

data.add(2,44);
System.out.println(data.toString());
//[100, 99, 44, 98]

ArrayList<Integer> data1 = new ArrayList<>();
data1.add(23);
data1.add(43);
data1.add(56);
data.addAll(2, data1);
System.out.println(data.toString());
//[100, 99, 23, 43, 56, 44, 98]

Delete element

• public E remove (int index) deletes the element at the specified position in this list and returns it. Shift any subsequent elements to the left (subtract one element from the index).
• public boolean remove (Object o) removes the first match (if any) of the specified element from the list. If the list does not contain this element, it will not change.

System.out.println(names.remove(2));
//Wang Wu
System.out.println(names);
//[Zhang San, Li Si]
System.out.println(names.remove("Zhao Liu"));
//false
System.out.println(names.remove("Li Si"));
//true
System.out.println(names);
//[Zhang San]

• public boolean removeIf (predict <? Super E > filter) deletes all elements in this collection that meet the given filter conditions.

ArrayList<String> names = new ArrayList<>(3);
names.add("Zhang San");
names.add("Li Si");
names.add("Wang Wu");
System.out.println("Names:"+names);
//Names: [Zhang San, Li Si, Wang Wu]
names.removeIf(s -> s.contains("Lee"));
System.out.println(names);
//[Zhang San, Wang Wu]

ArrayList<Integer> data = new ArrayList<>();
data.add(100);
data.add(99);
data.add(98);
data.add(97);
data.add(96);
data.add(95);
System.out.println(data);
//[100, 99, 98, 97, 96, 95]

//If it is an even number, it will be deleted
data.removeIf(integer -> (integer % 2) == 0);
System.out.println("Odd numbers:" + data);
//Odd numbers:[99, 97, 95]

• public boolean removeAll (collection <? > C) removes all elements contained in the specified collection from this list.

//data = [100, 99, 98, 97, 96, 95]

//Deletes an element from the specified array
data.removeAll(data);
System.out.println(data);
//[]

• Protected void remorerange (int fromIndex, int toIndex) removes all elements with indexes between fromIndex (inclusive) and toIndex (exclusive) from this list. Moves any subsequent element to the left (lowers its index). This call shortens the list through the (toIndex - fromIndex) element. (this operation is invalid if toIndex==fromIndex.)
  • The removelange () method is protected, so if you want to use the ArrayList class that needs to be inherited, we can use Demo3 class to create a dynamic array after inheritance
  • So use ArrayList subList(int fromIndex, int toIndex). Clear () is more convenient

public class Demo3 extends  ArrayList<Integer>{
    public static void main(String[] args) {
        Demo3 data = new Demo3();
        data.add(100);
        data.add(99);
        data.add(98);
        data.add(97);
        data.add(96);
        data.add(95);
        System.out.println(data);
        //[100, 99, 98, 97, 96, 95]
        data.removeRange(1, 3);
        System.out.println(data);
        //[100, 97, 96, 95]
    }
}

• public boolean retainAll (collection <? > C) only keeps the elements contained in the specified collection in this list. In other words, remove all elements from the list that are not included in the specified collection.

//data = [100, 99, 98, 97, 96, 95]

//Only elements with index [2,4) are retained
data.retainAll(data.subList(2,4));
System.out.println(data);
//[98, 97]

• public void clear()

//Connect
data.clear();
System.out.println(data.toString());
//[]

public Object clone()

• Function: clone() method is used to copy a dynamic array, which belongs to shallow copy.

Shallow copy only copies the pointer to an object, not the object itself. The old and new objects still share the same block of memory. Therefore, if one object changes this address, it will affect the other object.

Shallow copy corresponds to deep copy. Deep copy is to copy an object completely from memory, open up a new area from heap memory to store the new object, and modifying the new object will not affect the original object.

data1 = (ArrayList<Integer>)data.clone();
System.out.println(data.clone());
//[100, 99, 23, 43, 56, 44, 98]
System.out.println(data1.toString());
//[100, 99, 23, 43, 56, 44, 98]

Here, the return value of clone() is Object, so ArrayList () is required to convert the type to an integer dynamic array

Reference source http://www.w3school.me/java/java-arraylist-clone.html

public boolean contains​(Object o)

• Function: returns true if the list contains the specified element.

Integer i = 100;
System.out.println(data.contains(i));
//true

public void ensureCapacity​(int minCapacity)

• Function: increase the capacity of this ArrayList instance to ensure that it can accommodate at least the number of elements specified by the minimum capacity parameter. Although ArrayList will expand dynamically, manually determining the array length can reduce the time spent in automatic expansion

ArrayList<String> names = new ArrayList<>();
names.ensureCapacity(3);
names.add("Zhang San");
names.add("Li Si");
names.add("Wang Wu");
System.out.println("Names:"+names);
//Names: [Zhang San, Li Si, Wang Wu]

public void forEach​(Consumer<? super E> action)

• Function: perform the given operation on each element of Iterable until an exception is thrown by processing all elements or operations of Iterable. If this order is specified, the operations are performed in iterative order. There is no return value, and the contents of the original array remain unchanged

//Pass the lamda expression to forEach
names.forEach((e)->{
    e = e + "It's a fool";
    System.out.println(e);
});
// Zhang San is a fool
// Li Si is a fool
// Wang Wu is a fool

public E get​(int index)

• Function: returns the element at the specified position in this list

System.out.println(names.get(2));
//Wang Wu

public int indexOf​(Object o)

• Function: returns the index of the specified element that appears for the first time in this list. If this list does not contain this element, - 1 is returned.

System.out.println(names.indexOf("Wang Wu"));
//2
System.out.println(names.indexOf("Zhao Liu"));
//-1

• Similar to public int lastIndexOf (Object o)

public boolean isEmpty()

• Function: judge whether the array is empty

ArrayList<String> names1 = new ArrayList<>();
System.out.println(names1.isEmpty());
//true

public Iterator<E> iterator()

• Return iterator

Iterator<String> iterator = names.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

public E set​(int index, E element)

• Replaces the element at the specified location in this list with the specified element.

//data = [100, 99, 98, 97, 96, 95]

data.set(2,250);
System.out.println(data);
//[100, 99, 250, 97, 96, 95]

public int size()

• Returns the number of valid elements in this list.

System.out.println(data.size());

public List<E> subList​(int fromIndex, int toIndex)

• Returns the view of this part of the list between the specified fromIndex (inclusive) and toIndex (exclusive). (if fromIndex and toIndex are equal, the returned list is empty.) The returned list is supported by this list, so non structural changes in the returned list will be reflected in this list and vice versa. The returned list supports all optional list operations

//data = [100, 99, 98, 97, 96, 95]
List<Integer> data1 = data.subList(2, data.size());
System.out.println(data1);
//[98, 97, 96, 95]

public Object[] toArray()

• Returns an array containing all the elements in this list in the appropriate order (from the first element to the last element).

//data = [100, 99, 98, 97, 96, 95]
Object[] it = data.toArray();
System.out.println(Arrays.toString(it));
//[100, 99, 98, 97, 96, 95]

public <T> T[] toArray​(T[] a)

• Return an array containing all the elements in this list (from the first element to the last element) in the appropriate order; The runtime type of the returned array is the runtime type of the specified array.

Integer[] it = new Integer[(data.size())];
data.toArray(it);
System.out.println(Arrays.toString(it));
//[100, 99, 98, 97, 96, 95]

public void trimToSize()

• Adjust the capacity of this ArrayList instance to the current size of the list. Applications can use this operation to minimize the storage of ArrayList instances.