概述

Java中List知识点主要涵盖ArrayList、LinkedList实现，需要理解实现逻辑，及实际使用场景。另外在JUC中需要注意线程安全问题。

ArrayList

Java可动态扩容数组的实现。底层动态扩容数组，更适合快速查找（随机访问），不适合频繁新增删除。

• ArrayList 有最大容量的，为 Integer 的最大值（2^31-1），大于这个值 JVM 是不会为数组分配内存空间的
• 可添加删除null，删除null找到第一个值删除

ArrayList的动态扩容

效果

• 使用者不用关心底层数据结构的变化，封装得很好
• 1.5 倍的扩容速度，可以让扩容速度在前期缓慢上升，在后期增速较快
• 大部分工作中要求数组的值并不是很大，所以前期增长缓慢有利于节省资源，在后期增速较快时，也可快速扩容。

扩容步骤

1. 初始默认0，添加一个元素后，变为10

2. 每次扩容的大小为原来的一半（>>1 向右位移运算（除以2取整），再加上增量），1.5倍扩容

   例如：10+10>>1=15, 15+15>>1=22, 22+22>>1=33

注意

• addAll 如果一次加入的元素量大于扩容量，就直接扩容到需要的大小

• 拷贝很大的数组，可一开始就指定ArrayList(容量)，避免频繁扩容。频繁扩容就会有大量拷贝的工作，造成拷贝的性能低下

LinkedList

底层双向链表。可用于实现队列与栈。

• LinkedList 更适合于经常新增和删除，对查询反而很少的场景。
• 理论上可以无限大。LinkedList 实际大小(下标)用的是 int 类型，这也说明了 LinkedList 不能超过 Integer 的最大值，不然会溢出。
• 允许插入删除null，但作为Queue实现最好加判断拦截，否则无法区分poll是null还是异常

队列的实现

栈的实现

线程安全问题

手动复现

一个线程往List里添加，另一个线程遍历输出。

问题和异常

多线程下，共享变量，导致并发修改异常，ConcurrentModificationException

解决方案一

• Vector类的所有⽅法都是同步的。可以由两个线程安全地访问⼀个Vector对象，但是⼀个线程访问Vector的话代码要在同步操作上耗费⼤量的时间，性能低。
• 利用Collections工具类实现。Synchronized是依赖于JVM实现的，非公平锁。

解决方案二（推荐）

• CopyOnWriteArrayList写时复制技术。是Arraylist的一种线程安全变体，其中所有可变操作（add、set等）都是通过生成底层数组的新副本来实现的。同时满足写和读，读写分离。

• 并发操作中使用ReenTrantLock，是JDK实现的，公平锁。

遍历

• 迭代器

  迭代中不使用list.remove(e)，使用iterator.remove()删除元素

• for 效率低

• forEach

• stream流 配合stream中的各个方法

关于【一分钟学Java】

【一分钟学Java】是一个巩固Java基础知识的文档集合。

每天一分钟，碎片化学习，面试复习，助你上岸！！！