List源码解析

ArrayList

ArrayList的subList方法会返回一个list视图,对这个SubList的修改都会映射到原来的list

而Arrays.asList返回的arrays包下的ArrayList,这个类并没有重写add,remove等方法,所以修改时会抛出异常

架构

202002191425

解析

一共有三种方式可以初始化ArrayList

public ArrayList(Collection<? extends E> c) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {        // 直接将传入的集合转成数组复制给内部数组        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        this.elementData = {};    }}public ArrayList() {    this.elementData = {};}public ArrayList(int initialCapacity) {    if (initialCapacity > 0) {        this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {        this.elementData = {};    } else {        throw new IllegalArgumentException("Illegal Capacity: "+                                           initialCapacity);    }}

添加元素时:

// 这个版本是基于JDK13的private void add(E e, Object[] elementData, int s) {    // 当发现现在list的size跟数组容量一样大时,则进行扩容    if (s == elementData.length)        // 这里扩容完,会产生一个新数组,我们要将新数组保存        elementData = grow(size+1);    //添加index:size    elementData[s] = e;    size = s + 1;}// 扩容核心代码private Object[] grow(int minCapacity) {    int oldCapacity = elementData.length;    // 只有数组不为空时,才进行扩容,否则直接创建    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        // 计算数组的新容量        int newCapacity = ArraysSupport.newLength(oldCapacity,                minCapacity - oldCapacity, /* minimum growth */                oldCapacity >> 1           /* preferred growth */);        // 复制老数组到新数组        return elementData = Arrays.copyOf(elementData, newCapacity);    } else {        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];    }}// 计算容量的方法public static int newLength(int oldLength, int minGrowth, int prefGrowth) {    // 判断list的size与elementData的差值如果大于elementData长度的一半    // 新数组长度就等于老数组长度加上list的size与elementData的差值    // 否则新数组的长度就等于老数组的1.5倍    int newLength = Math.max(minGrowth, prefGrowth) + oldLength;    if (newLength - MAX_ARRAY_LENGTH <= 0) { // 数组长度不能大于整数最大值        return newLength;    }    return hugeLength(oldLength, minGrowth);}

所以扩容的本质就是申请一个更大的数组,将旧数组的内容移过去

源码扩容过程值得借鉴的地方

无论是根据Object删除还是index删除,都必须给出被删除元素的index

private void fastRemove(Object[] es, int i) {    modCount++;    final int newSize;    if ((newSize = size - 1) > i)        // 将elementData 下标为i后面的全部元素往前移动一个位        System.arraycopy(es, i + 1, es, i, newSize - i);    // 如果删除的是最后一个元素,置为null就行    es[size = newSize] = null; // 同时记得size-1}

202002191507

迭代器

public boolean hasNext() {    return cursor != size;}
public E next() {    // 有点乐观锁的意思,通过版本号来确定持有的数据是否被修改了    if (modCount != expectedModCount)        throw new ConcurrentModificationException();    // 否则每次根据游标获取元素,获取完游标+1    int i = cursor;    if (i >= size)        throw new NoSuchElementException();    Object[] elementData = ArrayList.this.elementData;    if (i >= elementData.length)        throw new ConcurrentModificationException();    cursor = i + 1;    return (E) elementData[lastRet = i];}
public void remove() {    if (lastRet < 0)        throw new IllegalStateException();   if (modCount != expectedModCount)        throw new ConcurrentModificationException();    // 将当前游标作为下标,删除这个位置的元素    try {        ArrayList.this.remove(lastRet);        // 删除完之后要更新版本号        cursor = lastRet;        lastRet = -1;        expectedModCount = modCount;    } catch (IndexOutOfBoundsException ex) {        throw new ConcurrentModificationException();    }}

线程安全

ArrayList 有线程安全问题的本质,是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时,都没有加锁


问:对 ArrayList 的理解?

答:底层数据结构、对数组的封装、add、remove

问:为什么说扩容会消耗性能

答:扩容底层使用的是 System.arraycopy 方法,会把原数组的数据全部拷贝到新数组上,所以性能消耗比较严重

LinkedList

架构

LinkedList 底层数据结构是一个双向链表

202002191526

解析

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;    }}
void linkLast(E e) {    final Node<E> l = this.last;    final Node<E> newNode = new Node<>(l, e, null);    this.last = newNode;    // 如果尾节点为空,则代表当前链表是空的,直接把插入节点作为头节点    if (l == null)        first = newNode;    else        l.next = newNode; // 否则就将插入节点设置为尾节点,并且把旧尾节点的next指向插入节点    size++;    modCount++;}
private void linkFirst(E e) {    final Node<E> f = this.first;    final Node<E> newNode = new Node<>(null, e, f);    this.first = newNode;    // 如果头节点为空,则代表当前链表是空的,直接把插入节点作为尾节点    if (f == null)        last = newNode;    else        f.prev = newNode; // 否则就将插入节点设置为头节点,并且把旧头节点的prev指向插入节点    size++;    modCount++;}
E unlink(Node<E> x) {    // assert x != null;    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    // 当前删除的是头节点,所以将删除节点的next变为头节点    if (prev == null) {        first = next;    } else {        // 否则设置删除节点的上一个节点的next指向删除节点的next        prev.next = next;        x.prev = null;    }    // 当前删除的是尾节点,所以将删除节点的prev变为尾节点    if (next == null) {        last = prev;    } else {        // 否则设置删除节点的下一个节点的prev指向删除节点的prev        next.prev = prev;        x.next = null;    }        x.item = null;    size--;    modCount++;    return element;}
Node<E> node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) { // 在前半部分,所以从头节点迭代查找        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else { // 在后半部分,所以尾头节点迭代查找        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

迭代器

// 双向迭代器private class ListItr implements ListIterator<E> {    private Node<E> lastReturned;//上一次执行 next() 或者 previos() 方法时的节点位置    private Node<E> next;//下一个节点    private int nextIndex;//下一个节点的位置    …………}
public boolean hasNext() {    return nextIndex < size;}    public E next() {    checkForComodification();    if (!hasNext())        throw new NoSuchElementException();    lastReturned = next;    next = next.next; // next指向当前遍历元素的next    nextIndex++;    return lastReturned.item;}
public boolean hasPrevious() {    return nextIndex > 0;}public E previous() {    checkForComodification();    if (!hasPrevious())        throw new NoSuchElementException();    // 主要是判断next为空的情况下要选择last作为遍历节点,否则选择遍历元素的prev    lastReturned = next = (next == null) ? last : next.prev;    nextIndex--;    return lastReturned.item;}
public void remove() {    checkForComodification();    // lastReturned 是本次迭代需要删除的值,分以下空和非空两种情况:    // lastReturned 为空,说明调用者没有主动执行过 next() 或者 previos(),直接报错    // lastReturned 不为空,是在上次执行 next() 或者 previos()方法时赋的值    if (lastReturned == null)        throw new IllegalStateException();    Node<E> lastNext = lastReturned.next;    //删除当前节点    unlink(lastReturned);    // next == lastReturned 的场景分析:从尾到头递归顺序,并且是第一次迭代,并且要删除最后一个元素的情况下    // 这种情况下,previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等    if (next == lastReturned)        // 这时候 lastReturned 是尾节点,lastNext 是 null,所以 next 也是 null,这样在 previous() 执行时,发现 next 是 null,就会把尾节点赋值给 next        next = lastNext;    else        nextIndex--;    lastReturned = null;    expectedModCount++;}

问:ArrayList 和 LinkedList 有何不同

答:底层数据结构,数组结构导致的读写差异

问: ArrayList 和 LinkedList 应用场景

答:ArrayList 更适合于快速的查找匹配,不适合频繁新增删除,像工作中经常会对元素进行匹配查询的场景比较合适,LinkedList 更适合于经常新增和删除,对查询反而很少的场景

问:ArrayList 和 LinkedList 两者有没有最大容量

答:两个都有最大容量,是int的最大值,原因是ArrayList使用的数组容量不能超过int最大值,LinkedList则是因为size使用int表示的,所以也不能超过int的最大值

问:ArrayList 和 LinkedList 是如何对 null 值进行处理的

答:ArrayList 允许 null 值新增,也允许 null 值删除。删除 null 值时,是从头开始,找到第一值是 null 的元素删除;LinkedList 新增删除时对 null 值没有特殊校验,是允许新增和删除的

问:ArrayList 和 LinedList 是线程安全的么,为什么

答:都非线程安全,主要的问题点在于多线程环境下,所有线程任何时刻都可对数组和链表进行操作,这会导致值被覆盖,甚至混乱的情况