当前位置：网站首页>If you want to learn ArrayList well, it is enough to read this article

From the perspective of data structure ,List It's a linear table , It can be saved n A finite sequence of elements of the same type , In this sequence , You can add, delete, query and modify variables

List For an interface , There are many ways , Not introduced here , You can view List Official documents of
List Official documents of

About List Use ：

List It's a Interface cannot instantiate object , So there must be a class to implement it , and ArrayList And that's what happened List Interface

ArrayList Introduction to

The picture above clearly shows ArrayList Inherited classes and implemented interfaces , You can understand... In combination with the underlying code

🪔 explain ：

️ArrayList Realized RandomAccess Interface , indicate ArrayList Support random access
️ArrayList Realized Cloneable Interface , indicate ArrayList Sure clone
️ArrayList Realized Serializable Interface , indicate ArrayList Sure Support serialization
️ArrayList The ground floor is a continuous space , Sure Dynamic capacity , Is a dynamically typed sequential table

Here's a problem ：ArrayList And Vector The difference between ？（ The interview questions may be ）

Vector And ArrayList The same has been achieved List Interface , The ground floor is also a continuous space , Is a dynamic class order table , The only difference is Vector yes Thread safety Of , Can be used in multithreading , and ArrayList yes Thread unsafe Of , It can only be used safely under single thread

Vector It's thread safe , It is because the bottom layer uses synchronized Lock , That's why thread safety is guaranteed

Vector The underlying method implementation ：

ArrayList Use

ArrayList Construction method of

Construction method	explain
ArrayList()	No arguments structure
ArrayList(int initalCapacity)	The parameter indicates the initial capacity of the sequence table
ArrayList(Collection<? extends E> c)	Use other Collection Set building ArrayList

Code presentation of the use of construction methods ：

import java.util.ArrayList;
import java.util.List;

public class ArrayListTest {
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();  // No arguments structure 

        List<String> list2 = new ArrayList<>(20); // Use the initial capacity value to construct 

        list1.add(1);
        list1.add(2);
        list1.add(3);

        List<Integer> list3 = new ArrayList<>(list1);  // Use an existing set to construct 
    }
}

*ArrayList The common method of

ArrayList There are a lot of ways , Only common methods are shown here

Method	explain
boolean add(E e)	Tail insertion e
void add(int index , E e)	take e Insert index Location
boolean addAll(Collection<? extends T> c)	Tailoring set c The elements in
E remove(int index)	Delete index Elements in position
boolean remove(Object o)	Delete the first encountered element o
E get(int index)	Or take index Location elements
E set(int index , E e)	take index The location element is set to e
void clear()	Empty
boolean contains(Object o)	Judge o Are you in this collection
int indexOf(Object o)	Return to the first o The subscript
int lastIndexOf(Object o)	Go back to the last o The subscript
List<E> subList(int fromIndex , int toIndex)	Interception part list

ArrayList Insert operation of

Tail insertion ：

import java.util.ArrayList;
import java.util.List;

public class ArrayListTest {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        for(int i : list){
            System.out.print(i+" ");
        }
    }
}

Print ：1 ,2 ,3 Print it out in turn

Insert the element into the specified position ： take 9 Insert into subscript 1 The location of

        list.add(1,9);

Print ： In sequence 1,9,2,3

Tail all the elements of a collection ：

        List<Integer> list1 = new ArrayList<>(); // Create a new linear table list1
        list1.add(6); 
        list1.add(8);
        list.addAll(list1);  // take list1 Tail insert to list in

Print the results ：1,9,2,3,6,8

ArrayList Delete operation of

Delete the specified location element ： Mark the subscript as 0 Delete the elements of

        list.remove(0);

Print ： Before we found out 0 Subscript elements 1 Been deleted

Delete the first element encountered ： Because the method parameter is Object type , So the parameter must be passed into the packing type

        Integer a = 3;
        list.remove(a);

Print ： Find elements 3 Been deleted

️ Gets the specified subscript element

        list.remove(a);
        int b = list.get(2);
        System.out.println(b);

