ArrayList和LinkedList哪个更占空间？

前言

　　相信在面试的时候可能都会碰到关于ArrayList和Linkedlist相关的面试题。趁此机会也记录一下。

ArrayList

　　ArrayList是List接口的一个实现类，底层是Object数组，数据放在一个变量里面：

transient Object[] elementData;

　　而这个elementData数组使用了一个transient关键字修饰，transient表示的意思是：序列化对象的时候，如果在属性前面加上了该关键字，那么在序列化是就不会将该属性序列化。

　　ArrayList初始化时默认数组长度为10，随着我们不断的往list中插入数据，当list大小超过容量时就会进行扩容，每次扩容的大小为之前的1.5倍。可以这么理解，当list已经足够大时，如果刚好插入的数据满足扩容的条件，那么扩容之后的list容量为之前的1.5，于是这个空间已经扩展的很大了。

　　由于ArrayList底层是数组，数组我们都知道可以根据索引来定位，相应ArrayList查找性能很快。但是数组我们又知道是一连串的空间组成，于是当我们在中间插入或者删除一个元素时，插入或删除位置之后的元素是不是都要向后移动或向前移动一位，所以插入或者删除都比较消耗性能。最后我们又知道，既然你是在中间插入或删除时后面元素需要移动，那我在最后插入元素是不是很快呢？是的，最后插入由于不需要移动元素，插入的效率很高。总结：ArrayList底层是数组，可以根据索引查找元素，查找效率很高，在数组中间插入或删除元素由于需要移动数据导致效率很低，但是在最后插入元素效率很高。

Linkedlist

　　Linkedlist底层是双向链表，不需要指定初始容量，链表中任何一个存储单元都可以通过向前或向后的指针获取到前面或后面的存储单元。源码中使用Node来存储数据。

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;    
    }
}

　　　因为有保存前后节点的地址，LinkedList增删数据的时候不需要像ArrayList那样移动整片的数据，只需要通过引用指定index位置前后的两个节点即可。删除数据只需要改变index位置前后节点的指向地址即可。虽然增删数据很快，但是查询数据效率就比较低，查询数据时，首先会计算下链表总长度的一半，判断对应索引是在该值的左边还是右边，然后决定从头节点还是尾节点开始遍历。所以，Linkedlist增删数据较快，查询数据较慢，并且对内存占用空间也是很大的，因为每个node都维护这前后指向地址的节点。

谁更占空间？

　　表面上看，肯定是Linkedlist更占用空间，但是ArrayList扩容的时候会把之前的容量扩充为1.5倍。你可以试想下，我往ArrayList只想加一个元素，但刚好满足扩容条件，那是不是剩下的空间就浪费了呢。况且ArrayList本身就很大了，扩容1.5倍。。。　

　　所以，如果数据量很大又在实时添加数据的情况下，ArrayList占用的空间不一定会比LinkedList空间小，这样的回答就显得谨慎些了，听上去也更加让人容易认同，但你以为这样回答就完美了吗？还记得我前面说的那个transient变量吗？它的作用已经说了，不想序列化的对象就可以用它来修饰，用transient修饰elementData意味着我不希望elementData数组被序列化。

　　为什么要这么做呢？这是因为序列化ArrayList的时候，ArrayList里面的elementData，也就是数组未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法。

　　每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData这个数组对象不去序列化它，而是遍历elementData，只序列化数组里面有数据的元素，这样一来，就可以加快序列化的速度，还能够减少空间的开销。

　　最后，一般情况下，LinkedList的占用空间更大，因为每个节点要维护指向前后地址的两个节点，但也不是绝对，如果刚好数据量超过ArrayList默认的临时值时，ArrayList占用的空间也是不小的，因为扩容的原因会浪费将近原来数组一半的容量，不过，因为ArrayList的数组变量是用transient关键字修饰的，如果集合本身需要做序列化操作的话，ArrayList这部分多余的空间不会被序列化。