一、ArrayList是什么？

ArrayList内部是动态数组的结构，具备数组的特点
优点：

1）查找速度快
2）随机访问性强
3）尾插速度快，时间复杂为O（N）

缺点：

1）头插、中间插入和删除操作时需要搬运数据，时间复杂度是O(N)
2) 数组需要连续的内存空间，对空间要求高
3) 数组是固定大小的，但是ArrayList 插入元素会触发扩容机制

常用的方法：
1）add( element) 添加一个元素，
2）add( index , element) 在index位置添加一个元素 index当前元素就会往后挪
3）size() 顺序表长度
4） set (index ,element) 将index位置元素进行修改
5）get( index) 获取index位置的元素
6）remove(index) 删除index 位置的元素
7）contains (element) 是否包含该元素
8）isEmpry() 判断顺序表是否为空

ArrayList 的扩容机制

总体来说就是把数组复制到另外一个内存空间更大的数组中
若只是创建了对象没有添加元素，此时的大小为0，如果我们没有指定大小，此时默认大小为10
扩容时机
如果当前数组大小大于数组初识容量（比如初识容量为10，当添加第11个元素时）就会进行扩容，新的容量为旧的容量的1.5倍
扩容方式
扩容时，会以新的容量创建一个原数组的拷贝，将原数组的数据拷贝过来，原数组就会被抛弃，会被GC回收

二、LinkedList

LinkedList 底层通过双向链表实现 LinkedList 通过first 和 last 引用分别指向链表的第一个和最后一个元素

双向链表的优点：

1.内存利用率高，不会浪费内存
2.大小不固定，拓展灵活
3.插入、删除头尾速度快，时间复杂度为O（1）

缺点：

在Java中LinkedList 中间位置插入元素，时间复杂度为O（N）,且不能随机查找，必须遍历链表

常用的方法
1）add( element ) 添加一个元素
2）addFirst (element) 头插一个元素
3）addLast (element) 尾插一个元素
4）get( index) 获取index 位置的元素
5）set(index element) 设置index位置元素为 element
6）indexOf(element) 返回该元素所在下标，没找到就返回-1
7）contains (element) 判断是否有该元素

LinkedList 和链表的区别

平时我们说的链表是单链表而LinkedList 是具体的，特指Java标准库的某个集合类
举一个简单的例子：
给定一个单向链表，删除最后一个节点，时间复杂度是O（N）
给定一个LinkedList,删除最后一个节点，时间复杂度为O（1）

三、ArrayList和LinkedList区别

这里我们从二者增删改查的方面进行对比

增加元素:

1.头插/尾插
ArrayList 头插要进行大量的挪元素时间复杂度为O（N）而尾插根据下标就能直接插入O（1）
LinkedList 因为是双向链表，有节点进行记录所以时间复杂度为O（1）
2.中间位置插入
ArrayList 在中间位置插入元素，需要挪元素，时间复杂度为O（N）
LinkedList 在中间位置插入元素，需要遍历链表去找位置，时间复杂度也为O（N）

总结：增加元素时，LinkedList 表现更好，因为ArrayList 插入元素需要进行挪元素，而LinkedList 只需要修改地址值，而且头插和尾插速度快，所以LinkedList 表现更佳