这里写目录标题
ArrayList的底层原码：
研究思路：
1.研究继承关系
2.研究属性
3.理解创建集合的过程 – 构造方法的底层原理
4.研究添加元素的过程
场景：
public static void main(String[] args) {
//ArrayList<String> list = new ArrayList<>();
ArrayList<String> list = new ArrayList<>(10000);
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
}
1.研究继承关系
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//外部操作数（记录添加和删除的次数）
protected transient int modCount = 0;//4
}
2.研究属性
public class ArrayList<E> extends AbstractList<E> implements List<E>{
//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//空内容的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空内容的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数据容器最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//数据容器 - [“aaa”,"bbb","ccc","ddd",null,null,null,null,null,null]
transient Object[] elementData;//new Object[10];
//元素个数
private int size;//4
}
3.理解创建集合的过程 – 构造方法的底层原理
//无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有参构造
//initialCapacity - 10000
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);
}
}
4.研究添加元素的过程
//e - "ddd"
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//minCapacity - 11
private void ensureCapacityInternal(int minCapacity) {
//使用无参构造创建ArrayList，第一次添加元素时进入的判断
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//minCapacity = Math.max(10, 1);
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//minCapacity - 11
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 有溢出意识的代码（准备扩容的长度必须大于数据容器的长度）
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//minCapacity - 11
private void grow(int minCapacity) {
// oldCapacity - 10
int oldCapacity = elementData.length;
// newCapacity - 15
int newCapacity = oldCapacity + (oldCapacity >> 1);//ArrayList的扩容机制（1.5倍）
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
5. ArrayList分析的总代码
public class ArrayList<E> extends AbstractList<E> implements List<E>{
//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//空内容的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空内容的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数据容器最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//数据容器 - [“aaa”,"bbb","ccc","ddd",null,null,null,null,null,null]
transient Object[] elementData;//new Object[10];
//元素个数
private int size;//4
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//initialCapacity - 10000
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);
}
}
//e - "ddd"
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//minCapacity - 11
private void ensureCapacityInternal(int minCapacity) {
//使用无参构造创建ArrayList，第一次添加元素时进入的判断
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//minCapacity = Math.max(10, 1);
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//minCapacity - 11
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 有溢出意识的代码（准备扩容的长度必须大于数据容器的长度）
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//minCapacity - 11
private void grow(int minCapacity) {
// oldCapacity - 10
int oldCapacity = elementData.length;
// newCapacity - 15
int newCapacity = oldCapacity + (oldCapacity >> 1);//ArrayList的扩容机制（1.5倍）
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}
6.深究
1.研究删除集合的过程
2.研究遍历集合的过程
7.面试题
1.如何减少集合的伸缩性及其目的是什么？
根据需求判断元素大概的长度，在创建集合时指定长度，减少扩容次数，提高效率 （eg：ArrayList的有参构造）
ArrayList默认初始化容量是多少？
10
ArrayList最大容量是多少？
Integer.MAX_VALUE-8
ArrayList最大容量为什么是Integer.MAX_VALUE-8？
减8是为了腾出空间存放数组的头部信息。
ArrayList扩容机制是什么？
扩容后的长度是原来长度的1.5倍。
LinkedList的底层原码：
研究思路：
1.研究继承关系
2.研究属性
3.理解创建集合的过程 – 构造方法的底层原理
4.研究添加元素的过程
场景：
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
}
}
1.研究继承关系
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//外部操作数（记录添加和删除的次数）
protected transient int modCount = 0;//0
}
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
}
2.研究属性
//元素个数
transient int size = 0;//0
//首节点
transient Node<E> first;//null
//尾节点
transient Node<E> last;//null
//节点类
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;
}
}
3.理解创建集合的过程 – 构造方法的底层原理
public LinkedList() {
}
4.研究添加元素的过程
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
5. LinkedList分析的总代码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>{
//元素个数
transient int size = 0;//0
//首节点
transient Node<E> first;//null
//尾节点
transient Node<E> last;//null
public LinkedList() {
}
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {//构成双向链表
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//节点类
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;
}
}
}
6.深究
1.研究删除集合的过程
2.研究遍历集合的过程
7.面试题
LinkedList底层数据结构是什么？
双向链表
ArrayList 和 LinkedList的效率区别：
ArrayList底层：一维数组
LinkedList底层：双向链表
添加数据 – ArrayList扩容的情况：LinkedList快
添加数据 – ArrayList不扩容的情况：ArrayList快
查询数据：ArrayList快
删除数据：LinkedList快
修改数据：ArrayList快
补充：平时我们一般使用ArrayList，是因为众多业务中查询功能使用最为频繁，而ArrayList查询功能比LinkedList更快，所以我们选择使用ArrayList会更多。
LinkedList如何实现删除？
1.通过下标找到要删除的节点
2.把要删除的节点的下一个节点地址赋值给上一个节点的next
3.把要删除的节点的上一个节点地址赋值给下一个节点的prev