在 Java 中，数组（Array）和链表（LinkedList）是两种常见的数据结构，它们在存储和操作方式上有显著的区别。了解它们的差异有助于选择适合特定应用场景的结构。下面是数组和链表之间的详细比较。
1. 存储结构
数组（Array）
- 连续内存空间：数组在内存中是一个连续的块，所有元素依次存储在一起。
- 固定大小：数组的大小在创建时就确定，不能动态调整。创建后不能改变大小（除非重新创建数组并拷贝内容）。
- 索引访问：数组支持通过索引直接访问任意位置的元素，时间复杂度为 O(1)。
链表（LinkedList）
- 非连续内存：链表中的元素（节点）并不保存在连续的内存位置。每个节点包含一个数据部分和一个指向下一个节点的引用（对于双向链表，还有指向前一个节点的引用）。
- 动态大小：链表的大小可以动态变化，不需要预先指定大小。可以在运行时不断添加或删除节点。
- 逐步访问：访问链表中的元素需要从头节点开始，逐一遍历节点，直到找到目标元素。时间复杂度是 O(n)，其中 n 是链表的长度。
2. 内存使用
数组
- 内存分配：数组一次性分配连续的内存空间，内存效率较高。但如果数组大小太大，可能会浪费空间；如果大小过小，则可能需要重新分配新的更大数组。
- 固定大小：一旦数组的大小固定后，就无法扩展。如果数组大小不够，需要创建一个新的数组并将数据复制到新数组中。
链表
- 内存分配：链表的每个节点都是单独分配内存的，因此内存使用更加灵活。每次新增元素时，只需要分配一个节点的内存。
- 节点开销：每个节点除了存储数据外，还需要存储指向其他节点的引用，因此链表的内存开销比数组大，尤其是双向链表需要存储两个引用（前向引用和后向引用）。
3. 时间复杂度
数组
- 访问元素：由于数组支持通过索引直接访问元素，访问时间是常数时间，O(1)。
- 插入和删除：
- 在数组的 末尾 插入或删除元素时间复杂度是 O(1)。
- 在数组的 中间 插入或删除元素时，需要移动后续的元素，时间复杂度是 O(n)。
链表
- 访问元素：需要从头节点开始遍历，逐个节点查找目标元素，时间复杂度是 O(n)。
- 插入和删除：
- 在链表的 头部 插入或删除元素时间复杂度是 O(1)。
- 在链表的 中间 或 末尾 插入或删除元素也可以在 O(1) 时间完成，但需要先找到目标位置，找到位置的时间复杂度是 O(n)。
4. 使用场景
数组
-
优点：
- 直接的索引访问非常高效，适用于查找操作频繁的场景。
- 存储连续的元素，内存管理较简单。
- 适合元素个数已知且不经常变动的场景。
-
缺点：
- 大小固定，扩展困难（需要重新分配更大的数组）。
- 插入和删除操作较慢，特别是中间的插入和删除，需要大量元素移动。
- 随着元素增多，可能会浪费内存。
链表
-
优点：
- 动态大小，能方便地进行插入和删除操作，尤其是在头部或尾部插入删除。
- 不需要预先分配固定大小，内存使用更加灵活。
-
缺点：
- 访问速度较慢，需要逐一遍历节点，不能像数组那样通过索引直接访问。
- 每个节点需要额外存储指向下一个节点的引用，增加了内存开销。
5. 代码示例
数组示例
public class ArrayExample {public static void main(String[] args) {// 创建一个大小为 5 的数组int[] arr = new int[5];// 向数组中添加元素arr[0] = 10;arr[1] = 20;arr[2] = 30;arr[3] = 40;arr[4] = 50;// 通过索引访问元素System.out.println("Element at index 2: " + arr[2]);// 插入元素时需要重新分配数组（手动管理）}
}
链表示例（使用 LinkedList 类）
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建一个 LinkedListLinkedList<Integer> linkedList = new LinkedList<>();// 向链表中添加元素linkedList.add(10);linkedList.add(20);linkedList.add(30);// 访问链表中的元素System.out.println("First element: " + linkedList.get(0));// 插入元素linkedList.addFirst(5); // 在链表的头部插入元素linkedList.addLast(40); // 在链表的尾部插入元素System.out.println("Linked list: " + linkedList);// 删除元素linkedList.removeFirst(); // 删除头部元素linkedList.removeLast(); // 删除尾部元素System.out.println("After deletion: " + linkedList);}
}
6. ArrayList 和 LinkedList 的比较（Java 视角）
在 Java 中，ArrayList 和 LinkedList 都实现了 List 接口，但它们在底层实现上有所不同。ArrayList 使用数组作为存储结构，而 LinkedList 使用双向链表。
-
ArrayList：
- 支持通过索引快速访问元素。
- 插入和删除元素的时间复杂度通常为 O(n)，特别是在中间位置。
-
LinkedList：
- 支持快速的插入和删除，特别是在头部或尾部。
- 访问元素时需要遍历链表，访问时间较慢。
7. 总结
| 特性 | 数组（Array） | 链表（LinkedList） |
|---|---|---|
| 存储结构 | 连续的内存空间 | 每个节点包含数据和指向下一个节点的引用 |
| 大小 | 固定大小 | 动态大小 |
| 访问效率 | 快速 O(1) | 需要遍历，O(n) |
| 插入/删除效率 | 中间插入/删除 O(n)，尾部 O(1) | 插入/删除 O(1)（头尾），查找 O(n) |
| 内存管理 | 静态分配，可能浪费空间 | 节点动态分配，内存使用灵活 |
| 使用场景 | 查找操作频繁，大小已知且不变的场景 | 插入/删除频繁，元素动态变化的场景 |
选择使用数组还是链表，取决于具体应用场景。如果需要频繁的随机访问，数组是更好的选择。如果需要频繁的插入和删除操作，链表会更高效。
小伙伴们在开发过程中有使用心得可以再评论区一块讨论
