【数据结构与算法】手搓JDK底层ArrayList底层 - 动态数组

数组

在介绍数组之前，我们先来看一段chatGPT给出的对于数组描述：

数组（Array）是一种线性数据结构，它由一组连续的内存空间组成，用来存储相同类型的数据元素。数组具有固定的大小，一旦创建后，其大小通常不能被动态改变。每个元素在数组中都有一个唯一的索引，通过索引可以快速访问数组中的元素。

Java中的ArrayList是一种动态数组的实现，它是java.util包下的一个类。ArrayList能够动态地增长和缩减，使得在>运行时可以根据需要添加或删除元素，而无需预先指定数组的大小。

在Java中，ArrayList的底层实现是一个数组。当你创建一个ArrayList时，Java会在内部创建一个Object类型的数组来存储元素。默认情况下，这个数组的初始大小是10。当向ArrayList添加元素时，如果数组已满，Java会自动创建一个新的数组，并将原数组中的元素复制到新数组中，然后继续添加新的元素。这个过程被称为"扩容"。

ArrayList还提供了一些方法来操作数组，比如添加元素（add）、获取元素（get）、删除元素（remove）、获取大小（size）等等。由于ArrayList底层使用数组实现，所以可以通过数组的索引来快速访问元素，这使得ArrayList在随机访问方面具有较好的性能。
总之，ArrayList是Java中常用的动态数组实现，它提供了灵活的数组操作方法，并且在需要动态调整大小的情况下能够高效地管理内存。

1) 概述

定义

在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

int[] array = {1,2,3,4,5}
1

知道了数组的数据起始地址 $BaseAddress$，就可以由公式 $BaseAddress+i\ast size$ 计算出索引 $i$ 元素的地址

• $i$ 即索引，在 Java、C 等语言都是从 0 开始
• $size$ 是每个元素占用字节，例如 $int$ 占 $4$，$double$ 占 $8$

小测试

byte[] array = {1,2,3,4,5}
1

已知 array 的数据的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

答：0x7138f94c8 + 2 * 1 = 0x7138f94ca

空间占用

Java 中数组结构为

• 8 字节 markword
• 4 字节 class 指针（压缩 class 指针的情况）
• 4 字节 数组大小（决定了数组最大容量是 $2^{32}$）
• 数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍[^12]，不足的要用对齐字节补足）

例如

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

的大小为 40 个字节，组成如下

8 + 4 + 4 + 5*4 + 4(alignment)
1

随机访问性能

即根据索引查找元素，时间复杂度是 $O(1)$

2) 动态数组

java 版本

package com.dataStructure.dataStructure.array;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

/**
 * 动态数组
 */
public class DynamicArray implements Iterable<Integer> {
    private int size = 0;     //有效元素个数
    private int capacity = 8; //容量
    private int[] array = {};  //懒加载

    /**
     * 向数组的最后位置添加元素
     *
     * @param element 待添加元素
     */
    public void addLast(int element) {
        add(size, element);
    }

    /**
     * 向数组任意位置插入元素
     *
     * @param index   索引位置
     * @param element 待插入元素
     */
    public void add(int index, int element) {
        //容量检查及扩容
        checkAndGrow();

        // 添加逻辑
        if (index >= 0 && index < size) {
            // 向后挪动, 空出待插入位置
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    /**
     * 数组扩容方法,该动态数组实现懒加载模式，
     * 并且如果数组满了，以1.5倍进行数组扩容
     */
    private void checkAndGrow() {
        //容量检查
        if (size == 0) {
            array = new int[capacity];//初始化数组长度
        } else if (size == capacity) {
            //进行1.5倍扩容
            capacity += capacity >> 1;
            //创建一个容量为之前容量1.5倍的新数组
            int[] newArray = new int[capacity];
            //将原来数组中的元素拷贝到新数组中去
            System.arraycopy(array, 0, newArray, 0, size);
            //将新数组赋给全局变量
            array = newArray;
        }
    }

    /**
     * 删除元素
     *
     * @param index 待删除元素索引
     * @return 删除元素
     */
    public int remove(int index) {
        int removedElement = array[index];
        if (index < size - 1) {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        size--;
        return removedElement;
    }

    /**
     * 查询元素
     *
     * @param index 索引位置，在[0,size)区间内
     * @return 该索引位置的元素
     */
    public int get(int index) {
        if (index >= 0 && index < size) {
            return array[index];
        } else throw new ArrayStoreException();
    }

    /**
     * 遍历方式 1
     *
     * @param consumer 函数式接口
     */
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }

    /**
     * 遍历方法2—迭代器遍历
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

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

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

    /**
     * 遍历方法3—Stream流
     *
     * @return 有效数组的流对象
     */
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

• 这些方法实现，都简化了 index 的有效性判断，假设输入的 index 都是合法的
  

插入或删除性能

头部位置，时间复杂度是 $O(n)$

中间位置，时间复杂度是 $O(n)$

尾部位置，时间复杂度是 $O(1)$（均摊来说）

本文为学习黑马数据结构笔记！更多内容大家可以参考23版黑马数据结构！