The difference between ArrayList and LinkedList

ArrayList and LinkedList It's all done List Interface , But they have the following differences ：

Underlying data structure ：ArrayList Is based on Indexes (index) Data structure of , At the bottom of it is an array , It can take O(1) Time complexity for random access . Corresponding to this ,LinkedList In order to List of elements Store its data in the form of , Each element is linked to its previous and next elements , under these circumstances , The time complexity of finding an element is O(n).
Action on element ： be relative to ArrayList,LinkedList Insertion , add to , Faster delete operations , Because when an element is added anywhere in the collection , There is no need to recalculate the size or update the index like an array ( Except inserting at the end of the array ), There is no need to reload all the data into a new array when the array is full , This is also ArrayList Worst case scenario , The time complexity of doing this is O(n), and LinkedList The time complexity of insertion or deletion in is only O(1). Delete something like this . Corresponding ,ArrayList The search operation of is better than LinkedList.
Memory footprint ：LinkedList Than ArrayList More memory , because ArrayList The location of each index is the actual data , and LinkedList The actual data and the positions of the front and rear nodes are stored in each node in the ( One LinkedList The instance stores two values ：Node<E> first and Node<E> last It represents the starting and ending nodes of the linked list respectively , Every Node The instance stores three values ：E item;Node next;Node pre).

What scenario is more suitable for LinkedList, without ArrayList

1. Your app doesn't randomly access data . Because if you need LinkedList No n When it's an element , You need to count from the first element to the n Data , Then read the data .
2. Your app inserts and deletes more elements , Less read data . Because inserting and deleting elements does not involve rearranging data , So it's better than ArrayList Be quick

ArrayList Common methods
1）add(element) Add an element ,
2）add(index , element) stay index Add an element to the position index The current element will move back
3）size() Sequence table length
4） set(index ,element) take index Modify the position element
5）get(index) obtain index The element of location
6）remove(index) Delete index The element of location
7）contains(element) Whether to include this element
8）isEmpry() Judge whether the sequence table is empty

LinkedList Common methods
1）add(element ) Add an element
2）addFirst(element) Insert an element in the header
3）addLast(element) Insert an element at the end
4）get(index) obtain index The element of location
5）set(index,element) Set up index The location element is element
6）indexOf(element) Return the subscript of the element , Go back if you can't find it -1
7）contains (element) Determine if there is this element

ArrayList Capacity expansion mechanism of
Generally speaking, it is to copy the array to another array with larger memory space
If you just create an object without adding elements , At this time, the size is 0, If we don't specify the size , The default size is 10
Time for expansion
If the current array size is larger than the initial capacity of the array （ For example, the initial capacity is 10, When the 11 Element time ） It's going to expand , The new capacity is... Of the old capacity 1.5 times
Expansion way
Add capacity , A copy of the original array will be created with the new capacity , Copy the data of the original array , The original array will be discarded , Will be GC Recycling