实现数组类

发表于 分类于 阅读次数：

实现一个数组类，实现了泛型，以及动态扩容。

内部实现

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
public class Array<T> {
	public T[] data;
	private int count;

	//提供两个构造器
	public Array(int num) {
		this.data = (T[]) new Object[num];
		this.count = 0;
	}

	public Array() {
		this(10);
	}

	// 获得数组中元素个数
	public int getSize() {
		return count;
	}

	// 获得数组长度
	public int getCapacity() {
		return data.length;
	}

	// 判断数组是否为空
	public boolean isEmpty() {
		return count == 0;
	}

	// 向所有元素后面添加一个新元素
	public void addLast(T e) {
		insert(count, e);

	}

	// 向所有元素前面添加一个新元素
	public void addFirst(T e) {
		insert(0, e);
	}

	// 插入新元素
	public void insert(int index, T value) {
		if (data.length == count) {
			resize();
		}
		if (index < 0 || index > count) {
			throw new IllegalArgumentException("数组已满");
		}
		// 其中数组索引都是从0开始，所以起始位置已经是最后一个元素的下一位
		for (int i = count; i > index; --i) {
			data[i] = data[i - 1];
		}
		data[index] = value;
		++count;
	}

	// 获取index位置的元素
	public T find(int index) {
		if (index < 0 || index >= count) {
			throw new IllegalArgumentException("数组越界");
		} else {
			return data[index];
		}
	}

	// 修改数组中index位置的元素值
	public void set(int index, T e) {
		if (index < 0 || index >= count) {
			throw new IllegalArgumentException("数组越界");
		}
		data[index] = e;

	}

	// 查找数组元素e所在的索引值
	public int get(T e) {
		for (int i = 0; i < data.length; i++) {
			if (data[i] == e) {
				return i;
			}
		}
		return -1;
	}

	//获取数组的第一个元素值
  	public T getFirst() {
		return find(0);
	}

	//获取数组的最后一个元素值
	public T getLast() {
		return find(count-1);
	}

	// 删除元素，并返回元素值
	public T delete(int index) {
		if (index < 0 || index >= count) {
			throw new IllegalArgumentException("数组越界");
		}
		T ret = data[index];
		for (int i = index + 1; i < count; i++) {
			data[i - 1] = data[i];
		}
		if (count <= data.length 2 && data.length / 2 != 0) {
			resize_less();
		}
		--count;
		data[count] = null;// 提醒GC对其进行回收
		return ret;
	}
	//删除首元素值

	public T deleteFirst() {
		return delete(0);
	}
	//删除末尾元素值
	public T deleTeLast() {
		return delete(count-1);
	}
	public T removeElement(T e) {
		int data_index=get(e);
		if(data_index!=-1) {
			delete(data_index);
		}
		return e;
	}
	//调整数组大小，扩容成原来的1.5倍
	private void resize() {
		Object[] newArray = new Object[data.length + (data.length >> 1)];
		System.arraycopy(data, 0, newArray, 0, data.length);
		data = (T[]) newArray;

	}
	//缩小成原来的2倍
	private void resize_less() {
		Object[] newArray = new Object[data.length/2];
		System.arraycopy(data, 0, newArray, 0, count);
		data = (T[]) newArray;

	}

	// 重写打印方法
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(String.format("Array:size= %d,length: %d", count, data.length));
		stringBuilder.append("[");
		for (int i = 0; i < count; i++) {
			stringBuilder.append(data[i]);
			if (i != count - 1) {
				stringBuilder.append(",");
			}

		}
		stringBuilder.append("]");
		return stringBuilder.toString();

	}

	public static void main(String[] args) {
		Array array = new Array(20);
		for (int i = 0; i < 10; i++) {
			array.addLast(i);
		}
		System.out.println(array);
		array.insert(3, 6);
		System.out.println(array);
		array.addFirst(-3);
		System.out.println(array);
		array.delete(2);
		System.out.println(array);
		array.deleteFirst();
		System.out.println(array);
		array.removeElement(4);
		System.out.println(array);
		array.removeElement(3);
		System.out.println(array);
		array.addLast(4);
		array.addLast(7);
		array.addLast(8);
		System.out.println(array);
	}

}

输出示例

1
2
3
4
5
6
7
8
Array:size= 10,length: 20[0,1,2,3,4,5,6,7,8,9]
Array:size= 11,length: 20[0,1,2,6,3,4,5,6,7,8,9]
Array:size= 12,length: 20[-3,0,1,2,6,3,4,5,6,7,8,9]
Array:size= 11,length: 20[-3,0,2,6,3,4,5,6,7,8,9]
Array:size= 10,length: 20[0,2,6,3,4,5,6,7,8,9]
Array:size= 9,length: 10[0,2,6,3,5,6,7,8,9]
Array:size= 8,length: 10[0,2,6,5,6,7,8,9]
Array:size= 11,length: 15[0,2,6,5,6,7,8,9,4,7,8]
0%