导航
前言
首先声明本文使用的是jdk1.8
List 常见实现类
根据上篇Collection的文章我们了解了List的几个常见实现类。
image
- ArrayList：
底层数据结构是数组。线程不安全 - LinkedList：
底层数据结构是链表。线程不安全 - Vector：
底层数据结构是数组。线程安全
ArrayList
ArrayList的实现和继承结构
image
ArrayList类特点
image
- 可动态的改变数组的大小(数组的拷贝)。
- 和Vector类函数实现相似，区别只是线程不安全。
另外Vector有许多设计上的不足，不建议使用。当多条线程访问ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的。
ArrayList解析
ArrayList属性解析
其实注释写的都很清晰
构造函数
前两种方式十分的简单，需要注意的就是第三种：
在通过一个Collection来构造ArrayList的时候，其toArray函数可能不能成功返回一个Object[]类型的数组。需要我们再把elementData数组中的元素拷贝到Object[size]类型的数组中并重新赋值给elementData。
add()
函数处理步骤：
- 检查是否需要扩容
- 插入元素
元素在插入到集合前需要先对ArrayList进行判断是否需要扩容。
image
ensureCapacityInternal函数来确定真正的数组最小容量minCapacity
拿（当前元素个数+1）来进行判断。如果当前容器没有进行初始化。那么取minCapacity和DEFAULT_CAPACITY两个元素中较大的值作为数组的最小容量(也就是需求容量在10以下我们也把数组初始化成了容量为10，防止频繁的扩容操作)。
ensureExplicitCapacity函数记录容器的更改状态并判断容器是否真的需要扩容
modCount记录容器被修改过的次数。当通过ensureCapacityInternal函数确定的容器最小容量minCapacity大于数组当前大小时。调用grow函数来对数组进行扩容
image
- 如果扩容1.5倍后还小于需要的最小容量，干脆让数组容量等于minCapacity。
- 如果数组要求的最小容量已经大于数组所被允许的最大容量限制。让其容量最大只能等于Integer.MAX_VALUE。
image
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- 根据释义我们可以知道一些虚拟机在数组头会保存一些头元素。
- 请求的数组过大的话会出现OOM异常。可能会超出部分VM的限制
image
- 源码叙述的很清晰。接着上面的看，对elementData进行拷贝。将该数组元素拷贝到一个也是该数组类型的且容量为newCapacity的数组中。
总结：
- 首先去检查一下数组的容量是否足够
- 足够：直接添加
- 不足够：扩容
- 扩容到原来的1.5倍
- 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。
add(int index, E element)
image
函数处理步骤：
- 要插入元素的位置判断。是否小于0或超出当前数组元素
- 扩容判断
- 数组拷贝
由于ensureCapacityInternal函数的保障，所以这里数组元素移位即可。
image
可以发现在ArrayList中由于底层实现是由数组来作为容器。所以与扩容相关的add函数底层其实都是System类的arraycopy()函数来实现的
而其又是native函数，底层最终调用了C的memmove() 函数。该函数的相比于我们自定义的数组拷贝实现要性能高得多。更有可能得到细致的优化，应该尽可能去使用它。
参考R大回答：https://www.zhihu.com/question/53749473
get(int index)
image
字面意思
set(int index, E element)
image
字面意思
remove(int index)
正如注释中所述。
函数处理步骤：
- index索引边界判断
- modCount变量的维护
- 取出数组index处元素用于结果返回
- 数组元素从index+1处开始依次往前移一位。
其实看完remove函数之后，我比较疑惑为什么jdk开发人员在设计remove函数的时候不和add函数一样动态的维护数组的大小呢？因为我自己在学习数据结构的时候，设计我的ArrayList集合类的时候其add函数和remove函数都根据数组现有元素数量和数组总容量做了一个系数比，根据系数比动态的维护了其容量。
后来仔细一想，这么设计也确实很合理。ArrayList作为List接口常用的实现类之一，既然其容量确实到达过一个峰值。即便其后来被降下来了，也很难保证其后续不会再升回去。因为既然原来能到达，那么后续也肯定可以到达。所以既然这样就需要函数体中频繁的判断，频繁的扩容缩容性能上无疑会更大的放大了ArrayList在增删上的劣势。不可取
trimToSize()
image
remove函数由于性能影响在删除元素后既然不能缩容，Java开发人员提供了该函数供开发人员根据自己的需要来对数组缩容。底层依旧调用的是System类的arraycopy函数。
我设计的ArrayList
Github地址 - 我设计的ArrayList
实现了Arraylist的部分常见功能。
Vector与ArrayList区别
image
Java开发人员已经告诉我们了。
- 出生于jdk1.0时代，并在jdk1.2的时候被改造为实现List接口。
- 底层也是动态数组实现
- 它是线程安全的
- 如果不需要线程安全的实现，建议使用ArrayList代替Vector(早期设计有些许缺陷)。
可以从图中很明显的看出，Vector类在很多对其底层数组结构有修改作用的函数上都加上了synchronized关键字来保证其线程安全性。
image
如果想要ArrayList实现同步，可以使用Collections的方法：List list = Collections.synchronizedList(new ArrayList(...));，就可以实现同步了。
image
还有另一个区别：
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector则是如果未指定其容量不够时扩容的数组容量大小，那么Vector扩展1倍。
image
LinkedList
LinkedList的实现和继承结构
image
LinkedList类特点
image
- LinkedList底层是双向链表
- 允许存储NULL
- 线程不安全的，解决办法和Arraylist一样，通过Collections工具类来封装一下。并且在迭代的时候需要外部手动锁住该LinkedList的实例
image
LinkedList 类还为在列表的开头及结尾 get，remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
LinkedList解析
LinkedList属性解析
image
LinkedList的属性和我们自己设计的LinkedList一模一样。
很简单由于是双向链表就必然有头结点和尾节点两个属性，再加一个size变量指定LinkedList元素数量方便我们维护。
构造函数
image
其实构造思路很简单。第二种无非就是把一个集合迭代的跟到LinkedList实例之后。然后根据一些不同的case进行处理。和我们设计的LinkedList处理思路是一样的，只是可能它设计的更严谨一些。
add(E e)
image
我设计的LinkedList是单向链表，所以为了保证add函数的性能选择了头插法。而LinkedList的实现由于是双向链表，所以必然是尾插法才合理。
remove(Object o)
image
- 如注释所述，删除链表中第一次出现和指定元素的item属性equals的元素。
前提是需要对可能存在的NULL元素做过滤处理。避免空指针异常。
unlike函数：
- 其实就是具体的负责链表中元素的删除工作。
- modCount变量的维护
- 具体逻辑的判断不同case的处理(其实和我们的实现思路一样)
可以看出unlink函数的局部变量使用了final关键字来修饰。从一定程度上避免了一些由于LinkedList是线程不安全的类所带来的线程安全问题。同时也带来了一些性能上的提升
get(int index)
image
和我们正常获取元素的思路一致。对于LinkedList来说由于底层是双向链表，我们要向获取到指定位置的元素只能通过遍历的方式。但是Java开发人员想的非常周到，首先对index索引进行了大小判断，看时候大于size的一半，直接就是查询范围缩小了一半。更加高效
set(int index, E element)
image
如同注释描述的一致，没有多余操作，由于关系到index索引，所以按例检查一下。然后进行替换即可。
我设计的LinkedList
Github地址 - 我设计的ArrayList
总结
ArrayList
- ArrayList是基于动态数组实现的，在增删时候，需要调用System类的arraycopy函数进行拷贝复制((navite 函数底层由C/C++实现)。
- ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
- 删除元素时不会减少容量，若希望减少容量则调用trimToSize()
- 它大体上相似Vector，但不是线程安全的。多线程环境下，任何关于ArrayList集合类结构上的更改，为保障线程安全，我们都需要程序内手动的维护
- 能存放NULL值，元素可重复，且有序。
LinkedList
- LinkedList底层是双向链表(更方便获取指定元素)
- 允许存储NULL
- 线程不安全的，解决办法和Arraylist一样，通过Collections工具类来封装一下。并且在迭代的时候需要外部手动锁住该LinkedList的实例
Vector
- 出生于jdk1.0时代，并在jdk1.2的时候被改造为实现List接口。
- 底层也是动态数组实现
- 它是函数操作是线程安全的
- 现在已少用，被ArrayList替代，原因：
- Vector所有方法都是同步，有性能损失。
- Vector初始length是10 超过length时，如果未指定扩容大小。以成倍态势增长，相比于ArrayList开销更多内存。
- 出生早，设计可能不那么好
并且它唯一的优点，部分函数的线程安全对于我们来说，也不是必须的。
具体可参考：java数据结构中，什么情况下用Vector,什么情况下用ArrayList呢？
场景
- 查询多用ArrayList，增删多用LinkedList。
- ArrayList增删慢也是在大数据量的前提下。在我实现的数据结构中进行了测试(10w~),少量数据差别不大
网友评论