Java集合：List
一、集合概述
在Java中，我们能想到的List接口下的类有那么两个半吧：①ArrayList，②LinkedList，③Vector。
ArrayList：
- 底层是数组
- 初始容量为10，每次扩容为1.5倍
- 组的增删改底层由System和Arrays的数组赋值拷贝方法支持
LinkedList：
- 底层是双向链表
插入/删除操作适合LinkedList，查询操作适合ArrayList，Vector就是线程安全的ArrayList。
二、ArrayList
这里就直接上源码吧，先来看看成员变量和构造方法：
// 数组默认容量private static final int DEFAULT_CAPACITY = 10;// 空数组private static final Object[] EMPTY_ELEMENTDATA = { };// 默认大小的空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };// 实际存放数据的数组transient Object[] elementData;// 记录数组的大小private int size;// 有指定容量构造public ArrayList(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);}}// 空参构造public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
从上面我们可以看出有三种情况：
- 使用空参构造器，我们会收获一个默认容量大小的空数组，也就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- 使用参数为容量大小的构造器，如果initialCapacity为0，则赋值EMPTY_ELEMENTDATA；如果initialCapacity不为0，则构造一个initialCapacity大小的数组
那EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA有啥不一样呢？后面会有解析：
add方法：
public boolean add(E e) {// 确认数组是否需要扩容ensureCapacityInternal(size + 1);// 添加元素即可elementData[size++] = e;return true;}
扩容方法：
private void ensureCapacityInternal(int minCapacity) {// 如果是使用空参构造器构建的集合对象// 前面的疑问就在这里解决if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 重新计算minCapacityminCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}//private void ensureExplicitCapacity(int minCapacity) {// 操作次数+1modCount++;// 如果minCapacity >elementData.length，执行扩容操作if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// 获取旧数组的长度int oldCapacity = elementData.length;// 计算新数组的长度，长度 = 1.5*旧数组的长度，也就是1.5倍扩容int newCapacity = oldCapacity + (oldCapacity >> 1);//if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8// 计算出来的新数组长度已经 大于 最大数组大小if (newCapacity - MAX_ARRAY_SIZE > 0)// 重新计算新数组长度newCapacity = hugeCapacity(minCapacity);// 复制数组到新数组elementData = Arrays.copyOf(elementData, newCapacity);}// 重新计算新数组长度private static int hugeCapacity(int minCapacity) {if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
get方法： 正常的数组访问方式
public E get(int index) {rangeCheck(index);return elementData(index);}E elementData(int index) {return (E) elementData[index];}
remove方法:
public E remove(int index) {rangeCheck(index);modCount++;// 获取元素E oldValue = elementData(index);// 计算位移的位数int numMoved = size - index - 1;if (numMoved > 0)// 复制数组System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null;return oldValue;}
例如：n数组，下标0~n-1，我们要删除第k位的数值，我们就需要将0 ~ k-1位以及k+1 ~ n-1的数组复制到新数组。
三、LinkedList
LinkedList底层是双向链表，那我们脑普一下就该知道，重点在Node节点上，其余的按照链表的方式来。
Node节点
private static class Node<E> {// 保存的数据E item;// 保存的后继节点Node<E> next;// 保存的前驱节点Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
成员变量：
// 记录队列的大小transient int size = 0;// 指向队列的头结点transient Node<E> first;// 指向队列的尾节点transient Node<E> last;
双向链表的基本操作，不会推荐去手写下链表即可。
四、Vector
与ArrayList的不同在于每个操作方法上都添加了synchronized关键字，也就是加了锁，保证线程安全，不过也大大降低了性能。
朱雀
比眉伴天荒
还没有评论，来说两句吧...