1 集合框架介绍
- 所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口或实现类。
- 集合接口：6个接口（短虚线表示），表示不同集合类型，是集合框架的基础。
- 抽象类：5个抽象类（长虚线表示），对集合接口的部分实现。可扩展为自定义集合类。
- 实现类：8个实现类（实线表示），对接口的具体实现。
- Collection 接口是一组允许重复的对象。
- Set 接口继承 Collection，集合元素不重复。
- List 接口继承 Collection，允许重复，维护元素插入顺序。
- Map接口是键－值对象，与Collection接口没有什么关系。
- Set、List和Map可以看做集合的三大类：
- List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。
- Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）。
Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。
2 纯手写List框架
List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。
3 ArrayList实现
3.1 Arraylist底层基于数组实现
3.2 Arraylist底层默认数组初始化大小为10个object数组
3.3 添加元素后大于当前数组的长度，则进行扩容,将数组的长度增加原来数组的一半。
- add方法
- 判断实际存放的容量是否大于elementData
- 判断是否需要扩容
- 扩容实现
3.4 手写Arraylist底层框架
3.4.1 自定List接口
public interface ExtList<E> {
int size();
boolean add(E e);
void add(int index, E e);
E get(int index);
E remove(int index);
boolean remove(E e);
}
3.4.2 实现List接口
public class ExtArrayList<E> implements ExtList<E> {
private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
/**
* 实际容量大小
*/
private int size;
public ExtArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ExtArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
@Override
public boolean add(E e) {
// 1.判断实际存放的容量是否大于elementData
ensureCapacityInternal(size + 1);
// 2.使用下标进行赋值
elementData[size++] = e;
return true;
}
@Override
public void add(int index, E e) {
// 1.判断实际存放的容量是否大于elementData
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 2.使用下标进行赋值
elementData[index] = e;
size++;
}
/**
* 判断实际存放的容量是否大于elementData
*
* @param minCapacity 最小为size+1
* @return void
* @throws
* @author zhouxinlei
* @date 2019-12-24 14:43:09
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
private void grow(int minCapacity) {
//原数组容量大小
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//最小扩容容量
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
} else if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
E elementData(int index) {
return (E) elementData[index];
}
@Override
public E get(int index) {
//判断数组是否越界
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
elementData[--size] = null;
}
@Override
public E remove(int index) {
E e = get(index);
int numMoved = elementData.length - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return e;
}
@Override
public boolean remove(Object object) {
if (object == null) {
for (int index = 0; index < elementData.length; index++) {
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
} else {
for (int index = 0; index < elementData.length; index++) {
if (object.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
@Override
public int size() {
return this.size;
}
}
3 LinkList实现
LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比ArrayList差。
3.1 LinkedList数据结构原理
LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：
既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：
3.2 数组和链表结构对比
- 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组。
- 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储 数据元素 的 数据域，另一个是存储下一个结点地址的 指针。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
3.3 内存存储区别
- 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
- 链表从堆中分配空间, 自由度大但申请管理比较麻烦。
3.4 逻辑结构区别
- 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
- 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
3.5 总结
- 存取方式上，数组可以顺序存取或者随机存取，而链表只能顺序存取；
- 存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；
- 存储空间上，链表由于带有指针域，存储密度不如数组大；
- 按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；
- 按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；
- 插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；
- 空间分配方面： 数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败； 链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；
3.6 手写LinkList代码实现
