数组和链表的区别

数组（Array）和链表（Linked List）是两种基本的数据结构，主要区别在于 存储方式、访问方式、增删效率 和 内存分配：

• 数组：连续存储，随机访问快，增删慢。
• 链表：分散存储，增删快，访问慢。

关键区别

1. 存储方式

• 数组：
  • 内存连续分配，元素紧邻。
  • 示例：int[] arr = {1, 2, 3}。
• 链表：
  • 内存分散，节点通过指针（引用）连接。
  • 示例：Node { value=1, next=Node2 }。

2. 访问方式

• 数组：
  • 随机访问，通过索引直接定位，O(1)。
  • 示例：arr[2] 立即得到 3。
• 链表：
  • 顺序访问，从头遍历，O(n)。
  • 示例：找第 3 个元素，需遍历 1 → 2 → 3。

3. 增删效率

• 数组：
  • 插入/删除需移动元素，O(n)。
  • 示例：插入到 arr[1]，后移 2, 3。
• 链表：
  • 只改指针，O(1)（已知位置）。
  • 示例：插入到第 2 个节点，改 next 指针。

4. 内存分配

• 数组：
  • 固定大小（静态数组）或动态扩容（如 ArrayList），需预分配。
  • 示例：new int[10]。
• 链表：
  • 动态分配，按需添加节点，无需连续空间。
  • 示例：new Node()。

5. 空间利用

• 数组：
  • 无额外指针，空间紧凑。
  • 缺点：扩容浪费（如 ArrayList 翻倍）。
• 链表：
  • 每个节点存指针（4 或 8 字节），空间开销大。

延伸与面试角度

• 性能对比：
  • 查询：数组 O(1)，链表 O(n)。
  • 增删：数组 O(n)，链表 O(1)（定位后）。
• 适用场景：
  • 数组：频繁查询（如二分查找）。
  • 链表：频繁插入/删除（如队列）。
• 实际应用：
  • 数组：ArrayList，动态数组。
  • 链表：LinkedList，双向链表。
• 优缺点：
  • 数组：访问快，增删慢，内存连续。
  • 链表：增删快，访问慢，内存分散。
• 面试点：
  • 问“选择依据”时，提操作类型。
  • 问“内存差异”时，提连续 vs 分散。

总结

数组和链表区别在于存储（连续 vs 分散）、访问（随机 vs 顺序）、增删（慢 vs 快）和内存（固定 vs 动态）。数组适合查询，链表适合修改。面试时，可写简单代码或画结构图，展示理解深度。