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
| public class GenericArray<T>
{
private T[] data;
private int size;
// 根据传入容量，构造Array
public GenericArray(int capacity) {
data = (T[]) new Object[capacity];
size = 0;
}
// 无参构造方法，默认数组容量为10
public GenericArray() {
this(10);
}
// 获取数组容量
public int getCapacity() {
return data.length;
}
// 获取当前元素个数
public int count() {
return size;
}
// 判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
// 修改index位置的元素
public void set(int index, T e) {
checkIndex(index);
data[index] = e;
}
// 获取对应的index位置的元素
public T get(int index) {
checkIndex(index);
return data[index];
}
// 查看元素是否包含元素e
public boolean contains(T e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
// 获取对应元素的下标，未找到，返回-1
public int find(T e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 在index位置，插入元素e，时间复杂度O(m+n)
public void add(int index, T e) {
checkIndex(index);
// 如果当前元素个数等于数组容量，则将数组扩容为原来的2倍
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size; i > index; i--) {
data[i] = data[i-1];
}
data[index] = e;
size++;
}
// 向数组头插入数据
public void addFirst(T e) {
add(0, e);
}
// 删除index位置的元素并返回
public T remove(int index) {
checkIndexForRemove(index);
T ret = data[index];
for (int i = index+1; i < size; i++) {
data[i-1] = data[i];
}
size--;
data[size] = null;
// 缩容
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
// 删除第一个元素
public T removeFirst() {
return remove(0);
}
// 删除末尾元素
public T removeLast() {
return remove(size-1);
}
// 从数组中删除指定元素
public void removeElement(T e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
@Override
public String toString() {
StringBuffer builder = new StringBuffer();
builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
builder.append('[');
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size-1) {
builder.append(", ");
}
}
builder.append(']');
return builder.toString();
}
// 扩容方法，时间复杂度是O(n)
private void resize(int capacity) {
T[] newData = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
private void checkIndex(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed! Require index>=0 and index<=size");
}
}
private void checkIndexForRemove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed! Require index>=0 and index<=size");
}
}
public void printAll() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
GenericArray<Integer> array = new GenericArray<Integer>(5);
array.printAll();
array.add(0, 3);
array.add(0, 4);
array.add(1, 5);
array.add(3, 9);
array.add(3, 10);
array.printAll();
}
}
|