Java数据结构的继承关系

1. ArrayList

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

1）查找速度快
2）ArrayList可随着元素的增长而自动扩容，正常扩容的话，每次扩容到原来的1.5倍
3）尾插速度快，时间复杂为O（N）

缺点：

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

1.1 常用方法

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() 判断顺序表是否为空

1.2 源码相关定义:

// 默认的容量大小（常量）
private static final int DEFAULT_CAPACITY = 10;

// 定义的空数组（final修饰，大小固定为0）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 定义的默认空容量的数组（final修饰，大小固定为0）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 定义的不可被序列化的数组，实际存储元素的数组
transient Object[] elementData; 

// 数组中元素的个数
private int size;

1.3 ArrayList扩容机制

扩容可分为两种情况：

　第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同:

　　　　1.无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容。

　　　　2.传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

　　　　3.传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

　　第二种情况，当ArrayList的容量大于0，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

2. LinkedList

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

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

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

2.1 常用的方法

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) 判断是否有该元素