【数据结构与算法】系列二 - 动态数组

发表于 | 分类于 ， ，
| 字数统计 1.8k 字 | 阅读时长 8 分钟

一、什么是数据结构？

数据结构是计算机存储、组织数据的方式。

线性结构： 线性表（数组、链表、栈、队列、哈希表）

树形结构： 二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集

图形结构： 邻接矩阵、邻接表

在实际应用中，根据使用场景来选择最合适的数据结构。

二、线性表

线性表是具有n个相同类型元素的有限序列（n ≥ 0）。

a1是首节点（首元素），an是尾结点（尾元素），a1是a2的前驱，a2是a1的后继。

常见的线性表：

  • 数组
  • 链表
  • 栈
  • 队列
  • 哈希表（散列表）

线性表有一个特点就是都有索引的概念。

生活中的线性表：

三、数组

数组（Array）是一种顺序存储的线性表，所有元素的内存地址是连续的。

1
int array[] = new int[] {11, 22, 33};

在很多编程语言中，数组都有个致命的缺点：无法动态修改容量。但实际开发中，我们更希望数组的容量是可以
动态改变的。

3.1. 动态数组（Dynamic Array）

3.1.1. 接口设计

一个动态数组需要满足下面的方法才算动态。

1
2
3
4
5
6
7
8
9
10
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
boolean contains(E element); // 是否包含某个元素
void add(E element); // 添加元素到最后面
E get(int index); // 返回index位置对应的元素
E set(int index, E element); // 设置index位置的元素
void add(int index, E element); // 往index位置添加元素
E remove(int index); // 删除index位置对应的元素
int indexOf(E element); // 查看元素的位置
void clear(); // 清除所有元素

在Java中，成员变量会自动初始化，比如int类型自动初始化为 0，对象类型自动初始化为null。

3.1.2. 打印数组

重写toString方法，在toString方法中将元素拼接成字符串（字符串拼接建议使用StringBuilder）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public String toString() {
    // 打印效果：size,[11, 22, 33]
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
        
        string.append(elements[i]);
    }
    string.append("]");
    return string.toString();
}

3.1.3. 添加元素

添加元素是添加在数组最后面的，所以元素添加其实就是在索引等于size的位置添加。

1
2
elements[size] = element;
size++;

3.1.4. 指定位置添加元素

案例：在size等于5，index等于2的位置插入元素。

插入元素需要注意把index后面的元素重新往后移动一位。

插入元素时，移动元素位置是从最后面的元素开始的。如果从前面的元素开始移动，会把后面的元素值覆盖。错误的覆盖顺序：

1
2
3
4
5
6
7
8
9
10
public void add(int index, int element) { 
    // index后面的元素后移一位   
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    // 元素插入到index位置
    elements[index] = element;
    // 更新元素数量
    size++;
}

3.1.5. 删除元素

案例：删除size等于7，index等于3的元素。

也就是删除元素值为44的元素：

而且元素被删除后，后面的元素要往前移：

1
2
3
4
5
6
7
8
9
10
public int remove(int index) {
    // 取出待删除元素，用来返回（可以不返回，具体看自己的设计）    
    int old = elements[index];
    // 待删除元素索引的后面元素往前移
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    size--;
    return old;
}

思考：最后一个元素如何处理？

不需要处理，因为size已经限制了元素的数量。

3.1.6. 如何扩容？

数组申请的内存是一段连续的内存，是不能继续再申请空间拼接的。唯一的做法就是申请一块更大内存，把原数组的数据复制到新内存中，并且让原来的数组指针指向新的内存地址。

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
// 添加元素
public void add(int index, E element) {    
    ensureCapacity(size + 1);

    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

/**
 * 保证要有capacity的容量
 * @param capacity
 */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
    
    System.out.println(oldCapacity + "扩容为" + newCapacity);
}

oldCapacity >> 1是向右位移一位的意思，即oldCapacity / 2。位运算效率特别高。

3.1.7. 泛型

上面的案例只能操作int类型的元素。使用泛型技术可以让动态数组更加通用，可以存放任何数据类型。

Java中所有的类型都继承自Object。

完整案例：

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
package com.idbeny;

@SuppressWarnings("unchecked")
public class ArrayList<E> {
    /**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private E[] elements;
	
    /**
     * 默认数组容量 
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 元素未找到的返回值
     */
    private static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 创建数组（指定容量）
     */
    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    /**
     * 创建数组（默认容量）
     */
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear() {
        // 对象元素置空才能保证断开地址引用
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素ֵ
     */
    public E set(int index, E element) {
        rangeCheck(index);
        
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        ensureCapacity(size + 1);

        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        
        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        // 最后一个元素清空
        elements[--size] = null;
        return old;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        // 在java中使用null调用方法会崩溃，所以需要判空
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i; 
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        
        System.out.println(oldCapacity + "扩容为" + newCapacity);
    }

    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

可以阅读官方数组源码：java.util.ArrayList