Print ： obtain 2 Subscript the corresponding element 6

🪄 Set the specified subscript element to the new value

take 2 The value corresponding to the subscript is set to 7：

        list.set(2,7);

Print the results ： It is found that the original subscript is 2 The elements of 3 Set to 7

🪀 Determine whether an element is in a linear table

Judge 2 Whether it is in the linear table ：

        boolean flag1 = list.contains(2);

Print ：

Judge 5 Whether it is in the linear table ：

        boolean flag2 = list.contains(5);

Print ：

Returns the subscript of the first and last occurrence of a specified element

such as ArrayList The element sequence in is ：9,2,7,8,2

Print elements 2 First occurrence of subscript ：

       System.out.println(list.indexOf(2));

Print ：

Print elements 2 Last occurrence of subscript ：

      System.out.println(list.lastIndexOf(2));

Print ：

ArrayList Empty operation of

        list.clear();
        System.out.println(list.size());

Print ： All elements are cleared , The number of valid elements is 0

️ArrayList The traversal operation of

for Loop traversal

public class ArrayListTest2 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add(" Xiao Wang ");
        list.add(" Xiao Zhang ");
        list.add((" floret "));
        for(int i = 0;i < list.size();i++){
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
    }
}

Print the results ：

foreach Traverse

        for(String s : list){
            System.out.print(s+" ");
        }

Print the results ：

Iterator traversal

        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }

Print the results ：

ArrayList The underlying capacity expansion mechanism

ArrayList It's a Dynamic type sequence table , That is to say When inserting an element, it will be automatically expanded , The following is the capacity expansion mechanism ：

️ summary ：

When using a parameterless constructor to create ArrayList, Capacity defaults 10 The initial capacity is initialized at the first insertion , Instead of initializing capacity at creation time
When inserting , It will check whether the capacity expansion is really needed , if necessary , call grow Capacity expansion
The preliminary estimate is based on... Of the original capacity 1.5 Double expansion
If the user needs more than the estimated size 1.5 times , Then expand the capacity according to the size required by the user
Before the real expansion, check whether the expansion is successful , Prevent too large to cause expansion failure
Use copyOf super-popular

Simulation Implementation ArrayList( The interview may require writing )

Here is the simulation implementation , Therefore, the basic functions can be realized

Construction method

Here are two construction methods , One is parameterless by default , One is with initial capacity parameter , The default capacity is 10, In the parameterless construction method , Call the constructor with parameters , It doesn't have to be as complicated as the standard library

public class MyArrayList<E>{
    private E[] elementData;
    private int size;

    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList(){
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int initCapacity){
        if(initCapacity <= 0){
            initCapacity = DEFAULT_CAPACITY;
        }
        elementData = (E[]) new Object[initCapacity];
    }
}

🤿 Insert method add

To achieve Insert... At the specified location Methods ：

1. Judgment parameters index Is it legal
2. Confirm whether to expand the capacity
3. take index Move back with the elements in the back position
4. Go to index Position insert ,size++

    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new ArrayIndexOutOfBoundsException("add：index Transboundary ");
        }
        ensureCapacity(size);
        for(int i = size-1;i >= index;i--){
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
        size++;
    }

Tail insertion ：

We found that the tail insertion is size The position of the , So you can call the method inserted at the specified position , Improve code reuse

    public boolean add(E e){
        add(size,e);
        return true;
    }

Capacity expansion ：

It is necessary to check whether the capacity is expanded during each insertion , Expand the capacity if necessary

1. Get the old capacity value
2. Judge size Whether it is greater than the capacity value
3. If it is greater than or equal to , Explain the need for expansion
4. use 1.5 Update the capacity value in multiple mode

    public void ensureCapacity(int size){
        int oldCapacity = elementData.length;
        if(size >= oldCapacity){
            int newCapacity = oldCapacity + (oldCapacity>>1);
            elementData = Arrays.copyOf(elementData,newCapacity);
        }
    }

Delete method remove

