ArrayList and LinkedList design structure
Note:
- The green solid line is the inheritance relationship between interfaces
- The green dotted line is the class implementation interface relationship
- Blue implementations are inheritance relationships between classes
1. ArrayList design structure
2. LinkedList design structure
3. Analyze the structures of ArrayList and LinkedList
- On the whole, the main difference between ArrayList and LinkedList is that LinkedList implements the Queue interface, that is, LinkedList can be used directly as a Queue. ArrayList cannot be directly used as a Queue, but you can define your own Queue and use ArrayList as the storage structure.
//LinkedList is used directly as a queue Queue queue = new LinkedList();
- ArrayList and LinkedList both implement iteratable, so they can use iterators to traverse. The code is as follows:
public static void main(String[] args) {
User user = new User();
User user1 = new User();
user.setUname("ligel");
user.setAge(10);
user1.setUname("aaa");
user1.setAge(90);
List<User> arrayList= new ArrayList<User>();
List<User> linkedList = new LinkedList<User>();
arrayList.add(user);
arrayList.add(user1);
linkedList.add(user);
linkedList.add(user1);
//Traversing ArrayList with iterators
System.out.println("~~~~~~~~ArrayList ergodic~~~~~~~~~~");
Iterator it01= arrayList.iterator();
it01.forEachRemaining(System.out::println);
System.out.println("~~~~~~~~LinkedList ergodic~~~~~~~~~~");
Iterator it02= linkedList.iterator();
while(it02.hasNext()){
User item = (User) it02.next();
System.out.println(item);
}
}
- Both ArrayList and LinkedList implement the Collection and List interfaces.
ArrayList source code analysis
Contains properties, constructors, and all methods.
Attribute analysis
- private static final long serialVersionUID serialVersionUID
It is a serialization ID, which is used to match the version of deserialization. This ID cannot be changed arbitrarily. I won't introduce serialization here. - private static final int DEFAULT_CAPACITY
The default size for creating an ArrayList is 10 - EMPTY_ELEMENTDATA :
Empty array, the official annotation is: in order to calculate how much space is needed to add the first element. Because the default initialization is empty, the required size of the element added to the ArrayList. - transient Object[] elementData
Where the actual data is stored, the object is stored. Object is the base class of all classes. - private int size
The actual size of the ArrayList. This data is reduced by one when deleted and increased by one when added.
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
Constructor analysis
1. public ArrayList(int initialCapacity)
This constructor is to set the size when creating ArrayList, which is similar to the initialization of array.
- Internally, it determines whether initialCapacity is equal to zero. If it is equal to zero, it is defined as an empty set
- If it is greater than zero, the collection will be created normally
- If it is less than zero, an exception will be thrown
public ArrayList(int initialCapacity) {
/**
* 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//When the initialization value is less than zero, an exception will be thrown
*/
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);
}
}
2. public ArrayList()
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- This is an empty constructor. By default, an ArrayList with an empty initial value size is created.
2. public ArrayList(Collection<? extends E> c)
The construction method is to store the elements saved by the incoming collection into the currently created ArrayList.
/**
* 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;
}
}
The implementation idea of this method
First, the combination of the transmitted image is converted into an array through the toArray() method and assigned to elementData
Go to toArray() to see the source code
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
-
The Object[] toArray() method is also a method in the ArrayList class.
-
This method only calls copyOf(elementData, size) in the Arrays class
Enter copyOf(elementData, size) to see:
-
This method is also very concise. It calls the method with the same name under the same package (polymorphic), in which there is an additional parameter original getClass()
-
original.getClass(): this parameter is to get the type of runtime element of the array we want to copy. About element Class and element I won't introduce the difference between getclass(). reference resources
/*
* @param <T> the class of the objects in the array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
Go to copyOf(original, newLength, original.getClass()) and have a look:
This method is to create a new array with the size of the passed in array, and there are elements of the array that need to be assigned.
/*
* @param <U> the class of the objects in the original array
* @param <T> the class of the objects in the returned array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @param newType the class of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @throws ArrayStoreException if an element copied from
* <tt>original</tt> is not of a runtime type that can be stored in
* an array of class <tt>newType</tt>
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
Analyze this method in detail
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
Some people will wonder, why should we make a Sanmu judgment? Is to create a new array directly
Execute (t []) array Newinstance (newtype. Getcomponenttype(), newlength) is not enough. Should be array Newinstance (,) is the case that contains new Object[newLength].
Here we mainly consider the performance problem, array Newinstance (,) uses reflection mechanism. After checking the data, it is found that the operation efficiency of the reflection mechanism is lower than ew Object[newLength]. Therefore, the reason why Sanmu transportation is to consider the performance. reference resources
After analyzing the combination into an array, let's go back to the constructor
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
//Analyze from here
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;
}
}
-
If the size of the obtained array is zero, which means that the collection we pass in is empty, we will create an empty collection (which is the same as I directly use the parameterless constructor to build the ArrayList Collection).
-
Size is not zero, if (elementdata. Getclass())= Object[]. class)
- The code is to judge that the element type of the array runtime is different from the type we specify, so we use the type we specify as the specified type of the array.
- Next, call copyOf(elementData, size, Object[].class). This method is the same as when I analyzed the method combined with array conversion.
To summarize this constructor
-
The constructor is a constructor with one parameter, which is a collection type. By assigning the set element of the passed in parameter to the new set. Vernacular is to copy a collection.
-
This method is mainly implemented through copyOf(elementData, size, Object[].class).
Doubts
- (elementData.getClass() != Object[]. What is the use of this judgment?