线性数据结构之数组
数组概述
数组是一种数据结构，用于存储多个相同类型的元素。在许多编程语言中，数组是最基本的数据结构之一，常用于管理和处理数据。数组的元素在内存中是连续存储的，可以通过索引直接访问。
一、静态数组
定义：静态数组是指在编译时就确定了大小的数组，其大小在运行时不能改变。静态数组通常在栈上分配内存。
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)（在数组中间删除元素时）
- 内存使用：可能会根据元素数量动态调整，但需要在扩展时复制元素，增加了时间和空间的开销。
四、总结
- 静态数组适用于在编译时已知大小且对性能要求较高的场合，尤其在内存管理和访问速度方面表现优异。
- 动态数组则适用于在运行时元素数量不确定或需要频繁修改的情况，提供了更多的灵活性，但在性能和内存管理方面存在一定的开销。
原文地址：https://blog.csdn.net/m0_61840987/article/details/143393749
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！