Java数据结构之List（java list ?）

在Java语言中，List集合是非常重要和常用的集合，它继承了Collection接口，因此它包含了Collection接口的全部方法，并且外加了一些其他方法。它有两个重要的接口实现类ArrayList和LinkedList。本文主要对这个两个实现类进行说明和对比：

（一）、ArrayList

ArrayList可以说是一个数组，对ArrayList进行操作其实就是对一个数组进行操作，这个数组叫elementData；

所不同的是，这个数组在初始化的时候有一个默认大小，长度是10。当我们调用add方法时，该类会将目前的数组原有长度和添加后的实际长度进行比较，如果添加后的实际长度超过了数组的原有长度，这个数组就会自动扩容，扩充后的长度大约为原长度的1.5倍。如下图可知，扩容的长度为原长度向左移动1位，大约为原长度的二分之一。

既然是数组，就具备数据的优缺点，查询效率较高，新增和删除效率较低；其实并非如此，数据具备这样的优缺点的主要原因是每一个值都有一个索引相对应，新增和删除时，索引需要重新排列，导致资源的消耗，但是如果每次新增和删除都从该数组的最后一个开始，则和链表结构没有太大区别。

（二）、 LinkedList

与ArrayList不同，LinkedList是一个链表结构，确切的是，是一个双向链表结构，如下图

在LinkedList中，有一个静态私有内部类Node，对LinkedList进行操作就是对该内部类进行操作。List中的每一个值，其实就是一个Node。在这个链表结构中，有一个头节点和一个尾节点，最靠近头节点的元素索引为0，然后以此类推，当这个链表为空时，它只有头节点和尾节点，这样的好处的：不管这个链表是否为空，新增时都会先打断原有链接，再建立新的链接，实现了操作的统一性。

LinkedList共有4个新增方法，分别是add(E)，addFirst(E)，addLast(E)，add(int index,E)，想必大家都能看懂，add(E)和addLast(E)的效果是一样的。

值得一说的是在调用get(int index)时，有这样一个方法。

这个方法时干什么的，链表结构查询效率慢，这个方法时为了提高查询效率，具体实现是：当要查询元素的索引大于链表长度的一半时，就从后向前找；如果小于链表长度的一半时，则从前向后找。（厉害）

（三）、ArrayList和LinkedList的实际比较

1.调用add(E)方法，新增100万调数据耗时对比， ArrayList耗时377ms,LinkedList耗时512ms

2调用add(int index,E)方法，每次都在索引为0的位置添加，新增10万调数据耗时对比， ArrayList耗时3567ms,LinkedList耗时48ms

3 调用get()方法，查询10万条数据耗时对比，ArrayList耗时9ms,LinkedList耗时18914 ms

4.调用remove方法，移除集合中的偶数耗时对比，这个操作有两个问题，第一，如果使用for循环进行操作，你会发现linkedList耗时要大于ArrayList，这是因为使用for循环时，删除一个元素前必须先获取这个元素，而在获取操作上，ArrayList具有更大优势；第二，使用增强for循环，不管是ArrayList还是LinkedList都会报java.util.ConcurrentModificationException错误，这是因为在删除一个元素后，现有的元素就会进行重新排序，而这对于增强的for循环所使用的的基础迭代器是非法的。所以我们操作remove时，使用第三种方法，就是Interator迭代器，数据量为10万条，耗时对比，ArrayList耗时1867ms,LinkedList耗时21 ms

以上为小编首次整理技术方面的文档，如有不妥之处，敬请斧正。