黑马数据结构讲义

JavaJuice约 7915 字大约 26 分钟

021-动态数组-遍历

动态数组实现与遍历方法详解

一、测试添加方法

创建动态数组对象

DynamicArray dynamicArray = new DynamicArray();

添加元素测试

// 添加末尾元素测试
dynamicArray.addLast(1);
dynamicArray.addLast(2);
dynamicArray.addLast(3);
dynamicArray.addLast(4);
dynamicArray.addLast(5);

// 插入元素测试（在索引2处插入5）
dynamicArray.add(2, 5);

二、验证方法实现

get方法

public int get(int index) {
    return array[index];
}

• 测试方法：

for(int i=0; i<5; i++) {
    System.out.println(dynamicArray.get(i));
}

三、遍历方法实现

自定义forEach遍历

public void forEach(Consumer<Integer> consumer) {
    for(int i=0; i<size; i++) {
        consumer.accept(array[i]);
    }
}

• 测试使用：

dynamicArray.forEach(element -> System.out.println(element));

迭代器实现（实现Iterable接口）

public class DynamicArray implements Iterable<Integer> {
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public Integer next() {
                return array[i++];
            }
        };
    }
}

• 测试使用（增强for循环）：

for(Integer element : dynamicArray) {
    System.out.println(element);
}

Stream流处理

public IntStream stream() {
    return IntStream.of(Arrays.copyOfRange(array, 0, size));
}

• 测试使用：

dynamicArray.stream().forEach(element -> System.out.println(element));

四、关键实现细节

数据封装：通过private修饰符隐藏内部数据结构(array和size)
索引验证：实际开发中get方法应添加索引有效性检查

if(index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
}

泛型支持：示例使用Integer类型，实际可扩展为泛型类
内存优化：使用Arrays.copyOfRange避免暴露无效数组元素

五、测试结果验证

初始添加测试输出：1 2 3 4 5
插入元素后输出：1 2 5 3 4
三种遍历方式均能正确输出有效元素序列

六、设计原则

封装性：隐藏内部数据存储细节
扩展性：通过多种遍历方式满足不同需求
函数式编程：使用Consumer接口实现回调机制
标准接口实现：通过Iterable支持增强for循环

注意事项：
实际实现需添加空指针检查和边界检查
迭代器实现要考虑并发修改异常处理
流式处理可根据需求选择IntStream或Stream<Integer>

022-动态数组-删除

动态数组删除方法实现文档

方法概述

方法签名：public int remove(int index)
功能说明：删除指定索引位置的元素，并返回被删除元素的值
核心特性：
• 时间复杂度 O(N)
• 假设调用者保证索引有效性（0 ≤ index < size）
• 支持删除最后一个元素的优化处理

实现步骤

返回值处理
• 获取被删除元素：int removed = array[index]
元素移动逻辑

if (index < size - 1) {
    System.arraycopy(
        array,        // 源数组
        index + 1,    // 源起始位置
        array,        // 目标数组
        index,        // 目标起始位置
        size - index - 1 // 移动元素个数
    );
}

说明：当删除非末尾元素时，将后续元素向前移动一个位置

容量调整
• size-- 更新有效元素计数器

测试验证
测试用例

// 初始化数组 [1,2,3,4,5]
DynamicArray array = new DynamicArray();
for (int i = 1; i <= 5; i++) {
    array.addLast(i);
}

// 删除索引2的元素
int removed = array.remove(2);

断言验证

返回值验证：

assertEquals(3, removed);

剩余元素验证：

assertIterableEquals(
    List.of(1, 2, 4, 5),  // 期望值
    array                  // 实际值（需实现Iterable接口）
);

优化处理
末尾元素删除优化：
• 增加判断条件 if (index < size - 1)

• 当删除最后一个元素时（index == size-1），跳过数组拷贝操作

• 减少不必要的系统调用，提升性能

注意事项

索引有效性：调用者需保证传入合法索引，方法内部不做校验
容量变化：删除操作会永久丢失原末尾元素的引用（可能影响内存回收）
并发安全：非线程安全实现，多线程环境需自行同步

复杂度分析
• 时间复杂度：O(N)（最坏情况下需要移动size-1个元素）

• 空间复杂度：O(1)（原地操作，无需额外空间）

扩展思考

如何实现批量删除操作？
如果要求实现索引有效性检查，应如何处理非法参数？
如何实现环形缓冲区来优化频繁删除/插入操作？

