List集合

List集合

List是一个接口，它继承于Collection的接口，代表着有序的队列（其中的元素可以重复）

List集合下最常见的集合类有两个：ArrayList和LinkedList

不怎么用的Vector（与ArraList一样通过数组实现，但是Vector是线程安全的，如果不涉及线程安全问题，ArrayList更好（因为Vector使用synchronized，必然会影响效率））。

工作中，基本无脑用ArrayList

原因：

• 在工作中，遍历的需求比增删多，即便是增加元素旺旺也只是从尾部插入元素，而ArrayList在尾部插入元素也是O(1)
• ArrayList增删没有想象中慢，ArrayList的增删底层调用的copyOf()**被优化过，加上现代CPU对内存可以块操作**，普通大小的ArrayList增删比LinkedList更快。

LinkedList本身实现了Queue接口（一般用于耍算法题）

如果考虑线程安全的问题，CopyOnWriteArrayList，它的思想（CopyOnWrite），这个思想在Linux/文件系统都有用到。

ArrayList

ArrayList属性

//初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
//指定该ArrayList容量为0时，返回该空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//它与上面EMPTY_ELEMENTDATA区别：该数组时默认返回的，后者需要用户指定容量为0时返回,如果第一次添加数据的话那么数组扩容长度为DEFAULT_CAPACITY=10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存添加到ArrayList中的元素，当第一次添加元素进入Arraylist中时，数组将扩容DEFAULT_CAPACITY
transient Object[] elementData;
//ArrayList实际的大小
private int size;

由此可知：ArrayList底层其实就是一个数组

构造方法

//如果指定了容量，那么数组就初始化成对应的容量
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);
        }
    }

//如果没有指定容量，返回DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//构造一个包含指定集合元素的列表，其顺序由集合的迭代器返回
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add

JDK1.8与JDK1.14不同，先1.8

modCount是快速报错机制

//直接添加元素，确认list容量，尝试容量加1，看看有无必要
public boolean add(E e){
    ensureCapacityInternal(size + 1);
    //完成了size+1
    elementData[size++] = e;
    return true;
}

//先检查是否越界，再确定容量
public void add(int index, E element){
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

//addAll的两个方法，可以接受的参数对象为一个集合类型
//如果用了泛型，那么再Integer的类型的集合addAll到String类型的集合中就会在编译器抛出错误
//如果不用泛型，那么每次取出其中的数据，除非每次强制转换都正确，否则也会错误
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
 
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
 
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
}
//判断当前数组是否是默认构造方法生成的空数组，如果是的话minCapacity=10反之根据原来的值传入下一个方法去完成下一步扩容
private void ensreCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if(minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//扩容核心方法，有三种情况进行解析
//1、当前数组时默认构造方法生成的空数组并且第一次添加数据，此时minCapacity等于默认的容量10，可以看到最后数组的容量会从0扩容到10,。而后的数组扩容才是按照当前容量的1.5倍进行扩容
//2、当前容量是自定义初始容量构造方法创建并且指定出事容量为0.此时minCapacity等于1那么最后的数组容量会从0变成1.这就有一个严重的问题，一旦我们执行了初始容量为0，那么根据下边的算法前四次扩容每次都+1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容
//3、当newCapacity大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCpacity已经大雨Integer的最大值（溢出为负数）那么抛出内存溢出异常，否则根据MAX_ARRAY_SIZE的比较情况确定是返回Integer最大值还是MAX_ARRAY_SIZE。ArrayList允许的最大容量就是Integer的最大值
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity +(oldCapacity >> 1);
    if(new Capacity - minCapacity < 0)
        newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, new Capacity);

private static int hugCapacity(int minCapacity) {
    if(minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ？
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math,min(orriginal.length, newLength));
    return copy;
}

private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/*src - 源数组
      srcPos - 源数组中的起始位置 
      dest - 目标数组
      destPos - 目的地数据中的起始位置
      length - 要复制的数组元素的数量*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,  int length);

remove（int index）

删除时也用了System的本地方法arraycopy，删除位置后几位数全部向前移动一位，返回被删掉的数据

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; // clear to let GC do its work 消除过期对象的引用
 
        return oldValue;
}

remove(Object o)

删除Object操作分开了Null，重点是要注意的是在对非空对象进行删除的时候ArrayList是调用了equals来匹配数组中的数据。也就是说如果你的集合（不局限于ArrayList）是对类进行操作，而你的类没有重写hashCode以及equals，那么你通过该方法来删除数据都是无法成功的，总之如果你要在集合中对类对象进行操作就需要重写上述的两个方法。此外就算你ArrayList中存有多个相同的Obejct对象，执行该方法也只会删除一次。或许有人会有疑问，既然使用equals那直接重写equals不就好了何必跟着重写hashCode呢？答案是如果你只重写equals是可以完成删除操作，但是你重写equals没有重写hashCode那么你在使用散列数据结构HashMap，HashSet对该类进行操作的话会出错（jdk1.8 HashMap工作原理(Get,Put)和扩容机制）。而在Object规范中提到的第二点要求就是如果两个对象经过equals比较后相同，那么他们的hashCode一定相同。所以这就是为什么要hashCode跟euqals两者同时重写。

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;//只删除一次就返回
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
 
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work 消除过期对象的引用
}

iterator被内部类的方式实现，从源码可知：Iterator实际上就是在遍历集合,

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        // prevent creating a synthetic constructor
        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            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();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                // update once at end to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * An optimized version of AbstractList.ListItr
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

从源码看出，List有它自己对应的ListIterator接口

这个接口比普通的Iterator接口多了几个方法

可知：ListIterator可以往前遍历，添加元素，设置元素

LinkedList

get

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

//下标小于长度的一半，那就从头遍历，否则从尾遍历
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;
        }
    }

总结

ArrayList

• 底层实现是数组
• 默认初始化容量10，每次扩容增加原来容量的1.5倍（如果还不够就按给的容量来，但不能超过2的31次方-1
• 增删的时候，需要数组的拷贝复制（navite 方法由C/C++实现）

LinkedList

• 双向链表实现

Vector

• 底层是数组，现在很少用，被ArrayList取代
• 所有方法都是同步，有性能损失
• 初始长度10，增长2倍，比ArrayList更耗内存