您现在的位置是:首页 >其他 >【数据结构】-数组和List数据结构网站首页其他

【数据结构】-数组和List数据结构

stayhungerstayflush 2024-07-04 11:18:03
简介【数据结构】-数组和List数据结构

数组

  1. 定义和特点
  • 数组是一种静态数据结构,由相同类型的元素按顺序排列而成。
  • 元素在内存中是连续存储的,可以通过索引直接访问和修改元素。
  1. 访问和修改元素
  • 数组使用索引进行元素访问,索引从0开始。
  • 可以通过索引修改数组中的元素值。
  1. 数组的优点和缺点
  • 优点:随机访问速度快,内存连续存储利于缓存,适用于需要频繁访问元素的场景。
  • 缺点:插入和删除元素的操作相对较慢,需要移动其他元素。
  1. java中的使用示例
//创建数组
int[] numbers = new int[5];  // 创建一个包含5个整数的数组
String[] names = new String[3];  // 创建一个包含3个字符串的数组
// 访问和修改数组元素
int[] numbers = {1, 2, 3, 4, 5};  // 创建并初始化数组
System.out.println(numbers[0]);  // 访问数组第一个元素
numbers[2] = 10;  // 修改数组第三个元素的值
//获取数组长度:
int[] numbers = {1, 2, 3, 4, 5};
int length = numbers.length;  // 获取数组长度
System.out.println(length);
// 遍历数组
int[] numbers = {1, 2, 3, 4, 5};
for (int i = 0; i < numbers.length; i++) {
    System.out.println(numbers[i]);
}
  1. ArrayList扩容原理
    ArrayList使用一个内部数组来存储元素。当需要扩容时,ArrayList会创建一个新的更大容量的数组,并将原来数组中的元素复制到新数组中。
    扩容时,ArrayList通常会根据当前容量使用一种策略来确定新容量的大小,如每次扩容增加当前容量的一半或两倍。这样可以平衡内存开销和性能。
    扩容过程中,ArrayList需要将原来数组中的元素复制到新数组中,这可能涉及到系统级的内存复制操作。
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容一半,即增加原容量的50%
    if (newCapacity - minCapacity < 0) // 如果新容量仍然不满足需求,则直接使用需求的最小容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 检查是否超出数组的最大容量限制
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 创建新的数组,并将原数组的元素复制到新数组中
}

在上述代码中,grow(int minCapacity) 方法用于实现扩容逻辑。它首先根据当前数组的容量计算出新的容量 newCapacity,通常是原容量的一半。然后检查新容量是否满足最小需求 minCapacity,如果不满足,则直接使用最小需求容量。接着,检查新容量是否超出数组的最大容量限制,如果超出,则调用 hugeCapacity(minCapacity) 方法进行处理。最后,使用 Arrays.copyOf() 方法创建一个新的数组,并将原数组中的元素复制到新数组中,完成扩容操作。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。