[JAVA] List and happy classes

Introduction

I received a comment in Previous article, so I will write that I was interested in writing a little. Regarding Java List related classes, when I look at the source code of others while I usually work, I wonder if there are few people who are aware of it.

Classes under List and what is described in this article

For the class that implements the List interface, see "All known implementation classes" in here. As you can see, there are many. Among them, I will write about the following three classes, which are relatively famous (?). ・ ArrayList ・ LinkedList ・ Arrays $ ArrayList (I've never used anything other than these, so I'm not familiar with it)

ArrayList initialCapacity As you probably know, ArrayList is a class that everyone uses a lot, but have you ever been aware of initialCapacity? This is probably the best way to write an instance of an ArrayList.

Capacity.java

List<?> list = new ArrayList<>()

On the other hand, did you know that you can instantiate in this way?

Capacity.java

List<?> list = new ArrayList<>(100)

An int of 100 is specified as the argument of the constructor. This 100 is the initialCapacity. Specifies the number of elements to be initialized in ArrayList. What if I don't specify an argument? Let's take a look at the source of the ArrayList.

ArrayList.class (excerpt: Constructor 1)

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

Somehow an empty array is stored in elementData. I'm not sure if this is all. Next, let's take a look at the contents of the add () method.

ArrayList.class (excerpt: around add)

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

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

Immediately after add (), the ensureCapacityInternal () method is called. In ensureCapacityInternal (), the ensureExplicitCapacity () method is called after setting minCapacity. If you did not set initialCapacity in the constructor, as you saw earlier, elementData is set to DEFAULTCAPACITY_EMPTY_ELEMENTDATA (an empty array), so the if statement conditions are met and "minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity)" is set. It is done. As a result, minCapacity is set to 10 (DEFAULT_CAPACITY) and passed to ensureExplicitCapacity (). ensureExplicitCapacity () is a method to secure the capacity of the array. In other words, if no argument is set in the constructor of ArrayList, the elements stored in ArrayList will be managed by an array with 10 elements. So what about the constructor for those who specify initialCapacity?

ArrayList.class (excerpt 3)

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

If you specify an integer other than 0, an array for the specified number of elements is generated instead of an empty array. The behavior when add () is basically the same except that it does not pass through the if statement of the ensureCapacityInternal () method.

What does it mean to specify initialCapacity?

What does it mean to specify initialCapacity? You can see that by looking at the behavior when adding more elements than the number specified by initialCapacity. This is the implementation part (continuation of ensureCapacityInternal ()).

ArrayList.java (excerpt)

    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);
    }

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }

