数据结构-数组
数据结构数组的的学习笔记。
数据结构-数组
1. 数组概述
特点
顺序存放、可以随机访问。
缺点
数组功能比较弱，考虑封装。
2. 封装自己的数组
引入
为了增强数组的功能，我们对数组进行二次封装，虽然Java已经有ArrayList对数组进行了封装，但为了学习，我们对数组进行封装。
代码
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
164package top.tobing.ds.array;
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
// 默认构造
public Array() {
this(10);
}
// 获取数组的容量
public int getCapacity() {
return data.length;
}
// 获取数组的元素个数
public int getSize() {
return size;
}
// 判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
// 在所有元素后添加一个元素
public void addLast(E e) {
add(size, e);
}
// 在使用元素前添加一个元素
public void addFirst(E e) {
add(0, e);
}
// 在索引index处添加一个元素
public void add(int index, E e) {
if (index < 0 || index > data.length) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
}
if (index == data.length) {
resize(2 * data.length);
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
// 获取index索引位置的值
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
// 修改index索引出的值为e
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed, Index is illegal.");
}
data[index] = e;
}
// 查找数组中是否包含元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 删除数组中索引为index位置的元素，返回被删除的元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Rmove failed. Index is illegal.");
}
E temp = 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) {
resize(data.length / 2);
}
return temp;
}
// 删除元素第一个元素
public E removeFirst() {
E temp = remove(0);
return temp;
}
// 删除元素最后一个元素
public E removeLast() {
E temp = remove(size - 1);
return temp;
}
// 删除数组中元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append('[');
for (int i = 0; i < data.length; i++) {
builder.append(data[i]);
if (i != data.length - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
// 将数组的容量变成newCapacity大小
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}代码中的注意点
泛型数组在通过指定大小创建时要以
(E[])Objec[capacity]方式。添加add或者删除remove元素的时候要对传入的index进行合法性校验。
add和remove都是采用覆盖的方式，区别两种的实现：一个是从后往前移，另一个则相反。
add和remove的同时要维护size，即更新size。
remove操作时要对size所在的位置置为null，以至于gc回收。
find操作判断元素是否相等时要使用equals。
动态数组时，要注意remove的容量调整时机，使用懒汉式可以避免复杂度震荡。
复杂度分析
函数名 复杂度 其他 add(int,E) O(n) 移动挪位 addFirst O(n) addLast O(1)、O(n) 不用挪位、容量变化 remove(int,E) O(n) 移动覆盖 removeFirst O(n) removeLast O(1)、O(n) 不用覆盖、容量变化 removeElement(E) O(n) 遍历查找 contains O(n) find O(n) get O(1) resize复杂度分析：加上容量为n、n+1次addLast，触发resize，纵观2n+1基本操作平均，每次addLast，进行2次基本操作，O(1)。 这次叫做均摊复杂度分析。
addLast和removeLast同时存在是，如果采用饿汉式，即size=capacity/2立马缩减容量，容易引发复杂度震荡。因此考虑使用懒汉式。即推迟到size=capacity/4,才将capacity置为原理一半。
3. 拓展
查看Java对ArrayList的实现，对比我们的实现。
