试中ArrayList和LinkedList

Arraylist：底层是基于动态数组，根据下表随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组，是因为Arraylist在数组元素超过其容量大，Arraylist可以进行扩容（针对JDK1.8  数组扩容后的容量是扩容前的1.5倍），Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8，对于空出的8位，目前解释是 ：①存储Headerwords；②避免一些机器内存溢出，减少出错几率，所以少分配③最大还是能支持到Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）。以下是Arraylist部分源码：

• 
  

Arraylist扩容：

Arraylist添加数据：（向数组尾部添加）

• 向数组尾部添加）
• 
  

向数组的指定位置添加数组：

• ：
• 
  

可以看到，只要ArrayList的当前容足够大，add()操作向数组的尾部的效率非常高的，当向数组指定位置添加数据时，会进行大量的数组移动复制操作。而数组复制时，最终将调用System.arraycopy()方法，因此add()操作的效率还是相当高的。尽管这样当向指定位置添加数据时也还是比Linkedlist慢，后者添加数据只需要改变指针指向即可。Arraylist删除数组也需要移动数组，效率较慢。
Linkedlist基于链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。
Arraylist get数据的源码：（根据下标访问，效率高）

• ）
• 
  

Linkedlist访问数据的源码：（node()函数遍历链表）

• 
  

总结：1、对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
                 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
           2、各自效率问题：

试中ArrayList和LinkedList

Arraylist：底层是基于动态数组，根据下表随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组，是因为Arraylist在数组元素超过其容量大，Arraylist可以进行扩容（针对JDK1.8  数组扩容后的容量是扩容前的1.5倍），Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8，对于空出的8位，目前解释是 ：①存储Headerwords；②避免一些机器内存溢出，减少出错几率，所以少分配③最大还是能支持到Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）。以下是Arraylist部分源码：

• 
  

Arraylist扩容：

Arraylist添加数据：（向数组尾部添加）

• 向数组尾部添加）
• 
  

向数组的指定位置添加数组：

• ：
• 
  

可以看到，只要ArrayList的当前容足够大，add()操作向数组的尾部的效率非常高的，当向数组指定位置添加数据时，会进行大量的数组移动复制操作。而数组复制时，最终将调用System.arraycopy()方法，因此add()操作的效率还是相当高的。尽管这样当向指定位置添加数据时也还是比Linkedlist慢，后者添加数据只需要改变指针指向即可。Arraylist删除数组也需要移动数组，效率较慢。
Linkedlist基于链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。
Arraylist get数据的源码：（根据下标访问，效率高）

• ）
• 
  

Linkedlist访问数据的源码：（node()函数遍历链表）

• 
  

总结：1、对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
                 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
           2、各自效率问题：