-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGenericArray.java
More file actions
147 lines (111 loc) · 2.68 KB
/
GenericArray.java
File metadata and controls
147 lines (111 loc) · 2.68 KB
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
package algorithm.array;
import java.util.Objects;
/**
* @Author: zs
* @Date: 2020/11/24 16:40
*/
public class GenericArray<T> {
private T[] data;
private int size;
public GenericArray() {
this(10);
}
public GenericArray(int capacity) {
data = (T[]) new Object[capacity];
size = 0;
}
public int getCapacity() {
return data.length;
}
public int count() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void checkIndex(int index) {
if (index > size || index <= 0) {
throw new IllegalArgumentException("require index >=0 and < size");
}
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("remove failed! Require index >=0 and index <= size.");
}
}
/**
* 修改index位置的数
*/
public void set(int index,T e){
checkIndex(index);
data[index] = e;
}
/**
* 查看该数组是否包含某个数
*/
public boolean contains(T e){
for (T t : data) {
if(e == t){
return true;
}
}
return false;
}
/**
* // 获取对应元素的下标, 未找到，返回 -1
*/
public int find(T e){
for (int i = 0; i < data.length; i++) {
if(data[i] == e){
return i;
}
}
return -1;
}
/**
* // 在 index 位置，插入元素e, 时间复杂度 O(m+n)
*/
public void add(int index,T e){
checkIndexForAdd(index);
if(size == data.length){
resize(data.length << 1);
}
for(int end = size - 1;end >= index; end--){
data[end + 1] = data[end];
}
data[index] = e;
size ++;
}
public void addFirst(T e){
add(0,e);
}
public void addLast(T e){
add(size,e);
}
/**
*
* 删除指定位置的元素，并返回
*/
public T remove(int index){
checkIndex(index);
T ret = data[index];
for (int i = index + 1; i < index; i++) {
data[i - 1] = data[i];
}
size--;
if(size == data.length << 2 && data.length << 1 !=0){
resize(data.length << 1);
}
return ret;
}
// 从数组中删除指定元素
public void removeElement(T e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
public void resize(int capacity){
System.arraycopy(data, 0, new Object[capacity], 0, data.length);
}
}