Java集合——List

1. List的几种实现List 是有序的 Collection允许元素重复实现 List 的类有LinkedList、ArrayList、Vector、Stack 等。ArrayList是应用更加广泛的动态数组实现它本身不是线程安全的所以性能要好很多。与Vector近似ArrayList也是可以根据需要调整容量不过两者的调整逻辑有所区别Vector在扩容时会提高1倍而ArrayList 则是增加 50%。LinkedList顾名思义是Java提供的双向链表所以它不需要像上面两种那样调整容量它也不是线程安全的。Vector是Java早期提供的线程安全的动态数组如果不需要线程安全并不建议选择毕竟同步是有额外开销的。Vector内部是使用对象数组来保存数据可以根据需要自动的增加容量当数组已满时会创建新的数组并拷贝原有数组数据。Vector和ArrayList作为动态数组其内部元素以数组形式顺序存储的所以非常适合随机访问的场合。除了尾部插入和删除元素往往性能会相对较差比如我们在中间位置插入一个元素需要移动后续所有元素。而LinkedList进行节点插入、删除却要高效得多但是随机访问性能则要比动态数组慢。2. List可以一边遍历一边修改元素吗具体问题具体分析取决于遍历方式和具体的List实现类1使用普通for循环遍历可以在遍历过程中修改元素只要修改的索引不超出 List 的范围即可。import java.util.ArrayList; import java.util.List; public class ListTraversalAndModification{ public static void main(String[] args){ ListIntegerlist new ArrayList(); list.add(1); list.add(2); list.add(3); //使用普通for循环遍历并修改元素 for (int i0;ilist.size();i){ list.set(i,list.get(i) * 2); System.out.println(list); } } }2使用foreach循环遍历一般不建议在foreach循环中直接修改正在遍历的List元素因为这可能会导致意外的结果或concurrentModificationException异常。在foreach循环中修改元素可能会破坏迭代器的内部状态因为foreach循环底层是基于迭代器实现的在遍历过程中修改集合结构会导致迭代器的预期结构和实际结构不一致。import java.util.ArrayList; import java.util.List; public class ListTraversalAndModification{ public static void main(String[] args){ ListIntegerlist new ArrayList(); list.add(1); list.add(2); list.add(3); //使用foreach循环遍历并尝试修改元素会抛出ConcurrentModificationException异常 for (Integer num :list) { list.set(list.indexof(num)num * 2); System.out.println(list); } } }3使用迭代器遍历时可以使用迭代器的$remove$方法来删除元素但如果要替换元素的值对于不可变对象如IntegerString必须通过ListIterator的set方法来进行而不是直接通过List的set方法否则会抛出ConcurrentModificationException异常。importjava.util.ArrayList; importjava.util.ListIterator// 注意这里要用ListIterator public class ListTraversalAndModification { public static void main(String[] args) { ArrayListInteger list new ArrayList(); list.add(1); list.add(2); list.add(3); //使用ListIterator遍历并修改元素 ListIteratorInteger iteratorlist.listIterator()//使用listIterator(方法) while (iterator.hasNext()){ Integer num iterator.next(); if (num.equals(2)) { //使用ListIterator的set方法修改替换元素 iterator.set(4); System.out.println(1ist)//输出[143] } } } }对于线程安全的List如CopyOnWriteArrayList由于其采用了写时复制的机制在遍历的同时可以进行修改操作不会抛出ConcurrentModificationException异常但可能会读取到旧的数据因为修改操作是在新的副本上进行的。3. List如何快速删除某个指定下标的元素1ArrayList提供了remove(int index方法来删除指定下标的元素该方法在删除元素后会将后续元素向前移动以填补被删除元素的位置。如果删除的是列表末尾的元素时间复杂度为O(1)如果删除的是列表中间的元素时间复杂度为O(n)n为列表中元素的个数因为需要移动后续的元素。import java.util.ArrayList; import java.util.List; public class ArrayListRemoveExample{ public static void main(String[] args){ ListInteger listnew ArrayList(); list.add(1); list.add(2); list.add(3); //删除下标为1的元素 list.remove(1); System.out.println(list); } }2LinkedList的remove(int index方法也可以用来删除指定下标的元素。它需要先遍历到指定下标位置然后修改链表的指针来删除元素。时间复杂度为O(n)n为要删除元素的下标。不过如果已知要删除的元素是链表的头节点或尾节点可以直接通过修改头指针或尾指针来实现删除时间复杂度为O(1)。import java.util.LinkedList; import java.util.List; public class LinkedListRemoveExample{ public static void main(String[] args){ ListInteger list new LinkedList(); list.add(1); list.add(2); list.add(3); //删除下标为1的元素 list.remove(1); System.out.println(list); } }3CopyOnWriteArrayList的remove方法同样可以删除指定下标的元素。由于CopyOnWriteArrayList在写操作时会创建一个新的数组所以删除操作的时间复杂度取决于数组的复制速度通常为O(n)n为数组的长度。但在并发环境下它的删除操作不会影响读操作具有较好的并发性能。import java.util.concurrent.CopyOnwriteArrayList; public class CopyOnWriteArrayListRemoveExample{ public static void main(String[]args){ CopyOnWriteArrayListIntegerlistnew CopyOnWriteArrayList(); list.add(1); list.add(2); list.add(3); //删除下标为1的元素 list.remove(1); System.out.println(list); } }4. ArrayList 和 LinkList 的区别哪个集合是线程安全的ArrayList和LinkedList都是Java中常见的集合类它们都实现了List接口。底层数据结构不同ArrayList使用数组实现通过索引进行快速访问元素。LinkedList使用链表实现通过节点之间的指针进行元素的访问和操作。插入和删除操作的效率不同ArrayList在尾部的插入和删除操作效率较高但在中间或开头的插入和删除操作效率较低需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高因为只需要调整节点之间的指针但是LinkedList是不支持随机访问的所以除了头结点外插入和删除的时间复杂度都是O(n)效率也不是很高所以LinkedList基本没人用。随机访问的效率不同ArrayList支持通过索引进行快速随机访问时间复杂度为O(1)LinkedList需要从头或尾开始遍历链表时间复杂度为On。空间占用ArrayList在创建时需要分配一段连续的内存空间因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针因此相对较小。使用场景ArrayList适用于频繁随机访问和尾部的插入删除操作而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景.线程安全这两个集合都不是线程安全的Vector是线程安全的5. ArrayList 和 Vector 的区别是什么ArrayList和Vector都是Java中常用的动态数组实现用于存储和操作对象集合但它们在设计上有几个关键区别主要体现在线程安全性、性能和功能细节上。线程安全性这是最核心的区别。Vector是线程安全的它的大部分方法比如add、remove、get等都被synchronized修饰这意味着多线程环境下操作Vector时不需要额外处理同步问题。而ArrayList没有任何同步机制是非线程安全的在多线程并发修改时可能会出现数据不一致的问题比如抛出ConcurrentModificationException异常。性能正因为同步机制的存在两者在性能上也有差异。由于Vector的方法需要加锁释放锁在单线程环境下它的操作效率通常比ArrayList低。所以如果是单线程场景或者能自己保证线程安全的情况下ArrayList 是更优的选择性能更好。扩容机制当集合元素数量超过初始容量时都会自动扩容。Vector默认的扩容策略是翻倍如果没有指定增长因子的话比如初始容量10满了之后会扩容到20。而ArrayList在JDK1.8及之后默认是扩容为原来的1.5倍相对来说扩容的幅度更小能在一定程度上节省内存空间。Vector也可以通过构造方法指定增长因子灵活控制扩容幅度而ArrayList没有这个功能。总的来说选择两者时主要看是否需要线程安全如果是多线程环境且需要内置同步支持可能会用到Vector但现在更多时候会用ArrayList因为它性能更好而且在需要线程安全时可以通过Collections.synchronizedList()方法将ArrayList包装成线程安全的集合灵活性更高。6. ArrayList线程安全吗把ArrayList变成线程安全有哪些方法不是线程安全的ArrayList变成线程安全的方式有使用Collections类的synchronizedList方法将ArrayList包装成线程安全的ListListString synchronizedList Collections.synchronizedList(arrayList);使用CopyOnWriteArrayList类代替ArrayList它是一个线程安全的List实现CopyOnWriteArrayListString copyOnWriteArrayList new CopyOnWriteArrayList(arrayList);使用Vector类代替ArrayListVector是线程安全的List实现VectorString vector new Vector(arrayList);7. 为什么ArrayList线程不安全哪里不安全在高并发添加数据下ArrayList会暴露三个问题部分值为null我们并没有add null进去当线程1走到了扩容那里发现当前size是9而数组容量是10所以不用扩容这时候cpu让出执行权线程2也进来了发现size是9而数组容量是10所以不用扩容这时候线程1继续执行将数组下标索引为9的位置set值了还没有来得及执行size这时候线程2也来执行了又把数组下标索引为9的位置set了一遍这时候两个先后进行size导致下标索引为10的地方就为null了。索引越界异常线程1走到扩容那里发现当前size是9数组容量是10不用扩容cpu让出执行权线程2也发现不用扩容这时候数组的容量就是10而线程1set完之后size这时候线程2再set进来size就是10数组的大小只有10而你要设置下标索引为10的就会越界数组的下标索引从0开始size与我们add的数量不符这个基本上每次都会发生因为size本身就不是原子操作可以分为三步获取size的值将size的值加1将新的size值覆盖掉原来的线程1和线程2拿到一样的size值加完了同时覆盖就会导致一次没有加上所以肯定不会与我们add的数量保持一致的为了知道这三种情况是怎么发生的ArrayListadd增加元素的代码如下public boolean add(E e) { ensureCapacityInternal(size 1) // Increments modCount!! elementData[size]e; return true; }ensureCapacitylnternal()这个方法的详细代码可以暂时不看它的作用就是判断如果将当前的新元素加到列表后面列表的elementData数组的大小是否满足如果size1的这个需求长度大于了elementData这个数组的长度那么就要对这个数组进行扩容。大体可以分为三步1判断数组需不需要扩容如果需要的话调用grow方法进行扩容2将数组的size位置设置值因为数组的下标是从0开始的3将当前集合的大小加18. ArrayList 和 LinkedList的应用场景?ArrayList适用于需要频繁访问集合元素的场景。它基于数组实现可以通过索引快速访问元素因此在按索引查找、遍历和随机访问元素的操作上具有较高的性能。当需要频繁访问和遍历集合元素并且集合大小不经常改变时推荐使用ArrayListLinkedList适用于频繁进行插入和删除操作的场景。它基于链表实现插入和删除元素的操作只需要调整节点的指针因此在插入和删除操作上具有较高的性能。当需要频繁进行插入和删除操作或者集合大小经常改变时可以考虑使用LinkedList。9. ArrayList的扩容机制说一下ArrayList在添加元素时如果当前元素个数已经达到了内部数组的容量上限就会触发扩容操作。ArrayList的扩容操作主要包括以下几个步骤1计算新的容量一般情况下新的容量会扩大为原容量的1.5倍在JDK10之后扩容策略做了调整然后检查是否超过了最大容量限制。2创建新的数组根据计算得到的新容量创建一个新的更大的数组。3将元素复制将原来数组中的元素逐个复制到新数组中。4更新引用将ArrayList内部指向原数组的引用指向新数组。5完成扩容扩容完成后可以继续添加新元素。ArrayList的扩容操作涉及到数组的复制和内存的重新分配所以在频繁添加大量元素时扩容操作可能会影响性能。为了减少扩容带来的性能损耗可以在初始化ArrayList时预分配足够大的容量避免频繁触发扩容操作。之所以扩容是1.5倍是因为1.5可以充分利用移位操作减少浮点数或者运算时间和运算次数。// 新容量计算 int newCapacity oldCapacity (oldCapacity 1)10. 线程安全的 ListCopyonWriteArraylist是如何实现线程安全的CopyOnWriteArrayList底层也是通过一个数组保存数据使用volatile关键字修饰数组保证当前线程对数组对象重新赋值后其他线程可以及时感知到。private transient volatile Object[] array;在写入操作时加了一把互斥锁ReentrantLock以保证线程安全。public boolean add(E e) { // 获取锁 final ReentrantLock lock this.lock; // 加锁 lock.lock(); try { //获取到当前List集合保存数据的数组 Object[] elements getArray(); //获取该数组的长度这是一个伏笔同时1en也是新数组的最后一个元素的索引值 int len elements.length; //将当前数组拷贝一份的同时让其长度加1 Object[] newElements Arrays.copyof(elementslen 1); //将加入的元素放在新数组最后一位1en不是旧数组长度吗为什么现在用它当成新数组的最后一个元素的 newElements[len]e; //替换引用将数组的引用指向给新数组的地址 setArray(newElements); return true; }finally { // 释放锁 lock.unlock(); } }看到源码可以知道写入新元素时首先会先将原来的数组拷贝一份并且让原来数组的长度1后就得到了一个新数组新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度然后将新加入的元素放置都在新数组最后一个位置后用新数组的地址替换掉老数组的地址就能得到最新的数据了。在我们执行替换地址操作之前读取的是老数组的数据数据是有效数据执行替换地址操作之后读取的是新数组的数据同样也是有效数据而且使用该方式能比读写都加锁要更加的效率。现在我们来看读操作读是没有加锁的所以读是一直都能读public E get(int index){ return get(getArray(),index); }11. List里面填基本数据类型为什么会报错List等泛型集合类要求填充的必须是引用类型对象类型而不能直接使用基本数据类型如int、char、double等否则会编译报错。这是因为Java的泛型机制在设计时就只支持引用类型不支持基本数据类型。// 错误示例List中直接使用基本数据类型int Listint listnewArrayList()//编译报错 // 解决的办法是使用基本数据类型对应的包装类。 //正确示例使用包装类Integer ListInteger list new ArrayList(); list.add(10)//自动装箱:int-Integer int num list.get(e); //自动拆箱:Integer -int这么设计的原因是泛型的类型擦除机制Java泛型在编译后会被擦除为object类型而object只能接收引用类型不能接收基本数据类型历史原因Java最初设计时基本数据类型和引用类型是严格区分的泛型是后期UDK1.5才引入的特性为了兼容已有的类型系统选择只支持引用类型。通过使用包装类结合Java的自动装箱基本类型→包装类和自动拆箱包装类→基本类型机制可以很方便地在泛型集合中操作基本数据类型的数据12. List和数组如何互转1List 转数组主要有两种方式核心是用List 的toArray()方法重点注意泛型和类型匹配① 无参toArray()(返回 Object []不推荐ListString strList new ArrayList(); strList.add(a); strList.add(b); //返回object[]强转可能报错 Object[] objArr strList.toArray();这种方式返回的是Object数组若强转成String[]会抛ClassCastException仅适合不确定数组类型的场景基本不用。② 带参toArrayT[] a(推荐指定类型ListString strList new ArrayList(); strList.add(a); strList.add(b); ​ //方式1传入指定长度的数组 String[] strArr1 strList.toArray(new String[strList.size()]); //方式2传入空数组JDK1.8更高效 String[] strArr2 strList.toArray(new String[e]); //自定义对象List转数组 ListUser userList new ArrayList(); userList.add(new User(张三20)) User[] userArr userList.toArray(new User[θ]);这是最常用的方式传入对应类型的数组List会把元素复制到该数组中若传入的数组长度不足会自动创建新数组推荐传空数组UDK会优化长度。2数组转 List核心是用Arrays.asList()但要注意返回的 List不可变和基本类型数组的坑① 普通对象数组转List(常用String[] strArr {abc}; //返回固定大小的List属于Arrays内部类不可add/remove) ListString strList1Arrays.asList(strArr); ​ //若需要可变List包装一层ArrayList ListString strList2 new ArrayList(Arrays.asList(strArr)): strList2.add(d)// 正常执行Arrays.asList() 返回的 List 不是 ArrayList而是Arrays的内部类不支持添加/删除操作想修改就套一层 ArrayList。② 基本类型的数组转List(避坑//错误示例int[]转List会变成Listint[]而非ListInteger int[] numArr {12,3}; Listint[] wrongList Arrays.asList(numArr); ​ //正确方式1手动装箱JDK8- ListInteger numList1 new ArrayList(); for (int num: numArr{ numList1.add(num); } ​ //正确方式2Stream流JDK8 ListInteger numList2 Arrays.stream(numArr).boxed().collect(Collectors.toList());基本类型数组(int[]、long[]直接用Arrays.asList()会把整个数组当成一个元素必须手动装箱或用Stream流转换为包装类(Integer) 的 List。