023-动态数组-扩容

动态数组扩容机制详解

一、容量检查与扩容逻辑
1.1 触发条件
• 当数组元素个数（size）等于当前容量（capacity）时触发扩容

• 示例：原始容量为8的数组已存储8个元素时，继续添加需扩容

1.2 扩容策略

扩容倍数：采用Java标准库实现方式，新容量 = 旧容量 × 1.5
实现方式：

int newCapacity = oldCapacity + (oldCapacity >> 1); // 右移一位等价于除以2

1.3 扩容步骤

创建新容量数组

int[] newArray = new int[newCapacity];

复制旧数组元素

System.arraycopy(oldArray, 0, newArray, 0, size);

更新数组引用

array = newArray;
capacity = newCapacity;

二、代码结构优化
2.1 方法抽取
将容量检查逻辑封装为独立方法：

private void checkAndGrow() {
    if (size == 0) {         // 首次扩容
        array = new int[INITIAL_CAPACITY];
        capacity = INITIAL_CAPACITY;
    } else if (size == capacity) {  // 常规扩容
        int newCapacity = capacity + (capacity >> 1);
        int[] newArray = new int[newCapacity];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
        capacity = newCapacity;
    }
}

2.2 延迟初始化优化
• 初始状态：数组引用为空（null）

• 首次添加元素时创建初始容量数组（默认8）

• 优点：减少内存占用，提升资源利用率

三、时间复杂度分析

操作类型	时间复杂度	说明
按索引查询	O(1)	直接地址访问
按值查询	O(n)	需要遍历比较
尾部插入	均摊 O(1)	可能触发扩容但概率较低
头部/中部插入	O(n)	需要移动后续元素
删除操作	O(n)	需要移动后续元素

四、扩容策略对比

策略类型	扩容倍数	优点	缺点
固定增量	+1	内存利用率高	频繁扩容性能差
翻倍策略	×2	扩容次数少	内存浪费较大
1.5倍策略	×1.5	平衡内存与性能	计算稍复杂
黄金分割策略	×1.618	数学最优比例	实现复杂度高

五、测试验证
5.1 测试用例

DynamicArray array = new DynamicArray();
for (int i = 0; i < 9; i++) {
    array.add(i + 1);
}

5.2 预期结果

初始容量：0（空数组）
第一次添加：扩容至8
第九次添加：扩容至12（8 × 1.5）
最终元素：[1,2,3,4,5,6,7,8,9]

六、最佳实践建议

预估容量：在已知数据量时预设初始容量避免多次扩容
批量添加：优先使用批量添加方法减少扩容检查次数
内存敏感场景：考虑使用trimToSize()释放未使用空间
线程安全：多线程环境需配合同步机制使用

七、扩展思考

缩容策略：当元素减少到某个阈值时自动缩小容量
泛型支持：改造为泛型数组增强类型安全性
迭代器实现：支持foreach循环语法
并发版本：实现线程安全的CopyOnWriteArrayList机制

[图示说明]
扩容过程示意图：
旧数组：[1][2][3][4][5][6][7][8]（capacity=8）
新数组：[1][2][3][4][5][6][7][8][ ][ ][ ][ ]（capacity=12）

024-二维数组

Java二维数组详解

一、二维数组声明语法

基本语法结构：

数据类型[][] 变量名;

• 示例：int[][] array; 表示声明一个存储int类型元素的二维数组

• 数组元素类型决定存储数据的类型，两个中括号[][]表示二维数组

二、二维数组赋值方式

初始化语法：

int[][] array = {
    {1,1,1,2,1},
    {3,1,4,5,2},
    {5,9,6,7,3}
};

• 外层花括号包含整个二维数组

• 内层三对花括号分别表示三个一维数组

• 每个内层数组存储具体元素值

三、二维数组内存布局

结构组成
• 外层数组：存储内层数组的引用地址

• 内层数组：实际存储数据元素

内存分配示例
数组结构：

int[][] array = new int[3][5];

内存布局：

+---------------------+
| 外层数组（长度3）     |
|---------------------|
| Mark Word (8B)      |
| Class Pointer (4B)  |
| 数组长度3 (4B)       |
| [0] → 内层数组1地址   |
| [1] → 内层数组2地址   |
| [2] → 内层数组3地址   |
| 对齐填充 (4B)        |
+---------------------+
    ↓