In the ensureExplicitCapacity () method, the grow () method is called when the condition is met. The point is ʻint newCapacity = oldCapacity + (oldCapacity >> 1); `of the grow () method, and if the number of elements secured by initialCapacity is exceeded by adding elements, the capacity is multiplied by 1.5 (fraction). Truncation).

• ">>" is a shift operation. See here So, if you add a total of 100 elements, one for each ArrayList with initialCapacity set to 10, how will the number of elements in elementData change?

Initial value: 10 Added 11th element: 10 * 1.5 = 15 Added 16th element: 15 * 1.5 = 22 Added 23rd element: 22 * 1.5 = 33 Added 34th element: 33 * 1.5 = 49 Added 50th element: 49 * 1.5 = 73 Added 74th element: 73 * 1.5 = 109 I was finally able to add 100 elements here.

Difference in performance depending on the initialCapacity setting

This movement is likely to cause some overhead, isn't it? How much is it? I actually measured the execution time when add () while looping 100,000 data. This is the program used for the actual measurement.

DefaultListSize.java

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

public class DefaultListSize {
    private static final int CNT = 100000;
    public static void main(String... args) {
        //initialCapacity not specified
        List<Integer> defaultList = new ArrayList<>();

        long startDefautl = System.currentTimeMillis();
        for (int i = 0; i < CNT; i++) {
            defaultList.add(i);
        }
        long endDefautl = System.currentTimeMillis();
        System.out.println("Execution time (milliseconds):" + (endDefautl - startDefautl));

        //initialCapacity specification
        List<Integer> list = new ArrayList<>(CNT);
        long start = System.currentTimeMillis();
        for (int i = 0; i < CNT; i++) {
            list.add(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Execution time (milliseconds):" + (end - start));
    }
}

Execution result

Execution time (milliseconds):4
Execution time (milliseconds):1

If you did not specify initialCapacity, it was 4 milliseconds, and if you specified 100,000, it was 1 millisecond. By the way, when 10 million was specified, it was 731 milliseconds and 258 milliseconds. I can't say anything about the number of seconds because it is related to the specifications of the PC, but you can see that by specifying initialCapacity, there is no extra processing and the speed is increased accordingly. If you know that you will handle a large amount of data, it seems better to specify it properly.

LinkedList

Feature

Next is the LinkedList. LinkedList is good at adding and deleting elements, but it is not good at random access. Random access is list.get (i) at the source code level. The cause of this feature is the way elements are managed. It is managed by linking the i-th element to the i-1st and i + 1th elements. To get an element, just follow the link from the beginning or end, and to delete it, just replace the link.

I think the difference will be clear when you compare it with the ArrayList. ArrayList is good at random access because you can get elements directly using index.

On the other hand, if you delete it, you need to rebuild the array, which adds overhead.

Differences in random access behavior

Due to this feature, ArrayList and LinkedList behave differently during random access. In the case of ArrayList, even if you randomly access with list.get (i), you can get the element immediately, so you can respond immediately. This is the image.

In the case of LinkedList, the target element cannot be obtained unless the first element is followed in order. If you write list.get (4), you can finally reach the target element by following the order of 1 → 2 → 3 → 4. This is the image.

LinkedList can also be scanned in reverse order, so list.get (7) in the above example will surely follow in the order of 10 → 9 → 8 → 7.

What is the performance when looping a large amount of data?

Up to this point, I think it's "Hmm. So what if you loop through a lot of data and list.get (i)? Specifically, if you have a class like this, do you know what happens if you pass a LinkedList that holds a lot of data as an argument when calling this method? The point is that list.get (i) is done while looping.

ListSizeLoop.java

class ListSizeLoop {
    public void listSizeLoop(List<String> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

I found this article. This is exactly this. This can happen. The story that I ended up taking a break if I used the Linked List with a light feeling

What should I do?

As mentioned in the previous article, use the extension for (or Iterator) instead of looping with list.size (). Using the extension for for a List (to be precise, for a class that implements the Iterable interface) causes the Iterator to be expanded internally. Iterator is one of the design patterns and is an interface specialized for sequential processing. This alone avoids random access. This can happen if you loop using list.size (), so use the extended for unless you have a clear reason to do so.

Arrays$ArrayList

Arrays $ ArrayList is a fixed length List

The last is Arrays $ ArrayList. It's named ArrayList, but it's different from the well-known java.util.ArrayList. Inside the java.util.Arrays class, there is an inner class named ArrayList that implements the List interface ("$" is a Java reserved word to indicate that it is an inner class). This is a List that is convenient when converting an array to a List or specifying elements in advance when creating an instance, and assumes a fixed length. The usage is as follows.

ArraysAsList.java

import java.util.Arrays;
import java.util.List;

public class ArraysAsList {
    public static void main(String... args) {
        String[] strList = new String[3];
        strList[0] = "a";
        strList[1] = "b";
        strList[2] = "c";
        //Convert array to List
        List<String> list1 = Arrays.asList(strList);
        for (String str : list1) {
            System.out.println(str);
        }

        //Generate a List that holds the elements from the beginning
        List<String> list2 = Arrays.asList("d", "e", "f");
        for (String str : list2) {
            System.out.println(str);
        }
    }
}

What happens when you add ()?

I mentioned earlier that it assumes a fixed length, but what happens when you add ()?

ArraysAsList2.java

import java.util.Arrays;
import java.util.List;

public class ArraysAsList2 {
    public static void main(String... args) {
        //Add after instance creation()Method call
        List<String> list = Arrays.asList("d", "e", "f");
        list.add("a");
        for (String str : list) {
            System.out.println(str);
        }
    }
}

Execution result

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)
	at ArraysAsList2.main(ArraysAsList2.java:8)

An UnsupportedOperationException has occurred. Let's take a look at Arrays $ ArrayList.

Arrays.java

public class Arrays {
    @SafeVarargs
    @SuppressWarnings("varargs")
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

    /**
     * @serial include
     */
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return a.clone();
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size,
                                     (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) {
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

        @Override
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }

        @Override
        public Spliterator<E> spliterator() {
            return Spliterators.spliterator(a, Spliterator.ORDERED);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            for (E e : a) {
                action.accept(e);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            E[] a = this.a;
            for (int i = 0; i < a.length; i++) {
                a[i] = operator.apply(a[i]);
            }
        }

        @Override
        public void sort(Comparator<? super E> c) {
            Arrays.sort(a, c);
        }
    }
}

I can't find the add () method. Is it a higher class? AbstractList is extended, so let's take a look.

AbstractList.java

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

    /**
     * {@inheritDoc}
     *
     * <p>This implementation always throws an
     * {@code UnsupportedOperationException}.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

This is it. I'm throwing an UnsupportedOperationException with no questions asked. AbstractList is also available in ArrayList, Vector, and [AbstractSequentialList](https://docs. oracle.com/javase/jp/8/docs/api/java/util/AbstractSequentialList.html) also extends. Since LinkedList extends AbstractSequentialList, it is indirectly under AbstractList. I don't think you can write it in letters, but you can see that it is under AbstractList by looking at the figure below.

Difference from java.util.ArrayList (implementation side)

Let's take a look at ArrayList as an example of a class that extends AbstractList other than Arrays $ ArrayList.

ArrayList.java (excerpt from add part)

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

You're overriding the add () method. Since java.util.ArrayList overrides add () of AbstractList, UnsupportedOperationException does not occur and the implemented processing is performed. Arrays $ ArrayList does not override the add () method, so you will get an UnsupportedOperationException. Even though they have the same name as ArrayList, they are completely different ... AbstractList is a partial implementation of the List interface. By implementing the minimum required, the part that needs to be implemented as a concrete class is reduced, but if you do not override set (), add (), remove (), UnsupportedOperationException will be thrown. .. The same thing happens because Arrays $ ArayList does not override remove () as well as add (). Since set () is overriding, you can replace the existing element with another by calling this method.

If you want to convert an array to a variable length List

Arrays $ ArayList has a fixed length because add () and remove () cannot be called. If you want to convert an array to a variable length List, do the following:

ArraysAsList3.java

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

public class ArraysAsList3 {
    public static void main(String... args) {
        String[] strList = new String[3];
        strList[0] = "a";
        strList[1] = "b";
        strList[2] = "c";
        //Convert array to List via ArrayList constructor
        List<String> list = new ArrayList<>(Arrays.asList(strList));
        for (String str : list) {
            System.out.println(str);
        }
    }
}

With the description List <String> list = new ArrayList <> (Arrays.asList (strList));, it is converted in the order of array → Arrays $ ArrayList → ArrayList. In addition to the initialCapacity introduced earlier, there is another constructor that receives a Collection in the ArrayList constructor. You can use this constructor to convert ʻArrays $ ArrayList to java.util.ArrayList`. Since AbstractList extends AbstractCollection and AbstractCollection implements Collection, you can pass Arrays $ ArrayList as an argument to this constructor. I think this is also easier to understand if you look at the previous figure.

The implementation of the constructor of the ArrayList that receives the Collection is as follows.

ArrayList (partial excerpt of constructor)

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    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;
        }
    }

When I was just starting to use Java, I misunderstood Arrays $ ArrayList as the same as java.util.ArrayList and was quite confused, so I wrote it down.

At the end

It feels like I've written a lot about what I came up with about List. I hope you've noticed even one thing, "Oh, that's right !?" that's all.