Graphic and text details comparing ArrayList and LinkedList in java

This article mainly compares ArrayList and LinkedList in Java through examples. Friends in need can refer to it

ArrayList and LinkedList are both common implementation methods of the Collection interface, and they use different storage Strategies are used to adapt to the needs of different situations.

Implementation method

ArrayList internally uses a collection to store data

The only thing that needs to be noted is that The processing logic for capacity exceeding the threshold. The default capacity of the array is 10, and the maximum capacity is Integer.Max_Value. If the maximum capacity is exceeded, a memory overflow exception will be thrown.

The expansion mechanism is shown below

The expanded capacity is 1.5 times the original capacity

Implementation method of LinkedList

The internal class Node of a doubly linked list is used to store data. Due to the use of a doubly linked list, LinkedList can also be used as a stack and queue, but the efficiency is relatively low. Java provides a high-efficiency implementation of ArrayDeqeue.

Performance comparison

In terms of tail insertion efficiency, the difference between the two will not be too big, but LinkedList needs to maintain a doubly linked list Relationship, all storage efficiency will be slightly inferior to ArrayList

ArrayList’s time is mainly spent on capacity expansion and data migration. If we initialize the capacity at one time, it should be okay There is room for improvement. Let’s compare again. There is a terrifying 50% room for improvement.

The advantage of Linked is the efficiency of head insertion. You only need to modify the head element. Pointers can do it, but the array still needs to move subsequent data, and the efficiency is far lower than that of LinkedList

For get and set operations, binary search is performed inside the linked list. Arrays can directly access elements through subscripts, so the efficiency is higher than LinkedList

Based on the above comparison, we can basically determine
If it is just stored In the case of simple iteration of data, we generally use collections for the highest efficiency.

If it involves frequent modification of elements, LinkedList

The above is the detailed content of Graphic and text details comparing ArrayList and LinkedList in java. For more information, please follow other related articles on the PHP Chinese website!