Delete the specified location element ：

1. Judge index Is it legal
2. take index The elements after move forward by a length
3. size--

    public E remove(int index){
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("remove：index Transboundary ");
        }
        E ret = elementData[index];
        for(int i = index+1;i < size;i++){
            elementData[i-1] = elementData[i];
        }
        size--;
        return ret;
    }

Deletes the specified element ：

1. First determine whether the element exists , Here you can call the following indexOf Method , If returned to -1, There is no , Everything else exists
2. indexOf Will return the element subscript , So you can call the method above to delete the element at the specified location , Improve code reuse

    public boolean remove(E e){
        int index = indexOf(e);
        if(index == -1){
            return false;
        }
        remove(index);
        return true;
    }

🥌 Find element subscript method indexOf,lastIndexOf

Find where the element first appears ：

Traverse from the beginning , Find the return subscript , No return found -1

    public int indexOf(E e){
        for(int i = 0;i < size;i++){
            if(e.equals(elementData[i])){
                return i;
            }
        }
        return -1;
    }

Find the location of the last occurrence of the element ：

    public int lastIndexOf(E e){
        for(int i = size-1;i >= 0;i--){
            if(e.equals(elementData[i])){
                return i;
            }
        }
        return -1;
    }

Traverse from last forward , Find the return subscript , No return found -1

Be careful ： When comparing the above , use equals Methods to compare , Out-of-service == Compare

subList Method

1. Judge whether the parameter is legal
2. Take the length to be intercepted as the parameter , Create a new MyArrayList
3. From the beginning of the interception to the new one list Add the element to the end of the interception

    MyArrayList<E> subList(int from,int to){
        if(from > to){
            throw new IllegalArgumentException("subList： Illegal parameters ,from>to");
        }
        int newSize = to-from;
        MyArrayList<E> list = new MyArrayList<>(newSize);
        while(from < to){
            list.add(elementData[from]);
            from++;
        }
        return list;
    }

Be careful ：subList The intercepted range is [from,to), It's left closed and right open

🪁contains,get,set,size,clear Method

contains Method ：

We can call indexOf Position find the element subscript , if -1 It does not include , Otherwise, it contains

    public boolean contains(E e){
        return -1==indexOf(e);
    }

get Method ：

First judge whether the parameter is legal , If it is legal, it will directly return the location element

    public E get(int index){
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("get：index Transboundary ");
        }
        return elementData[index];
    }

set Method ：

First judge whether the parameter is legal , If it is legal, it should be modified directly

    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("set：index Transboundary ");
        }
        elementData[index] = e;
    }

size Method ：

Go straight back to size that will do

    public int size(){
        return size;
    }

clear Method ：

take size Set as 0, And traverse the elements from the beginning , Set each position to null

    public void clear(){
        size = 0;
        for(int i  =0;i < size;i++){
            elementData[i] = null;
        }
    }

️ Yes MyArrayList To test

    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>(4);
        list.add(1);   // Tail insertion 1
        list.add(2);   // Tail insertion 2
        list.add(3);   // Tail insertion 3
        list.add(3,4);  // In position 3 Insert 4
        System.out.println(list);  
        System.out.println(list.get(2));  // The output subscript is 2 The elements of 
        list.set(0,5); // Place 0 The element of is set to 5
        System.out.println(list);
        System.out.println(list.contains(4)); // Judge whether it includes 4
        System.out.println(list.contains(9)); // Judge whether it includes 9
        list.remove(0); // Delete location 0 The elements of 
        System.out.println(list);
        list.remove((Integer) 4); // Remove elements 4
        System.out.println(list);
        list.add(3);
        System.out.println(list.indexOf(3)); // Output the first 3 The location of 
        System.out.println(list.lastIndexOf(3)); // Output the last 3 The location of 
        MyArrayList<Integer> list2 = list.subList(0,1); // Interception part List
        System.out.println(list2);
        list.clear(); // Empty 
        System.out.println(list.size()); // See if it is empty 
    }

Print the results ： Meet the basic use