线性数据结构之数组

数组概述

数组是一种数据结构，用于存储多个相同类型的元素。在许多编程语言中，数组是最基本的数据结构之一，常用于管理和处理数据。数组的元素在内存中是连续存储的，可以通过索引直接访问。

一、静态数组

定义：静态数组是指在编译时就确定了大小的数组，其大小在运行时不能改变。静态数组通常在栈上分配内存。

1. 特点

固定大小：一旦定义，其大小就不能再更改。
内存分配：通常在栈上分配，生命周期与作用域一致，使用时速度快。
类型一致性：所有元素必须是相同类型，可以是基本数据类型或对象类型。

2. 优点

访问速度快：可以通过索引直接访问数组中的元素，访问时间复杂度为 O(1)。
内存管理简单：内存分配和释放由编译器自动管理，无需手动释放内存。

3. 缺点

缺乏灵活性：无法在运行时改变数组的大小，可能导致内存浪费或溢出。
插入和删除操作复杂：在数组中间插入或删除元素需要移动其他元素，时间复杂度为 O(n)。

4. 适用场景

已知固定大小的数组：如存储常量、简单的数据集合（如星期几的数字表示）。
性能要求高的场景：如图形处理、实时系统等。

5. 示例代码（Java）

public class StaticArrayExample {
    public static void main(String[] args) {
        // 定义一个静态数组，大小为5
        int[] staticArray = new int[5];

        // 为数组元素赋值
        staticArray[0] = 10;
        staticArray[1] = 20;
        staticArray[2] = 30;
        staticArray[3] = 40;
        staticArray[4] = 50;

        // 遍历输出数组元素
        for (int i = 0; i < staticArray.length; i++) {
            System.out.print(staticArray[i] + " "); // 输出数组元素
        }
    }
}

二、动态数组

定义：动态数组是一种可以在运行时调整大小的数组，通常在 Java 中使用 ArrayList 类来实现。动态数组允许动态增加或减少元素的数量。

1. 特点

可变大小：可以根据需要动态调整大小，随时添加或删除元素。
内存分配：在堆上分配内存，可能会有更高的内存管理开销。
类型安全：Java 中的 ArrayList 可以使用泛型，支持类型安全。

2. 优点

灵活性高：在元素数量未知或变化时，动态数组提供了更大的灵活性。
插入和删除操作简单：可以直接在列表中添加或删除元素，无需手动移动元素。

3. 缺点

性能开销：在动态数组扩展时，如果当前容量已满，需重新分配更大的数组并复制元素，时间复杂度为 O(n)。
内存管理复杂：动态数组使用堆内存，可能导致内存泄漏，需要谨慎管理。

4. 适用场景

元素数量不确定的情况：如用户输入、动态生成的数据集等。
需要频繁插入和删除的场景：如实现队列、栈等数据结构。

5. 示例代码（Java）

import java.util.ArrayList;

public class DynamicArrayExample {
    public static void main(String[] args) {
        // 定义一个动态数组（ArrayList）
        ArrayList<Integer> dynamicArray = new ArrayList<>();

        // 添加元素
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        dynamicArray.add(40);
        dynamicArray.add(50);

        // 删除元素
        dynamicArray.remove(Integer.valueOf(20)); // 删除元素20

        // 遍历输出数组元素
        for (int item : dynamicArray) {
            System.out.print(item + " "); // 输出数组元素
        }
    }
}

三、性能分析

静态数组
- 访问时间复杂度：O(1)
- 插入时间复杂度：O(n)（在数组中间插入元素时）
- 删除时间复杂度：O(n)（在数组中间删除元素时）
- 内存使用：内存分配固定，可能会造成空间浪费。
动态数组
- 访问时间复杂度：O(1)
- 插入时间复杂度：O(1)（在尾部添加元素时），O(n)（扩展时）
- 删除时间复杂度：O(n)（在数组中间删除元素时）
- 内存使用：可能会根据元素数量动态调整，但需要在扩展时复制元素，增加了时间和空间的开销。