As can be seen from the picture,ArrayListwithLinkedListAre implementation classes for the List interface, and therefore implement all unimplemented methods of the List, just in different ways. The List interface inherits from the Collection interface, which in turn inherits from the Iterable interface. Therefore, it can be seen that the List has both Collection and Iterable features.

ArrayList

ArrayList is a mutable array implementation of the List interface. All optional list operations are implemented and all elements, including NULL, are allowed. In addition to implementing the List interface, this class also provides methods to manipulate the size of the array internally used to store the List. Each ArrayList instance has a capacity, which is the size of the array used to store the elements of the list. It is always at least equal to the size of the list. As you add more elements to an ArrayList, its capacity automatically grows. Automatic growth causes a new copy of the data into the new array, so if you can predict how much data you have, you can specify its capacity when constructing an ArrayList. An application can also use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements, which reduces the amount of incremental reallocation. Note that this implementation is not synchronous. If multiple threads access an ArrayList instance simultaneously, and at least one of them structurally modifies the list, it must maintain external synchronization. This is usually done by synchronizing the objects used to encapsulate the list. But if there is no such objects exist, the need to use the list {@ link Collections# synchronizedList Collections. SynchronizedList} to “packaging”, this method is best done when creating a list of objects, To avoid sudden asynchronous operations on the list.

List list = Collections.synchronizedList(new ArrayList(...) );Copy the code

ArrayList is recommended for single-threaded applications, whereas Vector or CopyOnWriteArrayList are options for multi-threaded applications.

capacity

An obvious feature of an array is that its capacity is fixed. Once an array is created, its capacity cannot be changed. So the first thing to consider before adding a specified element to an array is whether it is saturated.

If the elements in the array exceed their capacity in subsequent appending operations, they must be expanded. Due to the fixed size of arrays, the essence of expansion is to create a new array with a larger capacity and then copy the elements of the old array into the new array.

This section takes adding an ArrayList as an example to look at the process of adding an array to an ArrayList.

public boolean add(E e) {
	// Key -> Verify capacity before adding
	ensureCapacityInternal(size + 1); 
	
	// Change the size and add the specified element to the end of the array
	elementData[size++] = e;
	return true;
}Copy the code

You can see that ArrayList checks the internal array capacity and selectively expands the array before adding. In ArrayList, arrays are expanded using the private method ensureCapacityInternal. Let’s look at the implementation process:

  • The first step of the expansion operation checks whether the current ArrayList is empty. If it is empty, minCapacity is set to 10.
// The default size of the internal array
private static final int DEFAULT_CAPACITY = 10;

// An empty internal array
private static final Object[] EMPTY_ELEMENTDATA = {};

// key -> minCapacity = seize+1, that is, the number of elements in the array after the add operation
private void ensureCapacityInternal(int minCapacity) {
	// Check whether the internal array is empty
	if (elementData == EMPTY_ELEMENTDATA) {
		// Set the minimum size of the array (>=10)
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}Copy the code
  • We then determine whether the add operation will saturate the internal array.
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	
	// If the result is true, the number of elements will exceed the array capacity as a result of subsequent additions
	if (minCapacity - elementData.length > 0) {// True expansion operationgrow(minCapacity); }}Copy the code
  • If the array capacity is insufficient, the expansion operation is performed. There are two key points: expansion formula and expansion operation by copying elements from the old array to the new array.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	
	int oldCapacity = elementData.length;
	
	// Key -> Capacity expansion formula
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	
	// A series of judgments for the new capacity
	if (newCapacity - minCapacity < 0){
		newCapacity = minCapacity;
	}
	if (newCapacity - MAX_ARRAY_SIZE > 0){
		newCapacity = hugeCapacity(minCapacity);
	}
		
	// Key -> copy the old array elements into the new array
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) {throw new OutOfMemoryError();
	}
			
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}Copy the code

For the ArrayList expansion operation, the whole process is shown as follows:



LinkedList

  1. LinkedList is a bidirectional LinkedList derived from AbstractSequentialList. It can also operate as a stack, queue, or double-endian queue.
  2. LinkedList implements the List interface to queue operations on it.
  3. LinkedList implements the Deque interface, which allows the LinkedList to be used as a two-ended queue.
  4. LinkedList implements the Cloneable interface, which overwrites the clone() function.
  5. LinkedList implements the Java.io.Serializable interface, which means that LinkedList supports serialization and can be transmitted via serialization.
  6. LinkedList is asynchronous.

As shown in the figure above, the underlying LinkedList uses a bidirectional LinkedList structure with one head and one tail. Bidirectional linked lists mean that we can traverse forward from the beginning, or backward from the tail, and do things for the head and tail.

private static class Node<E> {

E item;

Node<E> next;

Node<E> prev;

Node(Node

prev, E element, Node

next) { this.item = element; this.next = next; this.prev = prev; }}

conclusion

1.ArrayList is a data structure based on dynamic array, while LinkedList is a data structure based on LinkedList. 2. ArrayList feels superior to LinkedList for random access to GET and set because LinkedList moves the pointer. 3. For add and remove operations, LinedList has an advantage because ArrayList moves data.