本文共 1436 字，大约阅读时间需要 4 分钟。
1. ArrayList和LinkedList的区别
ArrayList和LinkedList是Java中常用的双端列表数据结构，主要区别体现在以下几个方面：
线程安全
- ArrayList和LinkedList都不是线程安全的，在多线程环境下使用时，需要手动加锁保护。
底层数据结构
- ArrayList采用数组实现，支持随机访问，特点是内存空间的浪费较小。
- LinkedList采用双向链表实现，节点之间仅有指针连接，不需要大块的内存空间。
插入和删除效率
- ArrayList基于数组实现插入和删除操作，在尾插/尾删除时复杂度为O(1)，但索引插/删除时需要O(N)时间。
- LinkedList基于链表实现，插入和删除操作均为O(1)，不受元素位置影响。
随机访问效率
- ArrayList支持随机访问，通过索引直接获取元素，时间复杂度为O(1)。
- LinkedList不支持随机访问，访问某个元素需从头遍历起始节点，时间复杂度为O(N)。
扩容机制
- ArrayList初始化时可指定大小，默认为10，当元素添加超过容量时，会扩容到原有容量的1.5倍。
- LinkedList无固定初始容量，不需要扩容，操作更为灵活。
内存占用
- ArrayList内存占用较低，主要浪费在数组的连续空间上。
- LinkedList每个节点存储两个指针，内存占用较高。
适用场景
- 如果需要频繁进行随机访问或规模较大（百万级别以上），应选择ArrayList。
- 如果需要高效的插入和删除操作，或不介意较慢的随机访问，LinkedList更为合适。
2. 顺序表与单链表的区别
顺序表与单链表是两种最基础的线性数据结构，它们的存储方式和操作方式存在显著差异。
存储方式
- 顺序表：数据存储为一连串的块，采用索引直接存取，支持快速随机访问。
- 链表：数据以相对指针的形式连接，每个节点包含指向下一个节点的引向，无连续内存占用。
优缺点对比
顺序表优点
空间利用率高：基于局部性原理，数据按区间连续存储。 存取效率高：通过固定的索引直接存取数据。 顺序表缺点
插入和删除效率低：需要移动大量数据，复杂度为O(N)。 固定容量限制：难以扩展，存储空间受连续内存影响。 链表优点
插入和删除效率高：操作仅需改动指针，时间复杂度为O(1)。 灵活扩展：无需预先分配空间，按需扩展。 链表缺点
空间浪费：每个节点需额外存储指向节点的指针。 访问效率低：需从头节点逐一遍历，查找复杂度为O(N)。 时间复杂度对比
- 顺序表：查找O(1)，插入和删除O(N)。
- 链表：查找O(N)，插入和删除O(1)。
3. 数组与链表的区别
数组和链表是同一类线性数据结构的两种实现形式，主要区别在于存储方式和操作机制。
数组特点
存储方式：内存中连续占用一块空间，需预先申请内存大小。 插入删除效率：插入和删除需移动大量元素，效率较低。 扩展困难：数组大小需预先确定，扩展需重新定义数组。 随机访问效率高：通过索引快速访问元素。 链表特点
存储方式：数据块不需连续，通过指针连接。 插入删除效率高：操作仅需调整指针，无需移动元素。 扩展灵活：按需申请内存，无需预先确定大小。 随机访问效率低：需从头节点逐一遍历。 优缺点对比
数组优点
随机访问效率高。 查找速度快。 数组缺点
插入和删除效率低。 代码复杂度高。 可能较大的内存浪费和预留空间。 链表优点
插入和删除效率高。 内存利用率高。 链表缺点
随机访问效率低。 查找速度较慢。 转载地址：http://zlanz.baihongyu.com/