ArrayList 与 LinkedList的异同点

时间:2021-11-29 19:34:47

ArrayList:底层是数组结构,查询快,增删慢,不同步。

LinkedList:底层是链表结构,增删快,查询慢,不同步。

linkedList 是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好

有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。 
LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以使用如下方式:

List list=Collections.synchronizedList(new LinkedList(...));

HashMap 初始化大小是 16 ,扩容因子默认0.75(可以指定初始化大小,和扩容因子) 
扩容机制.(当前大小 和 当前容量 的比例超过了 扩容因子,就会扩容,扩容后大小为 一倍。例如:初始大小为 16 ,扩容因子 0.75 ,当容量为12的时候,比例已经是0.75 。触发扩容,扩容后的大小为 32.)

ArrayList默认构造的容量为10。ArrayList默认size()是0, 因为ArrayList的底层是由一个Object[]数组构成的,而这个Object[]数组,默认的长度是10,所以ArrayList长度容量为10,然而你所指的size()方法,指的是“逻辑”长度,及是指内存已存在的“实际元素的长度” 而“空元素不被计算。

//通过ArrayList实现的接口可知,其支持随机访问,能被克隆,支持序列化,支持泛型
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //序列版本号
    private static final long serialVersionUID = 8683452581122892189L;
   //默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    //被用于空实例的共享空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //被用于默认大小的空实例的共享数组实例。其与EMPTY_ELEMENTDATA的区别是:当我们向数组中添加第一个元素时,知道数组该扩充多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * Object[]类型的数组,保存了添加到ArrayList中的元素。ArrayList的容量是该Object[]类型数组的长度
     * 当第一个元素被添加时,任何空ArrayList中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会被
     * 扩充到DEFAULT_CAPACITY(默认容量)。
     */
    transient Object[] elementData; //非private是为了方便嵌套类的访问
    // ArrayList的大小(指其所含的元素个数)
    private int size;

    ......  

}


ArrayList包含了两个重要的对象:elementData 和 size。

elementData 是”Object[] 类型的数组”,它保存了添加到ArrayList中的元素。实际上,elementData是个动态数组,我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity;如果通过不含参数的构造函数ArrayList()来创建 ArrayList,则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长,具 体的增长方式,请参考源码分析中的ensureCapacity()函数。

size 则是动态数组的实际大小。

若ArrayList的容量不足以容纳当前的全部元素,设置 新的容量=“(原始容量x3)/2 + 1”,这种算法构造出来的新的数组长度的增量都会比上一次大( 而且是越来越大) ,即认为客户需要增加的数据很多,而避免频繁newInstance 的情况。

都说ArrayList是动态数组,那么它里面存储数据的数据结构是什么呢?

private transient Object[] elementData;  

上面这个对象数组就是其存储元素的数据结构,前面有一个java关键字transient,这个关键字是去序列化的意思,即,在这个类序列化后保存到磁盘或者输出到输出流的时候,这个对象数组是不被保存或者输出的

ArrayList提供了三个构造方法,第一个是由调用者传入指定List的大小来创建elementData数组。第二个是默认的构造方法,默认数组容量是10。第三个是根据传入的一个集合,将集合转化成数组,然后赋给elementData


public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**  * Constructs an empty list with an initial capacity of ten.  */ public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

/**  * Constructs a list containing the elements of the specified  * collection, in the order they are returned by the collection's  * iterator.  *  * @param c the collection whose elements are to be placed into this list  * @throws NullPointerException if the specified collection is null  */ public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) 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;
}
根据传入的index,然后利用System.arraycopy()方法将index后面的元素从index位置开始进行覆盖,这里需要注意的是,index+1到size位置的元素,覆盖掉index到size位置的元素,所以最后的两个元素肯定相同,即重复了,所以最后一步会有elementData[–size] = null;将最后一个元素置为null。最后返回删除元素的值

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clear方法并不是把整个数组都删除,因为毕竟已经申请了内存,这样删了,很可惜,因为可能以后还用得着,这就免去了再次去申请内存的麻烦。这里的clear只是把每个元素的都置为null,并把size设为0

public void add(int index, E e) {
    if (index < 0 || index > this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

根据指定位置,插入指定元素,先进行越界检查,再进行容量检查,然后将从index开始的元素到最后的元素,从index+1位置开始往后复制,然后将指定元素插入到index位置,然后将容量size增加1。

public boolean addAll(int index, Collection<? extends E> c) {
    if (index < 0 || index > this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    int cSize = c.size();
    if (cSize==0)
        return false;

    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
    parent.addAll(parentOffset + index, c);
    this.modCount = parent.modCount;
    this.size += cSize;
    return true;
}

在数组后面插入一个指定集合里面的所有元素,首先将集合转化为数组,然后进行容量检查,将目标数组元素拷贝到elementData上。这里有一点需要注意,如果传入的集合为null,那么结果会返回FALSE。

LinkedList有两个构造方法,一个用于构造一个空的链表,一个用已有的集合创建链表

public LinkedList() {
}
 public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}