+---------------------+
| 内层数组（长度5）     |
|---------------------|
| Mark Word (8B)      |
| Class Pointer (4B)  |
| 数组长度5 (4B)       |
| [0] 元素值          |
| [1] 元素值          |
| [2] 元素值          |
| [3] 元素值          |
| [4] 元素值          |
| 对齐填充 (4B)        |
+---------------------+

内存占用计算
• 外层数组：

• 对象头：8B(Mark Word) + 4B(Class Pointer)

• 数组元数据：4B(长度)

• 元素存储：3个引用地址 × 4B = 12B

• 对齐填充：4B

• 总计：32B

• 单个内层数组：

• 对象头：8B + 4B

• 数组元数据：4B(长度)

• 元素存储：5个int × 4B = 20B

• 对齐填充：4B

• 总计：40B

四、元素访问方法

访问语法：

数组变量名[外层索引][内层索引]

定位示例：

// 访问元素25（假设位于第二行第五列）
int element = array[1][4];

• i=1：外层数组索引，对应第二行（索引从0开始）

• j=4：内层数组索引，对应第五个元素

五、核心概念总结

行式存储结构
• 外层数组每个元素对应一行数据

• 每行数据实际存储在内层数组中

引用关系
• 外层数组存储内层数组的引用地址

• 实际数据存储在内层数组的内存空间

内存连续性
• 所有数组对象在堆内存中连续存储

• 外层数组后紧跟内层数组的内存空间

索引机制
• 二维索引本质上是两次寻址过程

• 先定位行数组，再定位列元素

注：以上内存计算基于32位JVM未开启指针压缩的情况，实际使用中不同JVM实现可能有所差异。

025-数组-缓存与局部性原理

以下是根据课程录音整理并校正后的详细文档：

数组遍历效率与缓存局部性原理课程文档

一、实验背景
通过两个遍历二维数组的方法对比执行效率差异：
• 方法IJ：外层循环遍历行，内层循环遍历列

• 方法JI：外层循环遍历列，内层循环遍历行

1.1 代码示例

// 行优先遍历方法
public int IJ(int[][] A, int rows, int columns) {
    int sum = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += A[i][j];
        }
    }
    return sum;
}

// 列优先遍历方法
public int JI(int[][] A, int rows, int columns) {
    int sum = 0;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += A[i][j];
        }
    }
    return sum;
}

1.2 实验结果
• 相同数据量（10000行×10000列）下：

• IJ方法耗时：约13%总时间（约130ms）

• JI方法耗时：约87%总时间（约870ms）

• 结论：行优先遍历效率显著高于列优先遍历

二、核心原理分析

2.1 内存与CPU速度差异

组件	速度级别	时间单位换算
CPU运算	皮秒级	1皮秒 = 10⁻¹²秒
内存访问	纳秒级	1纳秒 = 10⁻⁹秒

速度差距：内存访问速度比CPU运算慢约1000倍

2.2 缓存机制
• 缓存行(Cache Line)：

• 数据读写最小单位（现代CPU多为64字节）

• 每次读取内存时，会将目标地址及相邻数据整块加载

• 空间局部性原理：

• 当程序访问某个内存地址时，很大概率会访问其邻近地址

• 缓存预加载机制基于此原理实现

2.3 效率差异关键分析

行优先遍历（IJ方法）优势

缓存友好型访问：
• 首次访问A[0][0]时，加载整行数据（如A[0][0]~A[0][13]共64字节）
• 后续访问A[0][1]~A[0][13]时直接从缓存读取
缓存行利用率：
• 单个缓存行可支撑14次连续访问（假设int为4字节）
• 缓存命中率高达93%（14/15）

列优先遍历（JI方法）劣势

缓存频繁失效：
• 访问A[0][0]后跳转至A[1][0]（间隔一整个行长度）
• 每次列跳转导致新缓存行加载
缓存污染：
• 当数据行数超过缓存容量时，旧缓存行被新数据覆盖
• 后续循环无法复用已加载数据

三、关键概念总结

3.1 多级缓存体系

缓存级别	容量	延迟
L1缓存	32-64KB	1ns
L2缓存	256KB-2MB	3ns
L3缓存	2-32MB	10ns

3.2 局部性原理类型

空间局部性：
• 本次实验中重点体现的原理
• 集中访问相邻内存地址提升缓存利用率
时间局部性：
• 被重复访问的数据应保留在缓存中
• 常见于循环变量、频繁调用的方法参数

