Java 从源码弄懂集合(超详细)-List篇
前言
集合是我们在开发中经常会使用的工具，不同的集合实现类有着不同的特性，而很多开发者却一个ArrayList从头用到尾，这种做法是非常不可取的，所以我决定写一篇博客全面记录集合的各个实现类已经用法
一、概述
以下是集合的框架图
由上图可知，我们的集合的顶层接口是Iterable被Collectionb继承，而List，Queue，Set则是Collection接口的三个最主要的子接口。
二、Iterable
Iterable是一个迭代器接口，它的作用是方便我们对集合进行遍历
源码如下：
import java.util.function.Consumer;
public interface Iterable<T> {
//iterator()方法
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}可以看出来，Iterable支持lambda函数接口，还需要注意的是它的forEach方法，我们可以看到它的参数是个Consumer类型的，所以在forEach内部我们常常用lambda特性来创建匿名接口实现对象
//Hero的属性：name、hp，仅包含get和set方法
List<Hero> list = new ArrayList<>();
list.add(new Hero("xie",100));
list.add(new Hero("li",100));
list.add(new Hero("guo",100));
//forEach遍历方式
//示例1和2代码本质是一样的，但是1更加简洁
//示例1
list.forEach((item) ->{
System.out.println(item.getName());
});
//示例2
list.forEach(new Consumer<Hero>() {
@Override
public void accept(Hero item) {
System.out.println(item.getName());
}
});
//迭代器遍历方式
//集合的实现类都重写了iterator方法，我们可以执行此方法返回一个迭代器
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Hero next = (Hero) iterator.next();
System.out.println(next.getName());
}由上面的代码可以看出，Iterator对象两个最常用的方法是hasNext()和next(),一个是用来判断容器中是否还有元素，一个是返回当前元素的下一个元素
三、Collection
该接口的源码就不给大家展示了，我们只需要知道该接口声明的常用方法即可
1. 增
boolean add(E e);
boolean addAll(Collection<? extends E> c);
2. 删
boolean remove(Object o);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter)
3. 子集
boolean contains(Object o);
boolean containsAll(Collection<?> c);
4. 交集
boolean retainAll(Collection<?> c);
5. 转成数组
<t> T[] toArray(T[] a);
Object[] toArray();
这两种toArray方法的返回类型是不一样的！！！</t>
6. 其它常用api
void clear();
int size();
boolean isEmpty();
四、ArrayList
ArrayList是List接口的实现类，它的特点是有序，所以它能通过索引来进行增删改查。
- 增：add(E e) addAll(Collection<? extends E> c);
- 删：remove(int index) remove(E obj) removeAll(Collection col);
- 改：set(int index, E e);
- 查：get(int index);
- 插：add(int index, E e) addAll(int index, Collection<? extends E> c);
- 长度：size();
ArrayList最大的特点就是会自动扩充，那它扩充的机制到底是怎样的呢？我们来分析源码
ArrayList基本属性和构造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//序列化的ID
private static final long serialVersionUID = 8683452581122892189L;
//初始化大小为10
private static final int DEFAULT_CAPACITY = 10;
//当size为0时，赋值给elementData的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//调用无参构造函数时用到的空数组，跟上面那个空数组的使用场景不同而已
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正用来存储数据的数组
transient Object[] elementData; // non-private to simplify nested class access
//存放元素的个数
private int size;
//初始化指定大小容量的数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//在该场景下elementData指向EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//无参构造函数
public ArrayList() {
//该场景下elementData指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//传入一个集合并将其初始化为ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
//当c不为空集合时，将elementData的类型强制转为Object[]
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
//将elementData的长度变为size
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//确保elementData容量够用，不够则扩容
public void ensureCapacity(int minCapacity) {
//minCapacity>elementData长度且elementData不指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
//或minCapacity>默认值(10)时扩容
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
}ArrayList添加元素
//向数组尾部添加元素
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
//插入元素
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}ArrayList扩容
//返回一个适合的大小给数组
private static int calculateCapacity(Object[] elementData, int minCapacity) {
/**
当调用无参构造器 elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时候
会返回默认大小和minCapacity的最大值
**/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//将newCapacity扩大成oldCapacity的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//若此时newCapacity还小于minCapacity则直接将minCapacity赋值给newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若此时newCapacity>MAX_ARRAY_SIZE,则调用hugeCapacity(minCapacity)
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将原数组的内容赋值给扩容后的新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}五、LinkedList
LinkedList是一个非常强大的实现类，它既实现了List的接口，又实现了DeQue(双端队列)的接口。
LinkedList结构
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
......
}可以看出LinkedList有一个头指针first和一个尾指针last，也就是我们数据结构里面的双端队列的逻辑结构。在Java中，传统的队列Queue 添加元素是在队尾添加，删除或取出元素是在队头进行操作，而LinkedList作为双端队列既可以在队头进行添加或删除，也可以在队尾进行添加和删除
Node的结构(LinkedList内部类)
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;
}
}可以看出Node对象具有next和prev两个指针，一个指向前，一个指向后，所以由Node结点组成的LinkedList不但是一个双端队列，还是个双链表
常用api
LinkedList<Hero> list = new LinkedList<>();、
//往队尾添加元素
list.offer(new Hero("1号",1));
list.offer(new Hero("2号",1));
list.offer(new Hero("3号",1));
//往队首添加元素
list.offerFirst(new Hero("4号",1));
list.offerFirst(new Hero("5号",1));
list.offerFirst(new Hero("6号",1));
//取出队尾元素:3号
System.out.println(list.peekLast().getName());
//取出队首元素:6号
System.out.println(list.peekFirst().getName());
//删除队首
System.out.println("删除队首：" + list.pollFirst().getName());
//删除队尾元素
System.out.println("删除队尾：" + list.poll().getName());以上是LinkedList作为DeQue实现类具有的api，除此之外LinkedList还实现了List接口中的方法，具体可以参考上面的ArrayList常用api，在此不再赘述
六、总结
在上面我们主要谈到了Iterator、Collection、以及List的两个实现类ArrayList和LinkedList，下面我们就来总结一下它们各自的功能以及特点吧
1. Iterator：迭代器对象，用来遍历集合，next()用来得到下一个元素，hasNext()判断集合是否遍历结束。
注意点：一个Iterator对象只能遍历一遍，若要遍历第二遍则需要重新创建该集合的Iterator
2. List：一个有序的集合接口，它可以通过索引来进行插入，删除，访问
3. ArrayList：它是List的实现类，开发中我们通常使用它来代替数组，需要注意的是它的底层是Object数组，默认大小是10，当添加元素的时候会判断它的容量是否够用，若不够的话则扩容为1.5倍大小，若还不够，则将其扩容为需要的大小
4. LinkedList：它实现了List接口和DeQue接口，具有它们两者的特性，除此之外它的结构是一个双端队列，可以从队头/队尾添加、删除、访问元素
ArrayList和LinkedList区别：
它们的区别由它们底层的数据结构所决定，由于ArayList底层是object数组，所以它具有随机访问特性，更适合查询业务比较多的场景，而LinkedList本质上是一个双链表，它更适合插入删除比较多的业务场景。
投递百度等公司6个岗位
