IT老哥,一个在大厂做高级Java开发的程序员,每天分享技术干货文章
数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。
随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。
增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。
综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。
ArrayList和LinkedList都实现了List接口,他们有以下的不同点: ArrayList是基于索引的数据接口,它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n)。 相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者是更新索引。 LinkedList比ArrayList更占内存,因为LinkedList为每一个节点存储了两个引用,一个指向前一个元素,一个指向下一个元素。
线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。
性能:ArrayList 在性能方面要优于 Vector。
扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。
三、 ArrayList 的扩容机制是什么?
ArrayList是List接口的实现类,它是支持根据需要而动态增长的数组。java中标准数组是定长的,在数组被创建之后,它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度,但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的。
因此,了解它的扩容机制对使用它尤为重要。
ArrayList扩容发生在add()方法调用的时候,下面是add()方法的源码:
public boolean add(E e) {
//扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
根据意思可以看出ensureCapacityInternal()是用来扩容的,形参为最小扩容量,进入此方法后:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
通过方法calculateCapacity(elementData, minCapacity)获取:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
ensureExplicitCapacity方法可以判断是否需要扩容:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需要空间比elementData的内存空间要大,则需要扩容
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
接下来重点来了,ArrayList扩容的关键方法grow():
private void grow(int minCapacity) {
// 获取到ArrayList中elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再判断一下新数组的容量够不够,够了就直接使用这个长度创建新数组,
// 不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若预设值大于默认的最大值检查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
// 并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。
到此扩容就基本完成了。
四:Array 和 ArrayList 区别?
Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。
Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。
Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
五、快速失败(fail-fast)和安全失败(fail-safe)的区别?
Iterator的安全失败是基于对底层集合做拷贝,因此,它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败的,而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常,而安全失败的迭代器永远不会抛出这样的异常。
六、10.Iterater和ListIterator之间有什么区别?
(1)我们可以使用Iterator来遍历Set和List集合,而ListIterator只能遍历List。
(2)Iterator只可以向前遍历,而LIstIterator可以双向遍历。
(3)ListIterator从Iterator接口继承,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。
七、LinkedList 底层结构
LinkedList是基于双向循环链表实现的,除了可以当作链表操作外,它还可以当作栈、队列和双端队列来使用。LinkedList同样是非线程安全的,只在单线程下适合使用。
云服务器,云硬盘,数据库(包括MySQL、Redis、MongoDB、SQL Server),CDN流量包,短信流量包,cos资源包,消息队列ckafka,点播资源包,实时音视频套餐,网站管家(WAF),大禹BGP高防(包含高防包及高防IP),云解析,SSL证书,手游安全MTP,移动应用安全、 云直播等等。
ArrayList的底层数据结构就是一个数组,数组元素的类型为Object类型,对ArrayList的所有操作底层都是基于数组的。默认容量是10