四、编程实践建议

数据布局优化：
• 优先保证顺序内存访问模式
• 对多维数组采用行优先存储结构
循环结构设计：
• 外层循环控制高维数据
• 内层循环处理连续内存区域
数据块化处理：
• 将大数据集分割为缓存友好的数据块
• 典型应用：矩阵分块乘法、图像分块处理

文档已校正主要术语与技术细节，确保内容准确性。实验数据为示例值，实际结果可能因硬件配置不同有所差异。

026-链表-概述

数据结构课程文档：链表详解

一、链表定义
链表（Linked List）是数据元素的线性集合，每个元素（节点）通过指针指向下一个元素。核心特点：

非连续存储：节点在内存中不要求连续存放
指针连接：每个节点包含数据域和指针域
线性结构：与数组同属一维线性集合

与数组对比：

特性	数组	链表
存储方式	连续内存空间	非连续存储
随机访问	O(1)	O(n)
插入/删除	O(n)	O(1)（已知位置）

二、链表分类

单向链表
• 节点结构：数据域 + 1个指针（指向后继节点）

• 示例：12 → 99 → 37 → null

• 特点：只能单向遍历

双向链表
• 节点结构：数据域 + 2个指针（前驱/后继）

• 示例：null ↔ 12 ↔ 99 ↔ 37 ↔ null

• 特点：

• 双向遍历

• 额外内存开销（多存储前驱指针）

循环链表
• 单向循环：尾节点指向头节点形成环

• 双向循环：头尾节点相互链接

• 特点：无null终止符，需特殊遍历控制

三、节点结构

普通节点
• 组成要素：

class Node {
    E data;         // 数据域
    Node next;      // 后继指针（单向）
    Node prev;      // 前驱指针（双向）
}

哨兵节点（Sentinel/Dummy Node）
• 特殊用途节点，不存储实际数据

• 作用：

• 简化头/尾节点的边界条件处理

• 保持链表永不为空的特性

• 示例：哨兵头 → 12 → 99 → 37 → 哨兵尾

四、性能分析

随机访问
• 时间复杂度：O(n)

• 访问过程：必须从头节点开始顺序遍历

插入操作
• 已知位置（头/尾节点）：

• 单向链表头插：O(1)

• 双向链表尾插：O(1)

• 未知位置（中间节点）：

• 查找时间O(n) + 插入时间O(1) = O(n)

删除操作
• 时间复杂度与插入操作一致

• 核心操作：调整相邻节点的指针指向

五、操作复杂度对比

操作	数组	链表
随机访问	O(1)	O(n)
头插	O(n)	O(1)
尾插	O(1)	O(1)*
中间插入	O(n)	O(n)

*注：双向链表尾插为O(1)，单向链表需O(n)找尾节点

六、核心优势

动态内存管理：无需预分配固定空间
高效增删：已知位置时的O(1)操作
内存利用率：适合存储大小不固定的数据元素

七、典型应用场景
• 实现栈/队列等抽象数据类型

• 浏览器前进/后退导航

• 音乐播放列表

• 内存管理系统

• 图的邻接表表示

注：Java中的LinkedList类是基于双向链表的实现，提供高效的插入/删除操作。在实际开发中，应根据具体需求选择数组（ArrayList）或链表（LinkedList）实现。

027-单向链表-addFirst

以下是根据课程录音整理并校正后的详细技术文档：

单向链表（Singly Linked List）代码实现教程

一、类设计

节点类（Node）

/**
 * 链表节点内部类（静态）
 */
private static class Node {
    // 节点存储的整型值
    int value;
    // 指向下一节点的引用
    Node next;

    /**
     * 节点构造方法
     * @param value 节点存储的整数值
     * @param next  下一节点引用
     */
    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

链表类（SingleLinkedList）

/**
 * 单向链表实现类
 */
public class SingleLinkedList {
    // 头节点引用（初始为null）
    private Node head;

