- ArrayList is implemented based on arrays, LinkedList is implemented based on linked lists, ArrayList is more efficient than LinkedList when accessing lists randomly, and so on
- Usage scenarios: ArrayList and LinkedList LinkedList is more efficient than ArrayList in adding and deleting elements, and ArrayList is more efficient than LinkedList in traversing
The Detail:
- An implementation class for ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code- ArrayList implements the List interface, inherits AbstractList abstract class, implements arrays at the bottom, and implements self-increasing array sizes.
- ArrayList also implements the Cloneable and Serializable interfaces, so it can implement cloning and serialization.
- ArrayList also implements the RandomAccess interface, a flag interface that says “any List class that implements this interface can achieve fast RandomAccess.”
When a new element is added to an ArrayList, it calculates the size of the element and dynamically expands it if it exceeds its existing size. Expanding an array causes a memory copy of the entire array. When the ArrayList no-argument constructor initializes, the default size is an empty array, not the usual 10, which is the value of the array expanded when we first add it.
- Adding an element: Adding an element to any position causes all elements after that position to be rearranged. Adding an element to the end of the array does not duplicate sorting without expansion. So an ArrayList doesn’t have to be slow with lots of new elements; If we know the size of the data stored at initialization, specify the size of the array when we initialize an ArrayList, and add elements only at the end of the array when we add elements, then an ArrayList performs better than other lists with a large number of new elements, rather than worse.
- Delete elements: An ArrayList reassembles the array after each valid delete operation, and the more advanced the deleted elements, the more expensive the array reassembles.
- Traversal: Since ArrayList is implemented based on arrays, it is very fast to get elements.
- LinkedList
LinkedList is implemented based on a two-way LinkedList data structure. This is a bidirectional list structure in which each node can be traced back and forth.
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
Copy the code- Class LinkedList implements List interface, Deque interface, and AbstractSequentialList abstract class. -LinkedList implements both List type and Queue type.
- LinkedList also implements Cloneable and Serializable interfaces and, like ArrayList, can be cloned and serialized.
Because the memory address of LinkedList storing data is discontinuous, but the discontinuous address is located by pointer, therefore, LinkedList does not support random fast access, and LinkedList cannot implement RandomAccess interface.
- Node query: linked list query of a node is relatively slow, need to search by cycle; A simple dichotomy is used
- New element: The add (Ee) method adds the added element to the end of the queue (the last element is replaced by a temporary variable, a new Node object is generated, and the last reference points to the new Node object, with the previous last pointer pointing to the new Node object). If we are adding an element in the middle of any two elements, the addition operation only changes the pointer to the element before and after, which points to the added element, so the LinkedList has a significant performance advantage over the ArrayList addition operation
- Delete element: First loop to find the element to delete. If the element to delete is in the first half of the List, look back. If it’s in the second half, look from back to front.
- Iterating through elements: In LinkedList loop, we can iterate through the loop using the iterator method, fetching our elements directly instead of going through the loop to look up the List.
Because LinkedList is implemented based on linked lists, each for loop will traverse half of the List, so the efficiency of traversal is seriously affected. ArrayList is implemented based on arrays and implements the RandomAccess interface flag, which means that ArrayList can achieve fast RandomAccess, so the for loop is very efficient. LinkedList iteration loop traversal is as good and not too bad as ArrayList iteration loop traversal, so avoid using for loop traversal when traversing LinkedList.
Source: mp.weixin.qq.com/s/IuXnprZdz…