常见集合篇（二）数组、ArrayList与链表：原理、源码及业务场景深度解析

常见集合篇（二）数组、ArrayList与链表：原理、源码及业务场景深度解析

1. 数组

1.1 数组概述

1.1.1 数组的定义与特点

数组是线性数据结构，在内存中占据连续空间，存储相同类型元素。核心特点：

• 随机访问高效：通过索引定位元素，时间复杂度O(1)。
• 插入/删除复杂：可能移动后续元素，时间复杂度O(n)。

1.1.2 业务场景举例

• 电商商品信息存储：电商用double[] productPrices存储商品价格，通过索引快速获取价格，如productPrices[100]。
• 游戏角色属性管理：游戏中int[] roleAttributes存储角色属性（生命值、魔法值等），方便访问。

1.2 寻址公式

1.2.1 寻址公式原理

公式：address = base_address + index * data_type_size。用于计算数组元素内存地址。

1.2.2 业务场景举例

• 数据库索引底层实现：数据库索引数组，首地址1000，int类型（4字节），索引5的元素地址：1000 + 5 * 4 = 1020，快速定位数据。
• 图形渲染像素存储：图像像素数组，首地址2000，4字节/像素，索引10的像素地址依公式计算，显卡读取渲染。

1.3 操作数组的时间复杂度

1.3.1 查询操作

• 时间复杂度：O(1)。
• 业务场景：社交平台用int[] likeCounts存储动态点赞数，通过索引瞬间获取点赞数。

1.3.2 插入操作

• 时间复杂度：O(n)。
• 业务场景：教育平台课程章节数组，插入新章节需移动后续章节，时间随章节数增加。

1.3.3 删除操作

• 时间复杂度：O(n)。
• 业务场景：金融交易系统订单数组，删除订单需前移后续订单编号，操作时间与订单量相关。

2. ArrayList源码分析

2.1 成员变量

2.1.1 核心成员变量

• elementData：存储元素的数组。
• size：记录元素数量。
• DEFAULT_CAPACITY：默认容量10。

2.1.2 业务场景举例

• 新闻资讯APP：ArrayList<News> newsList存储新闻，size记录新闻数，动态管理数据。

2.2 构造方法

2.2.1 无参构造方法

• 初始化为空数组，首次添加元素扩容。
• 业务场景：视频平台ArrayList<Video> cacheList，初始无数据，后续缓存视频。

2.2.2 指定容量构造方法

• 预分配空间，避免频繁扩容。
• 业务场景：电商促销ArrayList<PromotionProduct> productList = new ArrayList<>(50)，预加载50款商品。

2.2.3 集合构造方法

• 转换其他集合数据。
• 业务场景：社交平台ArrayList<User> friendList = new ArrayList<>(Arrays.asList(oldFriendArray))，迁移好友数据。

2.3 ArrayList源码分析

2.3.1 添加元素源码

• 容量不足时，新容量为旧的1.5倍，Arrays.copyOf复制元素。
• 业务场景：外卖平台订单ArrayList，第11单触发扩容，确保订单存储。

2.3.2 获取元素源码

• get(int index)直接返回元素，O(1)。
• 业务场景：在线教育Homework homework = homeworkList.get(studentIndex)，快速获取学生作业。

2.3.3 删除元素源码

• 移动后续元素，置空尾元素防内存泄漏。
• 业务场景：旅游平台删除订单，后续订单前移，保持编号逻辑。

2.4 面试题：ArrayList list = new ArrayList(10); 的扩容几次？

2.4.1 原理分析

初始容量10，第11个元素触发扩容为15，后续依1.5倍扩容。

2.4.2 业务场景举例

• 电商秒杀ArrayList<SeckillProduct> productList，首次扩容在添加第11个商品时，支撑活动商品展示。

2.5 面试题：数组和List转换

2.5.1 数组转List

• Arrays.asList()，需再包装为ArrayList以支持增删。
• 代码：Integer[] array = {1, 2, 3}; List<Integer> list = new ArrayList<>(Arrays.asList(array));
• 场景：金融系统将数据库查询数组转为List，便于业务处理。

2.5.2 List转数组

• toArray()指定数组类型。
• 代码：List<Integer> list = new ArrayList<>(); Integer[] array = list.toArray(new Integer[0]);
• 场景：游戏开发将角色List转数组，适配渲染引擎。

3. 链表

3.1 单向链表

3.1.1 结构

节点含数据域和指向下一节点的指针，头节点入口，尾节点指针为null。

3.1.2 业务场景举例

• 消息队列：即时通讯APP消息发送队列，新消息添加到尾部，按顺序发送。
• 浏览器历史记录：存储访问页面，回退时遍历链表。

3.2 单向链表时间复杂度

3.2.1 查询操作：O(n)

• 场景：物流配送路线查询站点，需遍历链表。

3.2.2 插入操作：O(1)（已知前节点）

• 场景：音乐播放列表插入歌曲，修改前节点指针。

3.2.3 删除操作：O(1)（已知节点）

• 场景：任务管理系统删除任务，跳过目标节点。

3.3 双向链表

3.3.1 结构

节点含前驱、后继指针，可双向遍历。

3.3.2 业务场景举例

• 电商购物车：调整商品顺序，双向指针支持前后移动。
• 操作系统内存管理：内存块分配回收，双向链表快速定位合并。

3.4 双向链表时间复杂度

3.4.1 查询操作：O(n)

• 场景：图书馆检索书籍，可能遍历全表。

3.4.2 插入操作：O(1)（已知节点）

• 场景：社交平台插入好友，修改前后节点指针。

3.4.3 删除操作：O(1)（已知节点）

• 场景：视频平台剪辑片段，跳过删除片段。

3.5 面试题：ArrayList和LinkedList的区别

3.5.1 存储结构

• ArrayList：连续内存，数组存储。
• LinkedList：非连续内存，节点连接。
• 场景对比：相册图片，随机访问多用ArrayList；动态编辑多用LinkedList。

3.5.2 查询操作

• ArrayList：O(1)。
• LinkedList：O(n)。
• 场景对比：股票系统实时股价，随机访问用ArrayList；顺序处理交易记录，LinkedList可满足。

3.5.3 插入/删除操作

• ArrayList：O(n)。
• LinkedList：O(1)（已知节点）。
• 场景对比：文本编辑器，插入删除频繁用LinkedList；代码编辑器跳转行，用ArrayList。

3.5.4 内存占用

• ArrayList：可能空间浪费（预分配）。
• LinkedList：节点指针占额外内存。
• 场景对比：嵌入式设备，数据稳定用ArrayList；动态变化大，权衡后选LinkedList。

通过对数组、ArrayList和链表的深入解析及业务场景实践，开发者可根据实际需求选择数据结构，优化程序性能，为电商、社交、金融等领域的系统高效运行提供保障。