Collection

title: 集合

ArrayList、LinkedList区别

• ArrayList：有序可重复；查找和访问元素的速度快，新增、删除的速度慢。线程不安全，使⽤频率⾼。

ArrayList底层结构是数组，查询数据时可根据索引直接查找，增删慢的原因是增删元素时牵扯到整体数据的左移或右移

• LinkedList：无序不可重复；查找和访问元素的速度慢，新增、删除的速度快。

原因：LinkedList底层结构是双向链表 ， 链表的元素的内存空间可以不连续；

随机访问慢（要沿着链表遍历） 头尾插入删除性能高

ArrayList线程不安全，为什么还要去⽤？

实际开发中有以下⼏种场景：

• 频繁增删：使⽤LinkedList，但是涉及到频繁增删的场景不多

• 追求线程安全：使⽤Vector。

• 普通的⽤来查询：使⽤ArrayList，使⽤的场景最多。

根据数据结构的特性，三者难以全包含，只能在相互之间做取舍。

ArrayList底层是数组，那是怎么实现不断扩容的？

初始化时是一个空的数组；当第一次添加元素时，默认容量为：10；

当新增元素，ArrayList放不下该元素时，触发扩容 。

底层执行一个叫做grow的方法，扩容后的容量是原来容量的1.5倍。

如何遍历ArrayList集合，并安全删除其中的元素？

1、遍历ArrayList集合有三种方式

(1)for循环  ==>倒序遍历
(2)增强for循环，也就是foreach
(3)迭代器iterator  ==> iteraror.remove()方法

2、普通for循环遍历删除元素，list集合的大小会变小，而索引也会发生改变，所以利用f
for循环遍历删除元素会漏调某些元素。
例如我for循环遍历删除第一个元素，接着按照索引去寻找第二个元素，由于删除的关系
后面所有的元素都会往前面移动一位，就会导致按照索引得到的是第三个元素。
解决方法：将list集合反过来遍历，循环删除其中的元素

当我们使用增强for循环删除第一个元素后，再去遍历list集合，此时就会报并发修改错
（concurrentModificationException异常）。
通过查看list的remove方法的源码，我们可以看到，remove方法中有一个modCount++操作，
然后再list集合的迭代器中有一个check操作，也就是检查modCount是否改变，如果改变
就会抛出并发修改错误。
解决方法：增强for循环遍历删除第一个元素后就break跳出。

使用迭代器循环遍历删除某些元素，不会出现问题，但是我们要注意的是，使用的是
iteraror.remove()方法，而不是list.remove()方法；如果使用的是list的remove方法，
同样会报conCurrentModificationbException异常
3、总结
如果是遍历删除list集合中某个特定的元素，使用这三个遍历方式都可以。
如果要循环遍历删除多个元素，最好使用迭代器。其次使用普通for循环反过来遍历list集合

ArrayList

ArrayList增删慢，查询快 和LinkedList增删快，查询慢 的原因

ArrayList 和Vector 都是数组存储方式，都是查询快，增删慢，性能比ArrayList差，但是Vector 使用synchronized 方法（线程安全）

ArrayList
查询快:
ArrayList底层是数组结构，在查询过程中，可以利用数组+下标方式，直接获取元素对应的内存地址，CPU直达！！！
效率极高

增删慢：
1.增删都是基于下标位置添加元素，数组中的元素都会向前或向后移动，移动过程浪费时间。
2.增加或删除可能触发数组的缩容或阔容操作，创建新数组，销毁原数组，需要时间
ArrayList集合结构
常用于查询多，增删少的结构。
例如:
商家的商品存储数据，图书馆的图书，员工管理系统
搜索，排序，过滤…

LinkedList
双向链表结构
由Node 组成，

增删快

1在双向链表中插入or删除元素不需要移动元素，只需要改变相关元素的头尾指针即可。

查询慢
根据传入的index去判断是否为LinkedList中的元素，判断逻辑为index是否在0和size之间，如果在则调用node(index)方法，否则抛出
调用node(index)方法，将size右移1位，即size/2，判断传入的size在LinkedList的前半部分还是后半部分
如果在前半部分，即index < size/2，则从fisrt节点开始遍历匹配
如果在后半部分，即index > size/2，则从last节点开始遍历匹配
可以看出，如果LinkedList链表size越大，则遍历的时间越长，查询所需的时间也越长。