    // 其他链表操作方法...
}

二、添加节点到链表头部的方法实现

方法签名

/**
 * 将新节点添加至链表头部
 * @param value 要添加的整数值
 */
public void addFirst(int value) {
    // 创建新节点，next指向当前头节点
    Node newNode = new Node(value, head);
    // 更新头节点引用
    head = newNode;
}

实现原理

节点创建
• new Node(value, head) 创建新节点：
◦ value 参数存储节点值
◦ head 引用当前链表头节点（处理空链表和非空链表的统一方式）
引用更新
• 将头节点引用head指向新建的节点

两种情况的统一处理

空链表情况
• 当head == null时：
◦ 新节点的next自动指向null
◦ head更新后成为唯一节点
非空链表情况
• 当链表已有节点时：
◦ 新节点next指向原头节点
◦ 原头节点成为第二个节点

类关系说明
• 组合关系

SingleLinkedList通过内部类形式封装Node类，对外隐藏实现细节

• 静态内部类

使用static关键字修饰Node类：
• 节点实例不依赖链表实例存在

• 符合节点作为独立数据结构的特性

三、设计优势

封装性
• 对外仅暴露SingleLinkedList类
• 节点操作细节对使用者透明
内存效率
• 静态内部类减少内存开销
• 按需创建节点，动态扩展链表
代码简洁
• addFirst方法统一处理边界情况
• 后续方法可复用节点处理逻辑

四、后续扩展
• 实现addLast()添加尾部节点

• 实现removeFirst()删除头节点

• 实现遍历方法forEach()

• 实现链表反转reverse()

本实现使用Java语言完成，重点展示了单向链表的核心结构和添加操作。通过内部类机制和引用操作，体现了链表数据结构的基本原理和面向对象的封装思想。

028-单向链表-遍历

链表遍历方法详解

一、链表遍历核心思想

准备指针变量指向链表头节点
通过指针依次访问每个节点
通过节点的next指针向后移动
终止条件：指针指向null时结束遍历

二、遍历实现方法

方法1：while循环遍历

public void loop(Consumer<Integer> consumer) {
    Node pointer = head;
    while (pointer != null) {
        consumer.accept(pointer.value);
        pointer = pointer.next;
    }
}

实现步骤：

初始化指针指向头节点
当指针非空时循环处理
处理当前节点值（通过Consumer接口）
指针指向下个节点

方法2：for循环遍历

public void loop2(Consumer<Integer> consumer) {
    for (Node pointer = head; pointer != null; pointer = pointer.next) {
        consumer.accept(pointer.value);
    }
}

特点：
• 将指针初始化、循环条件、指针更新整合到for语句

• 更紧凑的代码结构

方法3：迭代器实现

@Override
public Iterator<Integer> iterator() {
    return new Iterator<>() {
        Node pointer = head;

        @Override
        public boolean hasNext() {
            return pointer != null;
        }

        @Override
        public Integer next() {
            int value = pointer.value;
            pointer = pointer.next;
            return value;
        }
    };
}

使用示例：

for (Integer value : list) {
    System.out.println(value);
}

实现要点：
• 维护指针跟踪当前节点

• hasNext()判断是否还有元素

• next()返回当前值并移动指针

三、测试验证
测试用例：

SingleLinkedList list = new SingleLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.addFirst(4);

// 测试输出应为4->3->2->1
list.loop(System.out::println);

执行结果符合头插法特性，最后插入的元素最先遍历

四、内部类static使用规范

使用原则

情况	static修饰	示例
需要访问外部类成员字段	不加	NodeIterator
完全独立，不依赖外部类实例	加	Node

示例说明

// 需要访问外部类head字段，不加static
class NodeIterator implements Iterator<Integer> {
    Node pointer = head;  // 访问外部类成员
    //...
}

// 独立节点类，添加static
static class Node {
    int value;
    Node next;
    //...
}

五、注意事项

头插法特性：后插入的元素位于链表前端
节点遍历顺序与插入顺序相反
推荐使用Consumer参数解耦遍历与处理逻辑
递归遍历方法将在后续课程讲解

附：术语修正记录
原始录音中的非常规表述：
• "NN值" -> "null"

• "Y6值" -> "value"

• "NN" -> "null"

• "for each" -> "forEach"

• "死在这个了" -> "使用static"

• "秃鹰" -> "重构（Refactor）"

（文档已对代码格式、技术术语进行标准化处理，确保技术准确性）

029-单向链表-addLast

链表尾部添加节点实现详解

一、头部添加与尾部添加对比

头部添加流程
• 创建新节点

• 新节点指向原第一个节点

• head指针指向新节点

• 时间复杂度：O(1)

def add_first(value):
    new_node = Node(value, next=head)
    head = new_node

尾部添加难点
• 需要找到最后一个节点

• 最后一个节点特征：next指针为None

• 必须遍历整个链表才能定位

• 时间复杂度：O(n)

二、关键方法实现

查找最后一个节点方法（find_last）

def find_last(self) -> Node:
    """查找并返回链表最后一个节点"""
    if self.head is None:
        return None  # 空链表情况处理

