This is my first article on getting started

Writing in the front

Data structures are often asked in interviews, but are generally used in development without paying attention to how to implement them.

In data structure, a linked list is a linear storage structure, which is often called a linear table.

Concept: A linear table is a data storage structure in a data structure with a “one to one” logical relationship between data elements. It can be understood that all the data is strung together with a line and stored in the physical space.

The order table ArrayList

Concept: Data is sequentially stored in a contiguous block of physical space. This storage structure is called a sequential storage structure (order table for short). Similar to the picture below, they are connected by a line to form a linear structure.

ArrayList is one such example.

ArrayList is based on the array implementation, array is one of the simplest data structure, when using it must be created to the size, in daily development, often we do not know how much space to allocate to the array, if the array space allocation is too much, memory waste, allocation is small, can not be loaded. ArrayList can be used to add more than one element without specifying the size, because ArrayList is dynamically expanded.

Class

Source code analysis

Attributes of a class

/** * Default initial capacity */
private static final int DEFAULT_CAPACITY = 10;

/** *ArrayList specifies an array of actual data stores. The capacity of the ArrayList is the length of the array buffer. * When the first element is added, any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY. * /
transient Object[] elementData;

/** * Shared empty array instance for default size empty instance */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * Size of elementData */
private int size;
Copy the code

Class constructor

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

What does new ArrayList() do

public class TestClient {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        Integer capacity = getCapacity(list);
        System.out.println("Size without adding elements:" + capacity);
        System.out.println("Size without adding elements:" + list.size());
        list.add("Add elements");
        capacity = getCapacity(list);
        System.out.println("Size when adding 1 element:" + capacity);
        System.out.println("Size when adding 1 element:" + list.size());
    }

    /** * Get the capacity of the list by reflection **@param list
     * @return* /
    public static Integer getCapacity(List<String> list) {
        Integer length = null;
        Class c = list.getClass();
        Field f;
        try {
            f = c.getDeclaredField("elementData");
            f.setAccessible(true);
            Object[] o = (Object[]) f.get(list);
            length = o.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
        returnlength; }}Copy the code

Print the result

Capacity without adding elements:0Size with no element added:0add1The capacity of each element:10add1Size of elements:1
Copy the code

Therefore, when new ArrayList() is added, it defaults to an empty array of objects, with an initial capacity of 0 when no element is added, and a capacity of 10 only when the first element is added.

Basic method

Add (E E)

/** * appends the specified element to the end of the list */
 public boolean add(E e) {
     ensureCapacityInternal(size + 1);
     // Direct assignment
     elementData[size++] = e;
     return true;
}
Copy the code

add(int index, E element)

Adds an element at the specified index location

String[] elementData = {"1"."2"."3"."4"."5"."6"."Seven"."8"};
int index = 4;
/ / since the location of the subscript 4 copy, copy the length of the 8-4 = 4 (copy "5", "6", "7", "eight"), the subscript for 4 + 1 = 5 place began to replace with "5", "6", "7", "eight"
System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
Copy the code

ArrayList Expansion mechanism

ensureExplicitCapacity(int minCapacity)

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // If the number of elements is greater than its capacity, expand it
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
Copy the code

grow(int minCapacity)

    /** * Expansion *@param minCapacity
     */
    private void grow(int minCapacity) {
        // The original capacity
        int oldCapacity = elementData.length;
        // The new capacity is shifted to the right one bit by the bit operation. For example, the default value is 10. 10>>1=5
        OldCapacity >> 1 == oldCapacity/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // If it is greater than the maximum capacity allowed by ArrayList, set it to the maximum capacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
Copy the code

If you want to learn about bit operations, check out this article

Bit operations in Java

The internal implementation of ArrayList uses an array of objects to store specific values, and then uses a mechanism of expansion to dynamically grow the array.

The capacity expansion mechanism can be understood as: If the number of elements is greater than the capacity, the capacity is expanded to 1.5 times the original capacity.

extends

  • How is the size of an ArrayList automatically increased?
  • When would you use an ArrayList?
  • How to add or delete an object in an index ArrayList? Is it inefficient? Explain why?
  • How to delete nodes in the ArrayList sequence?
  • ArrayList traversal method?
  • The difference between ArrayList and LinkedList