List

ArrayList和LinkedList本质上的区别是数组和链表之间的增删改查的区别，ArrayList多一个扩容机制而已

ArrayList

底层是数组

image-20240115100728681

add()

先判断是否需要扩容

再插入

image-20240115100830425

grow()

1.5倍扩容，如果初始为0，那么扩容到1；如果初始为1，那么扩容到2

new一个新的数组，Arrays.copyof() 将旧的数组copy过去

image-20240115101353211

remove()

检查位置是否合法，然后删除，需要调用native方法移动数组元素

image-20240115102204254

get()

根据下标直接返回元素

image-20240115103317507

LinkedList

底层是双向链表，一头头节点，一个尾节点

image-20240115102442807

image-20240115102719636

add()

尾插法插入新的节点

image-20240115102842291

remove()

拿到待删除节点的前后节点，进行双向链表那样的删除

image-20240115102922252

get()

会用二分法先优化一下，索引位置和链表长度/2先比对一下，然后在左半边遍历还是右半边遍历

image-20240115103138904