什么是数据结构？
数据结构是计算机存储、组织数据的方式。常见的数据结构如下：
线性表
线性表是具有 n 个相同类型元素的有限序列（ n ≥ 0 ）
常见的线性表有：
数组（Array）
数组是一种顺序存储的线性表，所有元素的内存地址是连续的。在很多编程语言中，数组都有个致命的缺点，无法动态修改容量，实际开发中，我们更希望数组的容量是可以动态改变的。
动态数组接口设计
◼ 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(); // 清除所有元素
动态数组设计
添加元素：add(E element)
删除元素：remove(int index)
指定索引位置添加元素： add(int index, E element)
扩容
把原动态数组复制到新的动态组数(比原数组的容量大)
代码实现
MyList接口：定义要实现的方法
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
|
public interface MyList<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清楚所有元素
*/
void clear();
/**
* 列表元数数量
*
* @return 数量
*/
int size();
/**
* 判断列表是否为空
*
* @return 是否为空
*/
boolean isEmpty();
/**
* 是否包含某个元素
*
* @param element 元素
* @return 返回
*/
boolean contains(E element);
/**
* 添加元素到尾部
*
* @param element 元素
*/
void add(E element);
/**
* 获取index位置的元素
*
* @param index 索引位置
* @return 返回元素
*/
E get(int index);
/**
* 设置index位置的元素
*
* @param index 索引位置
* @param element 元素
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 在index位置插入一个元素
*
* @param index 索引
* @param element 元素
*/
void add(int index, E element);
/**
* 删除index位置的元素
*
* @param index 索引
* @return 元素
*/
E remove(int index);
/**
* 查看元素的索引
*
* @param element 元素
* @return 索引
*/
int indexOf(E element);
}
|
MyAbstractList：抽象类，实现接口MyList一些通用方法
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
|
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
@Override
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
|
动态数组的实现：
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
|
public class DynamicArrayList<E> extends MyAbstractList<E> {
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public DynamicArrayListV3(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
public DynamicArrayListV3() {
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
// 仅供参考
if (elements != null && elements.length > DEFAULT_CAPACITY) {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
}
/**
* 获取index位置的元素
* @param index
* @return
*/
@Override
public E get(int index) { // O(1)
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
@Override
public E set(int index, E element) { // O(1)
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
/*
* 最好：O(1)
* 最坏：O(n)
* 平均：O(n)
*/
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
} // size是数据规模
/**
* 删除index位置的元素
* @param index
* @return
*/
@Override
public E remove(int index) {
/*
* 最好：O(1)
* 最坏：O(n)
* 平均：O(n)
*/
rangeCheck(index);
E old = elements[index];
//index后面的元素往前移
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
//原尾元素置空
elements[--size] = null;
trim();
return old;
}
/**
* 查看元素的索引
* @param element
* @return
*/
@Override
public int indexOf(E element) {
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);
// 新容量为旧容量的2倍
// int newCapacity = 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 trim() {
// 30
int oldCapacity = elements.length;
// 15
int newCapacity = oldCapacity >> 1;
if (size > (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) return;
// 剩余空间还很多
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "缩容为" + newCapacity);
}
@Override
public String toString() {
// size=3, [99, 88, 77]
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中也有动态数组的实现ArrayList，本文的动态数组也是模仿jdk实现的ArrayList。
