我要评论在本文中，我们将深入探讨如何实现一个简单的动态数组（类似于java中的arraylist）。通过这个实现，我们可以更好地理解动态数组的工作原理和核心操作。
1. 基础结构设计
首先，让我们看看类的基本结构：
public class mylist {
private int[] arr; // 底层数组
private int capacity = 10; // 数组容量
private int size = 0; // 当前元素个数
private int extendratio = 2; // 扩容倍数
}
这个实现包含了四个关键的成员变量：
arr: 存储实际数据的底层数组capacity: 数组的容量size: 当前实际存储的元素数量extendratio: 扩容时的倍数
2. 核心功能实现
2.1 基本操作
获取元素个数和容量
public int size() {
return size;
}
public int capacity() {
return capacity;
}
获取和设置元素
public int get(int index) {
if (index < 0 || index >= size) {
throw new indexoutofboundsexception();
}
return arr[index];
}
public void set(int index, int num) {
if (index < 0 || index >= size) {
throw new indexoutofboundsexception();
}
arr[index] = num;
}
2.2 添加元素
public void add(int item) {
if (size == capacity) {
extendcapacity();
}
arr[size] = item;
size++;
}
2.3 插入元素
public void insert(int index, int item) {
if (index < 0 || index >= size) {
throw new indexoutofboundsexception();
}
if (size == capacity) {
extendcapacity();
}
// 将index后的元素都向后移动一位
for (int i = size - 1; i >= index; i--) {
arr[i + 1] = arr[i];
}
arr[index] = item;
size++;
}
2.4 删除元素
public int remove(int index) {
if (index < 0 || index >= size) {
throw new indexoutofboundsexception();
}
int num = arr[index];
// 将index后的元素都向前移动一位
for (int i = index; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
return num;
}
2.5 扩容机制
private void extendcapacity() {
// 新建一个长度为原数组 extendratio 倍的新数组，并将原数组复制到新数组
arr = arrays.copyof(arr, extendratio);
// 更新列表容量
capacity = arr.length;
}
3. 性能分析
时间复杂度
- 访问元素 (get/set): o(1)
- 在末尾添加元素 (add): 平均o(1)
- 插入元素 (insert): o(n)
- 删除元素 (remove): o(n)
空间复杂度
- 初始空间复杂度: o(1)
- 扩容后的空间复杂度: o(n)
4. 实现特点
- 动态扩容：当数组空间不足时，会自动扩容为原来的2倍。
- 边界检查：所有的操作都会进行严格的边界检查，防止数组越界。
- 数据搬移：在插入和删除操作时，需要移动元素，这是数组实现的一个缺点。
5. 改进建议
- 考虑添加收缩机制，当数组使用率过低时减少容量
- 可以支持泛型，使其能够存储任意类型的数据
- 优化扩容机制，使用更灵活的扩容策略
- 添加迭代器支持，提供更方便的遍历方式
总结
这个简单的动态数组实现展示了数据结构中最基本的一些概念：动态扩容、边界检查、元素操作等。通过理解这些基础实现，我们可以更好地理解java中arraylist等集合类的工作原理。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论