First look and then like, give yourself a little time to think, after thinking, please do not hesitate to wechat search [Silent King ii], pay attention to this long hair but rely on talent programmer. GitHub github.com/itwanger includes interview questions compiled by tech gurus and a series of essays by my second brother.

Basic Knowledge about Java, Java object-oriented programming, Java string, Java array and other aspects of the knowledge has been able to come to an end, friends can be in the “silent King ii” public account background reply “xiao Bai” to obtain the second edition of the manual. If you feel good about it, please forward it to your friends and give them roses.

So next, I began to liver Java collection of articles, friends, please give me a silent clap, I can hear, really, don’t mean your applause, ring. I have to start with ArrayList, because ArrayList is probably the most commonly used class for collections.

ArrayList implements the List interface and is implemented based on arrays. If the array is full, you can’t add any more elements to it. An ArrayList is a good alternative to arrays. It provides a richer set of predefined methods (add, delete, change, and check) than arrays, and is flexible enough to automatically adjust its size based on the number of elements.

Prepare to add an element 55 to the fourth location (subscript 3) of the ArrayList.

The element after the fifth position in the ArrayList will be moved backwards.

I’m going to remove 23 from the ArrayList.

The elements with subscripts 7, 8, and 9 move forward.

01, How to create an ArrayList

ArrayList<String> alist = new ArrayList<String>();
Copy the code

An ArrayList can be created as a string using the above statement (Angle brackets are used to qualify the types of elements in the ArrayList, and attempts to add elements of other types will result in a compilation error). A more simplified version of this statement is as follows:

List<String> alist = new ArrayList<>();
Copy the code

Since ArrayList implements the List interface, the alist variable can be of type List; The type of the element can no longer be specified in the Angle brackets after the new keyword declaration, because the compiler can infer intelligently from the type in the preceding Angle brackets.

You can also specify the initial size when creating an ArrayList if you are very sure of the number of elements in the list.

List<String> alist = new ArrayList<>(20);
Copy the code

This has the advantage of effectively avoiding unnecessary expansion when adding new elements. But in general, it’s hard to determine the number of elements in an ArrayList, so you don’t specify the initial size.

02. Add an element to the ArrayList

You can add an element to the ArrayList using the add() method, which defaults to the end if no subscript is specified.

alist.add("Silent King II.");
Copy the code

The add() method executes the grow() method when adding elements. This is one of the key points interviewers like to examine.

Add (E, E)

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
Copy the code

Call the private add(E E, Object[] elementData, int s) method:

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
Copy the code

The crucial grow(int minCapacity) method is then called:

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0|| elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = newObject[Math.max(DEFAULT_CAPACITY, minCapacity)]; }}Copy the code

If no initial size is specified when creating an ArrayList, the initial size of the ArrayList is DEFAULT_CAPACITY:

private static final int DEFAULT_CAPACITY = 10;
Copy the code

It can hold up to 10 elements.

You can also add an element to the specified position by using the add(int index, E element) method:

alist.add(0."Silent King three.");
Copy the code

Add (int index, E element)

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
            elementData, index + 1,
            s - index);
    elementData[index] = element;
    size = s + 1;
}
Copy the code

This method calls a very important local method, system.arrayCopy (), which copies the array (see the two images at the beginning of this article).

Update elements in ArrayList

You can use the set() method to change elements in an ArrayList, providing subscripts and new elements.

alist.set(0."The Silent King iv.");
Copy the code

The original element at position 0 was “Silent King iii”, now it is updated to “Silent King IV”.

Set () = set();

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
Copy the code

The method checks the specified subscript to see if it is out of bounds, then replaces the new value and returns the old value.

Delete elements from ArrayList

The remove(int index) method is used to remove the element at the specified subscript position, and the remove(Object O) method is used to remove the element at the specified value.

alist.remove(1);
alist.remove("The Silent King iv.");
Copy the code

Remove (int index); remove(int index);

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}
Copy the code

This method returns the element to be deleted, and the actual deletion is done in the fastRemove(es, index) method.

Remove (Object O) remove(Object O)

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}
Copy the code

This method finds the subscript of the element to be deleted by breaking the label (null using the == operator and non-null using equals(), which means deleting the first element if it has the same element), and then calls fastRemove().

Now that the fastRemove() method is called, let’s keep track of the source code:

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}
Copy the code

If the last element is deleted, you do not need to copy the array, but simply assign the last element to NULL. Otherwise, you call System.arrayCopy () to copy the array. Refer to the third and fourth pictures mentioned at the beginning of the article.

Find elements in an ArrayList

To find an element in positive order, use the indexOf() method; If you want to find an element in reverse order, you can use the lastIndexOf() method.

alist.indexOf("Silent King II.");
alist.lastIndexOf("Silent King II.");
Copy the code

IndexOf () = indexOf();

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                returni; }}}else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                returni; }}}return -1;
}
Copy the code

Use the “==” operator if the element is null, otherwise use the equals() method — which is not null-safe.

The lastIndexOf() method is similar to indexOf() but iterates from the end.

The contains() method determines whether an ArrayList contains an element that calls indexOf() inside:

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
Copy the code

If the elements in an ArrayList are sorted, binary lookup can be used more efficiently.

The Sort () method of the Collections class sorts an ArrayList, which sorts a list of strings alphabetically. If the list is of a custom type, you can also specify the Comparator for sorting.

List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

Collections.sort(copy);
System.out.println(copy);
Copy the code

The following output is displayed:

[a, b, c, d]
Copy the code

After sorting, we can use binary search:

int index = Collections.binarySearch(copy, "b");
Copy the code

6, the last

So much for ArrayList. From the perspective of source code, I think you must be more impressed by ArrayList.

A quick summary of ArrayList’s time complexity will serve as a comparison when we study LinkedList later.

1) The time complexity of accessing an element via the subscript (i.e. Get (int index)) is O(1), because it is direct, no matter how many times the data is increased, the time is the same.

2) The time complexity of adding an element (i.e., add()) is O(1) because it is added directly to the end.

3) The time complexity of deleting an element is O(n), because the amount of data to traverse the list increases several times, so does the time.

4) The time complexity of finding an unsorted list is O(n), because the list is traversed; Searching sorted lists takes O(log n) time, because binary search methods can be used, and when the data increases by n times, the time increases by logn times (log base 2 here, eliminating half of the possibilities for each search).

I am the Silent King 2, a programmer with good looks but mediocre talent. Attention can improve learning efficiency, don’t forget three even ah, like, favorites, leave a message, I don’t pick, Ollie.

Note: If there are any problems with the article, please kindly correct them.

Many readers sympathize with me and say, “Brother, you are more original like sow day tired?” I can only say that writing is not easy, and I cherish it. The point is that I really like writing. Finally, welcome to wechat search “Silent King ii” for the first time to read, reply to “resume” more ali tycoon’s resume template, this article GitHub github.com/itwanger has been included, welcome star.