如何实现一个支持动态扩容的数组 如何实现一个支持动态扩容的数

发表于

如何实现一个支持动态扩容的数组

这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战

笔者最近在学习《数据结构与算法之美》，正好借着这个机会边练习边记录一下自己学习的知识点。嘿嘿。

一、数组

什么是数组？

数组是一种线性数据结构，用连续的内存空间存储相同数据类型的数据。

由此我们可以得到数组的两个重要特点：

一是线性结构，顾名思义数据结构呈线状即只有前后两个方向。像数组、链表等都是线性结构，与之相对的就是非线性结构，像树、图等等。

二是连续的内存空间存储相同类型数据。

线性结构和非线性结构 - 副本.png

正是这两个特点，数组支持随机访问，只需要 O(1) 的时间复杂度就可以查询到你想要的数据（当然，前提是你知道这个数据所在的下标）。

但是有利也有弊，一个是数组在插入和删除数据时为了维护数组的连续性，就需要进行大量的数据搬移。如果不需要维护数组内数据的有序性，有一个取巧的方法减少数据搬移的次数。增加数据时，我们只需要将增加的数据和数组的最后一个数据进行交换。删除数据也是一样，将删除的数据和数组最后一个数据进行交换，在将最后一个数据删除即可。另一个是数组的长度是固定的。

数据插入数据 - 副本.png

那么如何实现一个动态扩容的数组呢？

二、扩容思路

例如：在长度为 5 的数组 A[5]={a,b,c,d,e} 的位置 2 也就是 c 所在的位置插入 f ，6 个数据大于了数组的长度，就需要进行扩容操作。

扩容的基本思路就是：创建一个容量更大的新数组，将之前的数组里的数据移到新数组中。

扩容思路 - 副本.png

如图，我们先创建了一个长度为 10 的数组 B[10] ，将数组 A 中的数据移动到数组 B 中，再将数据 c、d、e依次向后移动一位，最后将 f 插入到位置 2 ，就完成了插入扩容的操作。

有了扩容的思路，我们再来看看具体的代码实现。

三、实现代码

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
java复制代码/**
 * @author xuls
 * @date 2021/11/6 15:44
 * 实现支持动态扩容的数组
 */
public class CustomArray <T>{
    private int size;
    private Object[] data;
​
    public CustomArray(){
        this(10);
    }
​
    public CustomArray(int capacity){
        data = new Object[capacity];
        size = 0;
    }
​
    //将 t 插入 index 位置
    public void insert(int index,T t){
        //判断index是否在合理范围
        if (index<0 || index>size){
            throw new IllegalArgumentException("index 必须 0<= index <= size");
        }
        //判断是否需要扩容
        if (size == data.length){
            resetSize(2 * data.length);
        }
        //数据搬移
        for (int i = size -1; i>=index ; i--) {
            data[i + 1] = data[i];
        }
        data[index] = t;
        //别忘了++
        size++;
    }
​
    //移除 index 位置的元素
    public T remove(int index){
        //判断index是否在合理范围
        checkIndex(index);
        Object removeData = data[index];
        //数据搬移
        for (int i = index; i <size-1; i++) {
            data[i] = data[i+1];
        }
        size--;
        data[size] = null;
        //判断是否需要缩容
        if (size == data.length / 4 && data.length / 2 !=0){
            resetSize(data.length /2);
        }
        return (T)removeData;
    }
​
    //获取 index 位置的元素
    public T get(int index){
        //判断index是否在合理范围
        checkIndex(index);
        return (T) data[index];
    }
​
    //将 index 位置的数据更新为 t
    private void set(int index ,T t){
        //判断移除位置是否正确
        checkIndex(index);
        data[index]=t;
    }
​
    //重新设置数组的大小
    private void resetSize(int capacity){
        Object[] newData = new Object[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
​
    //检查 index 是否在合理的区间
    private void checkIndex(int index){
        if (index<0 || index>=size){
            throw new IllegalArgumentException("index 必须 0<= index < size");
        }
    }
​
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("数组 size=").append(size).append(",length = ").append(data.length).append("\n");
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size -1){
                builder.append(",");
            }
        }
        builder.append("]");
        return builder.toString();
    }
}

四、总结

  • 数组是既简单有实用的数据结构，优势是随机访问，劣势是删除增加需要进行大量数据搬移，同时不支持动态扩容。
  • 如果数组存储的数据是无序的话，增加删除时我们只需要将增加删除的数据和数组的最后一个数据进行交换，减少大量的数据搬移。
  • 我们不需要自己实现一个动态扩容的数组，Java 已经提供了动态扩容的 ArrayList，但数组并非无用武之地，因为 ArrayList 无法直接存储基本数据类型，需要进行拆箱和装箱操作，所以对性能要求高的场景数组也可以是你的选择。
  • 看到这了，XDM，点赞评论敷衍一下，求求了。
  • catdan.gif

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%