Which one should I use for the respective usage scenarios of LinkedList and ArrayList?

Click above ☝Java programming technology paradise, easy to follow! Timely access to interesting technical articles

In a word, in most cases, using ArrayList will be better.

has its own advantages and disadvantages in terms of time-consuming. ArrayList has a slight advantage List is just an interface, but LinkedList and ArrayList are different implementations of List. The LinkedList model is a doubly linked list, while ArrayList is a dynamic array

. First compare the algorithm complexity of common operations

LinkedList

get(int index): O(n) add(E element): O(1) add(int index, E element ): O(n) remove(int index): O(n) Iterator.remove(): O(1) <--- The main advantages of LinkedList ListIterator.add(E element) is O(1) <--->

ArrayList

get(int index): O(1) <--- The main advantages of ArrayList add(E element): Basically O(1), because of dynamic expansion, the worst case is O(n) add (int index, E element): Basically O(n-index), because of dynamic expansion, the worst case is O(n) remove(int index): O(n-index) (for example, remove the last one The element is O(1)) Iterator.remove(): O(n-index) ListIterator.add(E element): O(n-index)

LinkedList, because the essence is a linked list, so insert and remove operations through Iterator The time-consuming is a constant, but if you want to get the element at a certain position, you need to traverse the pointer. Therefore, the time consumption of the get operation is related to the length of the List.

For ArrayList, thanks to the characteristics of fast random access, the time consuming to obtain elements at any position is constant. However, if it is an add or remove operation, there are two cases. If the add is done at the end, that is, the add method is executed (without index parameter). At this time, there is no need to move other elements. The time-consuming is O(1), but If you do not add at the tail, that is, execute add(int index, E element), at this time, while inserting a new element, you must move all the elements behind the position to make room for the new element. At this time, the time-consuming is O(n-index). In addition, when the length of the List exceeds the initial capacity, a new array will be automatically generated (the length is 1.5 times the previous), and the old array will be moved to the new array. In this case, the time-consuming is O( n).

In short, get operation, ArrayList is faster. The add operation, the two are almost . (Unless you want to insert a node in the middle of the List and maintain an Iterator to point to a specified position, the linkedList can be faster at this time, but we often insert nodes directly at the end, and there are not many cases in this special case)

In terms of space occupancy, ArrayList is a win. Look at the memory occupancy graphs

. The horizontal axis is the length of the list, and the vertical axis is the memory occupancy value. The two blue lines are LinkedList, and the two red lines are ArrayList

. You can see that LinkThe space occupied by edList is much larger than that of ArrayList. The LinkedList line is steeper. As the length of the List expands, the space occupied is much larger than that of the ArrayList of the same length.

Note: Since mid JDK6, CompressedOops is enabled by default, so there is no difference between the results under 64-bit and 32-bit. The LinkedList x64 and LinkedList x32 lines are the same.

Also, if the list is large, remember that the memory usage is also different. Each element of LinkedList has more overhead because pointers to the next and previous elements are also stored. ArrayList does not have this overhead. However, the ArrayList occupies as much memory as the memory allocated for that capacity, regardless of whether elements are actually added. The default initial capacity of

ArrayList is very small (10 in Java 1.4-1.8). But because the underlying implementation is an array, if you add many elements, you must adjust the size of the array. In order to avoid the high cost of resizing when you are sure to add many elements, construct an ArrayList with a higher initial capacity.