[Java] 阿里一面~说一下ArrayList 与 LinkedList 区别

简介: [Java] 阿里一面~说一下ArrayList 与 LinkedList 区别


是否保证线程安全

ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;

底层数据结构

● ArrayList 底层使用的是 Object 数组;

● LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)

双向链表: 包含两个指针,一个 prev 指向前一个节点,一个 next 指向后一个节点。

双向循环链表: 最后一个节点的 next 指向 head,而 head 的 prev 指向最后一个节点,构成一个环。

插入和删除是否受元素位置的影响

● ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。

● LinkedList 采用链表存储,所以,如果是在头尾插入或者删除元素不受元素位置的影响,时间复杂度 O(1),如果是要在指定位置 i 插入和删除元素的话, 时间复杂度为 O(n) ,因为需要先移动到指定位置再插入。

是否支持快速随机访问

● LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。

快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

内存空间占用:

● ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间;

● 而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

注意: 文章内容属于站在巨人的肩膀进行输出~

相关文章
|
1天前
|
Java 索引 容器
Java ArrayList扩容的原理
Java 的 `ArrayList` 是基于数组实现的动态集合。初始时,`ArrayList` 底层创建一个空数组 `elementData`,并设置 `size` 为 0。当首次添加元素时,会调用 `grow` 方法将数组扩容至默认容量 10。之后每次添加元素时,如果当前数组已满,则会再次调用 `grow` 方法进行扩容。扩容规则为:首次扩容至 10,后续扩容至原数组长度的 1.5 倍或根据实际需求扩容。例如,当需要一次性添加 100 个元素时,会直接扩容至 110 而不是 15。
Java ArrayList扩容的原理
|
5天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
5天前
|
Java
Java代码解释++i和i++的五个主要区别
本文介绍了前缀递增(++i)和后缀递增(i++)的区别。两者在独立语句中无差异,但在赋值表达式中,i++ 返回原值,++i 返回新值;在复杂表达式中计算顺序不同;在循环中虽结果相同但使用方式有别。最后通过 `Counter` 类模拟了两者的内部实现原理。
Java代码解释++i和i++的五个主要区别
|
13天前
|
Java
通过Java代码解释成员变量(实例变量)和局部变量的区别
本文通过一个Java示例,详细解释了成员变量(实例变量)和局部变量的区别。成员变量属于类的一部分,每个对象有独立的副本;局部变量则在方法或代码块内部声明,作用范围仅限于此。示例代码展示了如何在类中声明和使用这两种变量。
|
15天前
|
安全 Java 程序员
Java集合之战:ArrayList vs LinkedList,谁才是你的最佳选择?
本文介绍了 Java 中常用的两个集合类 ArrayList 和 LinkedList,分析了它们的底层实现、特点及适用场景。ArrayList 基于数组,适合频繁查询;LinkedList 基于链表,适合频繁增删。文章还讨论了如何实现线程安全,推荐使用 CopyOnWriteArrayList 来提升性能。希望帮助读者选择合适的数据结构,写出更高效的代码。
43 3
|
16天前
|
Java
Java代码解释静态代理和动态代理的区别
### 静态代理与动态代理简介 **静态代理**:代理类在编译时已确定,目标对象和代理对象都实现同一接口。代理类包含对目标对象的引用,并在调用方法时添加额外操作。 **动态代理**:利用Java反射机制在运行时生成代理类,更加灵活。通过`Proxy`类和`InvocationHandler`接口实现,无需提前知道接口的具体实现细节。 示例代码展示了两种代理方式的实现,静态代理需要手动创建代理对象,而动态代理通过反射机制自动创建。
|
存储 安全 Java
LinkedList源码解读—Java8版本(上)
LinkedList源码解读—Java8版本(上)
161 0
LinkedList源码解读—Java8版本(上)
|
Java
LinkedList源码解读—Java8版本(下)
LinkedList源码解读—Java8版本(下)
132 0
|
存储 Java
LinkedList源码解读—Java8版本(中)
LinkedList源码解读—Java8版本(中)
125 0
|
8天前
|
安全 Java
java 中 i++ 到底是否线程安全?
本文通过实例探讨了 `i++` 在多线程环境下的线程安全性问题。首先,使用 100 个线程分别执行 10000 次 `i++` 操作,发现最终结果小于预期的 1000000,证明 `i++` 是线程不安全的。接着,介绍了两种解决方法:使用 `synchronized` 关键字加锁和使用 `AtomicInteger` 类。其中,`AtomicInteger` 通过 `CAS` 操作实现了高效的线程安全。最后,通过分析字节码和源码,解释了 `i++` 为何线程不安全以及 `AtomicInteger` 如何保证线程安全。
java 中 i++ 到底是否线程安全?