Difference between ArrayList and LinkedList

ArrayList

Extension mechanism

1. ArrayList() will use a zero-length array

2. ArrayList(int initialCapacity) will use an array with the specified capacity

3. public ArrayList(Collectionc) will use the size of c as the array capacity

4. add(Object o) expands to 10 for the first time, and then expands to 1.5 times the last time

5. addAll(Collection c) When there are no elements, the expansion is Math.max(10, the actual number of elements), and if there are elements, the expansion is Math.max (1.5 times the original capacity, the actual number of elements)

Features

1. Array-based, requires contiguous memory

2. Fast random access (access according to the specified subscript)

3. Tail insertion, deletion performance is OK, other parts insertion and deletion will move data, so the performance will be low

4. Can use cpu cache, locality principle

LinkedList

Features

1. Based on doubly linked list, no need for contiguous memory (each bit has a pointer to the next)

2. Random access is slow (traverse along the linked list)

3. High performance of head and tail insertion and deletion

4. Occupies a lot of memory