List in java: A brief introduction to the ArrayList and LinkedList implementation interfaces

ArrayList is implemented based on arrays. It is a dynamic array whose capacity can grow automatically, similar to dynamically applying for memory and dynamically growing memory in C language. LinkedList is implemented based on a two-way circular linked list (which can be easily seen from the source code). In addition to being operated as a linked list, it can also be used as a stack, queue and double-ended queue.

1. Introduction to List

2. ArrayList

Characteristics of ArrayList

ArrayList is based on array implementation and is a Dynamic array, its capacity can automatically grow, similar to dynamically applying for memory and dynamically growing memory in C language.

ArrayList is thread-unsafe, can only be used in a single-threaded environment, in a multi-threaded environment you can consider using the Collections.synchronizedList(List list) function to return A thread-safe ArrayList class, you can also use the CopyOnWriteArrayList class under the concurrent package.

ArrayList implements the Serializable interface, so it supports serialization, can be transmitted through serialization

ArrayList implements the RandomAccess interface, supporting fast random access, which is actuallyQuick access through subscript serial number

Implements the Cloneable interface, can be cloned

Pay attention to its three different construction methods. The capacity of the ArrayList constructed by the parameterless constructor is 10 by default. The constructor with Collection parameters converts the Collection into an array and assigns it to the ArrayList implementation array elementData. There is also a constructor that specifies the capacity.

Pay attention to the method of expanding capacity, ensureCapacity. Each time an element is added to ArrayList (it may be 1 or a group), this method must be called to ensure sufficient capacity. When the capacity is not enough to accommodate the current number of elements, the new capacity is set to 1.5 times the old capacity plus 1. If the set new capacity is not enough, the new capacity is directly set to the passed in parameter (that is, the required capacity), and then use the Arrays.copyof() method to copy the elements to a new array (see point 3 below for details). It can be seen from this that when the capacity is not enough, each time an element is added, the original elements must be copied to a new array, which is very time-consuming. Therefore, it is recommended to use ArrayList only when the number of elements can be determined in advance. , otherwise it is recommended to use LinkedList.

The implementation of ArrayList calls a large number of Arrays.copyof() and System.arraycopy() methods. It is necessary for us to have an in-depth understanding of the implementation of these two methods.

First look at the Arrays.copyof() method. It has many overloaded methods, but the implementation ideas are the same. Let’s look at the source code of the generic version:

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

Obviously another copyof method is called, which has three parameters, the last one The parameter specifies the type of data to be converted. The source code is as follows:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

It can be clearly seen that this method actually creates an array with a length of newlength inside it and calls System.arraycopy () method copies the elements in the original array to the new array.

Let’s look at the System.arraycopy() method. This method is marked native and calls the system's C/C code. It cannot be seen in JDK, but its source code can be seen in openJDK. This function actually ultimately calls the memmove() function of C language, so it can ensure the correct copying and moving of elements in the same array. It is much more efficient than the general copying method and is very suitable for batch processing of arrays. Java strongly recommends using this method when copying a large number of array elements to achieve higher efficiency.

Pay attention to the two toArray methods of ArrayList that are converted into static arrays.

The first one, Object[] toArray() method. This method may throw a java.lang.ClassCastException. If you directly use the downward conversion method to convert the entire ArrayList collection into an Array array of the specified type, this exception will be thrown. However, if you do not convert it into an Array array, Downcasting, but downcasting each element, will not throw this exception. Obviously, downcasting the elements in the array one by one is not efficient and inconvenient.

Second, T[] toArray(T[] a) method. This method can directly transform the Array converted from ArrayList downward as a whole (the transformation is actually implemented in the source code of this method), and it can be seen from the source code of this method that when the size of parameter a is insufficient, it will be called internally Arrays.copyOf method, this method internally creates a new array and returns it, so the common form of this method is as follows:

public static Integer[] vectorToArray2(ArrayList<Integer> v) {  
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);  
    return newText;  
}

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

三、LinkedList

LinkedList的特点

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用；

LinkedList同样是非线程安全的，只在单线程下适合使用；

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输；

实现了Cloneable接口，能被克隆；

相关推荐：

接口测试基础之入门篇

视频教程：

去除ArrayList集合中的重复自定义对象元素案例

The above is the detailed content of List in java: A brief introduction to the ArrayList and LinkedList implementation interfaces. For more information, please follow other related articles on the PHP Chinese website!