Spoiler: ArrayList's insertion and query operations are much faster than LinkedList
ArrayList
characteristic
- The bottom layer is realized by array, with fast query speed and slow addition, deletion and modification speed (in theory)
- Thread unsafe
Common methods of ArrayList
import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * @author Zhang Baoxu */ public class ArrayListTest { public static void main(String[] args) { List<String> list = new ArrayList<>(); // Create ArrayList list.add("Beijing"); // Add element list.add("Shanghai"); list.add("Hangzhou"); list.add("Shenyang"); list.add("Dongdaihe"); System.out.println(list.toString()); // Print set System.out.println(list.size()); // Get collection size System.out.println(list.get(0)); // Gets the element of the specified subscript list.remove(0); // Deletes the element with the specified subscript list.remove("Shanghai"); // Delete the specified element System.out.println(list.isEmpty()); // Judge whether the set is empty System.out.println(list.contains("Beijing")); // Interpret whether the set contains an element // Iterate over collection elements Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } System.out.println(); // Enhanced for traversal for (String value : list) { System.out.print(value + " "); } } }
Operations on basic data types
When you add a basic data type to the list, it will be automatically boxed into a packing type
List<Integer> lit = new ArrayList<>(); lit.add(12); lit.add(25); lit.add(99);
And when we delete the specified element
lit.remove(12);
Because 12 is a basic data type, this deletion method deletes elements with subscript 12
Therefore, you need to change the deletion statement to convert the 12 strong to the packaging type
lit.remove((Integer)12);
In this way, the element with 12 in the list can be deleted correctly
ArrayList source code analysis
The underlying uses arrays to hold elements
transient Object[] elementData;
Default capacity: 10
private static final int DEFAULT_CAPACITY = 10;
ArrayList construction method
When a list is created and no elements are added to the list, the capacity is 0
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
add() method (capacity expansion)
1. When there is no element in the list, the capacity is expanded to 10 after adding an element
public boolean add(E e) { // Initially, the size is 0, so 1 is passed in ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { // At first, the array is empty, so the condition holds if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // Let minCapacity = the maximum number between the two // DEFAULT_CAPACITY is the default capacity of 10, and the parameter passed in by minCapacity is 1 // So minCapacity = 10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } // Then call this method, and the passed in parameter is 10 ensureExplicitCapacity(minCapacity); }
private void ensureExplicitCapacity(int minCapacity) { // Number of modifications, plus one modCount++; // overflow-conscious code // The initial array length is 0, so 10-0 > 0 holds if (minCapacity - elementData.length > 0) // Call this method grow(minCapacity); }
private void grow(int minCapacity) { // overflow-conscious code // The original array length is 0 int oldCapacity = elementData.length; // New array length = original length + (original length divided by 2) = 0 + 0 / 2 = 0 int newCapacity = oldCapacity + (oldCapacity >> 1); // 0 - 10 < 0 if (newCapacity - minCapacity < 0) // So the new array length is assigned = 10 newCapacity = minCapacity; // 10 - a large number > 0 does not hold, so it will not be executed if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // This method is then called to copy the array // The original array is given a new length of 10 and copied into this array to realize the expansion of the array elementData = Arrays.copyOf(elementData, newCapacity); }
Therefore, the operation of expanding the array to 10 when adding an element at the beginning is realized here
Then perform the remaining operations of the add() method, add the value to the array, and increase the size by one
Sort out the process again
- First call the add() method
- Then call the ensureCapacityInternal() method to determine whether the element in the list is empty. If it is empty, the parameter of capacity expansion is 10
- Then call the ensueexplicitcapacity () method to determine whether the minimum capacity is greater than the length of the array. If it is not greater than, there is no need to expand the capacity. If it is greater than, expand the capacity and call the grow(minCapacity) method
- Then call the grow(minCapacity) method of the, give the length of the expansion, and then use the array copy method to expand the capacity
- Finally, execute the add() method to add the value to the array, and increase the size by one
2. When there are elements in the list, but the size of the array is not exceeded, add elements to the list
(if there is an element in the set at this time, size=1, and the length of the array is 10)
// First, call the add method to add public boolean add(E e) { // Judge whether capacity expansion is required. The input parameter is 2 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { // The array is not empty, so the condition does not hold if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } // Then call this method directly ensureExplicitCapacity(minCapacity); }
private void ensureExplicitCapacity(int minCapacity) { // Number of modifications plus one modCount++; // overflow-conscious code // 2 - 10 > 0, the condition is not tenable, and the downward execution is not allowed if (minCapacity - elementData.length > 0) grow(minCapacity); }
Finally, the add() method is executed
// Add a new element e to the position of size, and then add one to the length size elementData[size++] = e;
3. When there are elements in the list and the length is full, the second expansion is required
(if current array size = 10)
// First call the add() method to add public boolean add(E e) { // For capacity expansion, the input parameter is 11 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { // The array is not empty, so the condition does not hold if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } // Call this method directly, and the passed in parameter is 11 ensureExplicitCapacity(minCapacity); }
private void ensureExplicitCapacity(int minCapacity) { // Number of modifications plus one modCount++; // overflow-conscious code // 11 - 10 > 0, the condition holds, and the grow method is called if (minCapacity - elementData.length > 0) grow(minCapacity); }
private void grow(int minCapacity) { // overflow-conscious code // Original array length = 10 int oldCapacity = elementData.length; // New array length = 10 + (10 / 2) = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); // The condition of < 11 - 15 does not hold if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 15 - large number > 0 condition does not hold if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // Therefore, directly execute this method to copy the original array and also copy it to the original array (equivalent to overwrite) // The copy length is 15, which realizes the expansion of the array elementData = Arrays.copyOf(elementData, newCapacity); }
Finally, execute the add() method, add the element to the back, and then add one to size
According to the code
int newCapacity = oldCapacity + (oldCapacity >> 1);
Expand the capacity when adding elements for the first time. The size of each expansion is 1.5 times the original size (moving one bit to the right is to divide by 2)
remove() method
If there are 10 elements, delete the element with subscript 3
public boolean remove(Object o) { // First judge whether the incoming object is null if (o == null) { // If it is null, it will traverse the array again to find whether there are elements with null value for (int index = 0; index < size; index++) // When an element with null value is found, it is quickly deleted, and then true is returned, indicating that the deletion is successful if (elementData[index] == null) { fastRemove(index); return true; } } else { // If the object passed in is not null, it is also traversed for (int index = 0; index < size; index++) // A matching object was found in the array if (o.equals(elementData[index])) { // Then use the quick delete method to delete the found element with index fastRemove(index); return true; } } return false; }
private void fastRemove(int index) { // Number of modifications plus one modCount++; // Number of times the element needs to be moved 10 - 3 - 1 = 6 // 0 1 2 3 4 5 6 7 8 9 // Because there are six elements behind position 3, after deletion, these six elements must move forward one bit int numMoved = size - index - 1; // If you need to move elements if (numMoved > 0) // Using the array copy method, start from the position of index+1 and move the following elements forward by one bit (that is, forward overwrite) System.arraycopy(elementData, index+1, elementData, index, numMoved); // After moving, you need to clear the value of the last element, and then reduce the size by one to complete the deletion operation elementData[--size] = null; // clear to let GC do its work }
LinkedList
characteristic
- The bottom layer is realized by linked list, which has fast insertion and deletion speed (theoretically) and fast query speed
- LinkedList can be used to implement stack, queue and other data structures
LinkedList common methods
import java.util.*; /** * @author Zhang Baoxu */ public class LinkedListTest { public static void main(String[] args) { LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("I"); // Add element linkedList.add("Love"); linkedList.add("You"); linkedList.add("Very"); linkedList.remove("Very"); // Delete the specified element linkedList.size(); // Get list length linkedList.get(0); // Gets the element of the specified subscript linkedList.contains("Love"); // Determines whether the specified element is included linkedList.indexOf("I"); // Gets the subscript of the specified element linkedList.set(1, "love"); // Modify the element of the specified subscript // Convert list to array String[] strings = linkedList.toArray(new String[0]); System.out.println(Arrays.toString(strings)); // for loop traversal for(int i = 0; i < linkedList.size(); i++) { System.out.print(linkedList.get(i) + " "); } System.out.println(); // Enhanced for traversal for (String s : linkedList) { System.out.print(s + " "); } System.out.println(); // Iterator traversal Iterator<String> iterator = linkedList.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } System.out.println(); // List iterator traversal (reverse traversal) ListIterator<String> listIterator = linkedList.listIterator(linkedList.size()); while (listIterator.hasPrevious()) { System.out.print(listIterator.previousIndex() + " : " + listIterator.previous() + " "); } } }
LinkedList source code analysis
Basic properties
Construction method
public LinkedList() { }
Linked list length
transient int size = 0;
Head pointer
transient Node<E> first;
Tail pointer
transient Node<E> last;
add() method
public boolean add(E e) { linkLast(e); return true; }
void linkLast(E e) { // Create a temporary pointer to last, that is, l is the last node final Node<E> l = last; // Create a node, the precursor pointer points to l, the element is e, and the subsequent node points to null final Node<E> newNode = new Node<>(l, e, null); // Make the last pointer point to the new node last = newNode; // When l is empty, it indicates that the linked list is empty. Add it directly and make the header pointer point to the new node // At this time, there is only one node. last points to it and first points to it if (l == null) first = newNode; else // When l is not empty, it indicates that there are elements in the linked list, so the subsequent pointer of L points to the new node // At this time, the connection of the two-way linked list is completed (the second part completes the precursor pointer pointing to l) l.next = newNode; size++; modCount++; }
remove() method
public boolean remove(Object o) { // First determine whether the element to be deleted is null if (o == null) { // If so, traverse the linked list to find the node with null node value for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { // Call this method to delete elements when found unlink(x); return true; } } } else { // If the element to be deleted is not null, you can also traverse the linked list to find this element for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { // Call this method to delete elements when found unlink(x); return true; } } } return false; }
E unlink(Node<E> x) { // assert x != null; // Take out the value, successor node and predecessor node of the node final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; // If the precursor node is empty, it means that the header node is to be deleted if (prev == null) { // So direct the header pointer to the next one and skip the original header node first = next; } else { // Otherwise, the intermediate node is to be deleted // After a long time, point the subsequent pointer of the predecessor node of the node to be deleted to the subsequent node of the element to be deleted // That is to point its front to its back and skip it by itself prev.next = next; // Then make the precursor node of the element to be deleted null and release the jump precursor pointer x.prev = null; } // The above is the modification precursor, and the following is the modification successor // When the subsequent node of the element to be deleted is empty, this node is the tail node if (next == null) { // Therefore, the pointer directly leading its tail points to the previous one and skips the last node last = prev; } else { // Otherwise, the intermediate node is deleted // Point the precursor pointer of the last node of that node to the precursor node of that node, and skip it by itself next.prev = prev; // Then set the subsequent pointer of that node to null and release this pointer x.next = null; } // The precursor pointer is released, and the subsequent pointer is released. Now release the value of this node and set the value to null x.item = null; size--; // The length of the linked list minus one modCount++; // Number of modifications plus one return element; // Returns the deleted element }
Test the performance of ArrayList and LinkedList
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /** * Test the performance of ArrayList and LinkedList. * * @author Zhang Baoxu */ public class PerformanceTest { // A million times static final int QUERY_COUNT = 10000000; static List<String> arrayList = new ArrayList<>(); static List<String> linkedList = new LinkedList<>(); public static void main(String[] args) { // insert PerformanceTest.arrayListInsert(); PerformanceTest.linkedListInsert(); // query PerformanceTest.arrayListQuery(); PerformanceTest.linkedListQuery(); } /** * Test ArrayList insertion performance */ public static void arrayListInsert() { long startTime = System.currentTimeMillis(); for(int i = 0; i < QUERY_COUNT; i++) { arrayList.add(String.valueOf(i)); } long endTime = System.currentTimeMillis(); System.out.println("ArrayList Insert elapsed time: " + (endTime - startTime)); } /** * Test LinkedList insertion performance */ public static void linkedListInsert() { long startTime = System.currentTimeMillis(); for(int i = 0; i < QUERY_COUNT; i++) { linkedList.add(String.valueOf(i)); } long endTime = System.currentTimeMillis(); System.out.println("LinkedList Insert elapsed time: " + (endTime - startTime)); } /** * Test ArrayList query performance */ public static void arrayListQuery() { long startTime = System.currentTimeMillis(); for(int i = 0; i < QUERY_COUNT; i++) { arrayList.get(i); } long endTime = System.currentTimeMillis(); System.out.println("ArrayList Query consumption time: " + (endTime - startTime)); } /** * Test LinkedList performance */ public static void linkedListQuery() { long startTime = System.currentTimeMillis(); for(int i = 0; i < QUERY_COUNT; i++) { linkedList.get(i); } long endTime = System.currentTimeMillis(); System.out.println("LinkedList Query consumption time: " + (endTime - startTime)); } }
result
ArrayList Insert elapsed time: 96 LinkedList Insert elapsed time: 1684 ArrayList Query consumption time: 8 LinkedList Query consumption time: It's been a long time, but I haven't finished it
conclusion
Although the bottom layer of ArrayList is array and the bottom layer of LinkedList is linked list, the insertion operation of ArrayList is indeed more efficient than that of LinkedList
Because the bottom layer of ArrayList uses elementdata = arrays copyOf(elementData, newCapacity); This is a native method, so it is more efficient
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
When the execution times were modified, the previous test was one million times, and now it is modified to 10000 times
ArrayList Insert elapsed time: 3 LinkedList Insert elapsed time: 2 ArrayList Query consumption time: 1 LinkedList Query consumption time: 48
It can be seen that when the execution times are small, the difference between the two insertion operations is not obvious, but the query operation is still faster in ArrayList
When the execution times are large, the insertion efficiency of ArrayList is higher than that of LinkedList
summary
ArrayList bottom layer is implemented by array, and LinkedList bottom layer is implemented by linked list
The query operation of ArrayList is faster than that of LinkedList
Theoretically, the insertion operation of ArrayList is slower than that of LinkedList
In fact: the insertion operation of ArrayList is faster than that of LinkedList
Because the bottom layer of ArrayList uses elementdata = arrays copyOf(elementData, newCapacity); This is a native method, so it is more efficient