    pointer = self.head
    while pointer.next is not None:
        pointer = pointer.next
    return pointer

方法特性：
• 私有方法（建议添加_前缀）

• 处理空链表情况

• 循环终止条件：pointer.next == None

• 时间复杂度：O(n)

尾部添加方法（add_last）

def add_last(self, value):
    """在链表尾部添加新节点"""
    last_node = self.find_last()

    if last_node is None:  # 空链表处理
        self.add_first(value)
        return

    new_node = Node(value, next=None)
    last_node.next = new_node

方法流程：

调用find_last定位尾节点
处理空链表特殊情况
创建新节点（next=None）
原尾节点指向新节点

三、测试验证

测试用例

# 创建链表并添加元素
linked_list = LinkedList()
linked_list.add_last(1)
linked_list.add_last(2)
linked_list.add_last(3)
linked_list.add_last(4)

# 验证结果
expected = [1, 2, 3, 4]
assert linked_list.to_list() == expected

测试要点：

验证空链表首次添加
验证连续尾部添加顺序
验证节点连接关系
边界条件测试（单节点链表）

四、复杂度分析

操作	时间复杂度	空间复杂度
find_last	O(n)	O(1)
add_last	O(n)	O(1)
add_first	O(1)	O(1)

五、实现要点总结

尾节点定位是核心难点
必须处理空链表的特殊情况
新节点的next指针必须置为None
遍历时注意指针移动逻辑
保持与头部添加方法的兼容性

通过实现尾部添加，可以完整理解链表遍历机制，为后续实现其他链表操作（如删除、插入等）奠定基础。建议配合调试工具观察指针变化过程以加深理解。

030-单向链表-get

链表索引值获取方法实现课程文档

一、链表索引特性

链表节点结构特性：
• 仅包含值(value)和next指针
• 不存储索引信息
• 索引需通过遍历动态计算
不存储索引的原因：
• 维护成本过高（节点增删时需更新后续所有节点的索引）
• 动态计算索引可保证数据结构的简洁性

二、索引动态计算原理

遍历机制：
• 初始化索引计数器i=0
• 每次移动指针时索引自增
• 索引顺序：0→1→2→...→n-1
遍历流程示例：
• 指针指向头节点 → 索引0
• 指针后移 → 索引1
• 持续后移 → 索引逐次递增

三、核心方法实现

节点查找方法（findNode）

private Node findNode(int index) {
    Node p = head;
    int i = 0;
    while (p != null) {
        if (i == index) {
            return p;
        }
        p = p.next;
        i++;
    }
    return null;
}

值获取方法（get）

public int get(int index) {
    Node node = findNode(index);
    if (node == null) {
        throw new IllegalArgumentException(
            String.format("index [%d] 不合法%n", index)
        );
    }
    return node.value;
}

四、代码实现要点

遍历实现细节：
• 使用双操作for循环：

for (Node p = head, int i = 0; p != null; p = p.next, i++)

异常处理：
• 触发条件：无效索引（超出链表长度/负数）
• 异常类型：IllegalArgumentException
• 错误信息：包含具体非法索引值

五、测试用例说明

有效索引测试：

// 链表：1 → 2 → 3 → 4
System.out.println(list.get(2));  // 输出：3

无效索引测试：

list.get(10);  // 抛出异常：
// IllegalArgumentException: index [10] 不合法

六、设计原则

封装性：
• findNode设为private防止外部直接操作节点
• get方法对外提供安全的值访问接口
代码复用：
• 独立封装遍历逻辑
• 便于其他方法（如删除、插入）复用索引计算

七、注意事项

时间复杂度：
• 索引访问时间复杂度：O(n)
• 适合遍历操作，不推荐频繁随机访问
索引边界处理：
• 需严格校验索引有效性
• 包含负数校验和最大值校验
并发安全：
• 遍历过程中链表结构可能变化
• 多线程环境需同步控制

八、优化建议

索引缓存方案（慎用）：
• 维护size计数器记录链表长度

• 可快速判断索引是否越界

• 示例代码：

private int size = 0;

public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException(...);
    }
    // ...原逻辑
}

双向链表优化：
• 对高频索引访问场景
• 可优化为从近端开始遍历（头/尾）