Skip to content

Commit b1a5861

Browse files
MedalJiaoMedalJiao
committed
0226作业：实现ArrayList,LinkedList,Stack,Queue
1 parent 5a94541 commit b1a5861

File tree

6 files changed

+812
-0
lines changed

6 files changed

+812
-0
lines changed

‎group15/1510_739253131/src/com/bruce/homework0226/ArrayListV00.java

Lines changed: 177 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,177 @@
1+
package com.bruce.homework0226;
2+
3+
import com.bruce.utils.MyException;
4+
5+
import java.io.Serializable;
6+
import java.util.Arrays;
7+
8+
/**
9+
* 用数组实现ArrayList基本功能：add,remove,size,contains,toArray方法
10+
* @Version: 0.0
11+
* Created by Bruce.Jiao on 17-2-23.
12+
*/
13+
public class ArrayListV00 implements Serializable {
14+
15+
/**
16+
* 存放集合元素的数组
17+
*/
18+
private transient Object[] elementData;
19+
/**
20+
* 集合中元素的个数
21+
*/
22+
private int size;
23+
24+
/**
25+
* 空构造，默认数组长度为10
26+
*/
27+
public ArrayListV00() throws MyException {
28+
this(10);
29+
}
30+
31+
/**
32+
* 有参构造
33+
*
34+
* @param initCapacity
35+
* 用户传入的集合大小，底层数组的初始化大小
36+
*/
37+
public ArrayListV00(int initCapacity) throws MyException{
38+
if(initCapacity < 0){
39+
throw new MyException("集合大小不能小于0");
40+
}
41+
elementData = new Object[initCapacity];
42+
}
43+
44+
/**
45+
* 向集合中添加元素
46+
*
47+
* @param value
48+
* 添加的元素，允许添加null
49+
* @return true:添加成功 ; false:添加失败
50+
*/
51+
public boolean add(Object value) {
52+
// 添加元素之前，对数组长度进行判断，此处需要传入当前元素个数+1,
53+
ensureCapacity(size + 1);
54+
elementData[size++] = value;
55+
return true;
56+
}
57+
58+
/**
59+
* 返回指定位置的元素 数组和集合，下标从1开始
60+
*
61+
* @param index
62+
* 用户指定的位置
63+
* @return
64+
*/
65+
public Object get(int index) throws MyException {
66+
// 判断是否越界，注意：此处判断依据是size，而不能是elementData.length，
67+
// 集合元素个数size小于等于elementData.length
68+
if (index >= size || index < 0) {
69+
throw new MyException("给定数值超出集合范围");
70+
}
71+
return elementData[index];
72+
}
73+
74+
/**
75+
* 删除指定位置的元素
76+
*
77+
* @param index
78+
* 用户指定位置，从0开始
79+
* @return 返回删除掉的指定位置的元素
80+
*/
81+
public Object remove(int index) throws MyException {
82+
if (index >= size || index < 0) {
83+
throw new MyException("给定数值超出集合范围");
84+
}
85+
Object value = elementData[index];
86+
// 数组中被删除元素后边的所有元素的个数，此处不能使用elementData.length
87+
int length = size - 1 - index;
88+
// 被删除位置后还有元素，将数组中被删除位置往后(不包含被删除位置)的所有元素往前移动一位
89+
if (length > 0) {
90+
System.arraycopy(elementData, index + 1, elementData, index, length);
91+
}
92+
elementData[--size] = null;
93+
return value;
94+
}
95+
96+
/**
97+
* 判断集合中是否包含指定的元素
98+
*
99+
* @param value
100+
* 用户制定的元素
101+
* @return true:包含指定元素；false:不包含指定元素
102+
*/
103+
public boolean contains(Object value) {
104+
for (int i = 0; i < elementData.length; i++) {
105+
if (value == null) {
106+
if (elementData[i] == null) {
107+
return true;
108+
}
109+
} else {
110+
if (value.equals(elementData[i])) {
111+
return true;
112+
}
113+
}
114+
}
115+
return false;
116+
}
117+
118+
/**
119+
* 得到集合对应的静态数组
120+
*
121+
* @return 底层数组
122+
*/
123+
public Object[] toArray() {
124+
//elementData可能会包含null元素，不能直接返回，需返回一个包含集合所有元素的新数组
125+
// return elementData;
126+
return Arrays.copyOf(elementData,size);
127+
}
128+
129+
/**
130+
* 返回集合大小
131+
*
132+
* @return
133+
*/
134+
public int size() {
135+
return size;
136+
}
137+
138+
/**
139+
* 传入的数值与数组长度进行比较，长度小于传入数值，对数组进行扩容
140+
*
141+
* @param minCapacity
142+
* 传入的数值
143+
*/
144+
public void ensureCapacity(int minCapacity) {
145+
int oldCapacity = elementData.length;
146+
// 如果传入数值大于现有数组长度，对现有数组进行扩容
147+
if (minCapacity > oldCapacity) {
148+
// 此处用新的局部变量引用指向原有数组的内存地址,仅为了避免复制数组元素到新数组时候,发生原有数组内存地址被覆盖的情况
149+
Object[] oldArray = elementData;
150+
// 先得到现有数组长度1.5倍的值
151+
int newCapacity = oldCapacity + oldCapacity >> 1;
152+
// 如果增加1.5倍后的数值仍然小于传入的数值，将传入的数值赋给新数组长度
153+
if (minCapacity > newCapacity) {
154+
newCapacity = minCapacity;
155+
}
156+
// 将elementData引用指向一个新的扩容后的数组，并且将原有数组的元素复制到新数组中
157+
elementData = Arrays.copyOf(elementData, newCapacity);
158+
}
159+
}
160+
161+
/**
162+
* 重写toString方法，查看集合具体内容
163+
* @return
164+
*/
165+
@Override
166+
public String toString() {
167+
return Arrays.toString(elementData);
168+
}
169+
170+
/**
171+
* 仅仅作为自己查看底层数组长度的方法，
172+
* @return
173+
*/
174+
int arrayLength() {
175+
return elementData.length;
176+
}
177+
}

‎group15/1510_739253131/src/com/bruce/homework0226/JuintTest.java

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
package com.bruce.homework0226;
2+
3+
import com.bruce.utils.MyException;
4+
import junit.framework.TestCase;
5+
import org.junit.Test;
6+
import java.util.Arrays;
7+
import java.util.Random;
8+
9+
/**
10+
* Created by Bruce.Jiao on 17-2-23.
11+
*/
12+
public class JuintTest extends TestCase{
13+
14+
@Test
15+
public void testArrayList(){
16+
try {
17+
ArrayListV00 arrayList = new ArrayListV00(0);
18+
arrayList.add("aaa");
19+
arrayList.add("bbb");
20+
arrayList.add("ccc");
21+
arrayList.add("fff");
22+
arrayList.add("ggg");
23+
System.out.println("集合下标2处的元素："+arrayList.get(2));
24+
System.out.println("是否包含ccc这个元素："+arrayList.contains("ccc"));
25+
System.out.println("是否包含ddd这个元素："+arrayList.contains("ddd"));
26+
System.out.println("删除前集合大小为："+arrayList.size());
27+
System.out.println("删除下标2处元素前底层数组："+arrayList);
28+
arrayList.remove(2);
29+
System.out.println("删除下标2处元素后底层数组："+arrayList);
30+
System.out.println("删除一个元素后集合大小为："+arrayList.size());
31+
arrayList.remove(2);
32+
System.out.println("再删除下标2处元素后底层数组："+arrayList);
33+
System.out.println("集合为："+ Arrays.toString(arrayList.toArray()));
34+
System.out.println("集合底层数组长度："+ arrayList.arrayLength());
35+
// System.out.println("集合下标-1处的元素："+arrayList.get(-1));
36+
} catch (MyException e) {
37+
System.out.println("发生异常>>>"+e);
38+
} catch (Exception e) {
39+
e.printStackTrace();
40+
}
41+
}
42+
43+
@Test
44+
public void testLinkedList(){
45+
try {
46+
LinkedListV00<String> linkedList = new LinkedListV00<>();
47+
linkedList.add("aaa");
48+
linkedList.add("bbb");
49+
linkedList.add("ccc");
50+
linkedList.add("ddd");
51+
System.out.println("删除index=2的元素前："+linkedList);
52+
System.out.println("链表尺寸"+linkedList.size());
53+
System.out.println("拿到index=2的元素"+linkedList.get(2));
54+
linkedList.remove(2);
55+
System.out.println("删除index=2的元素后："+linkedList);
56+
} catch (MyException e) {
57+
System.out.println(e.getMessage());
58+
} catch (Exception e) {
59+
e.printStackTrace();
60+
}
61+
}
62+
63+
@Test
64+
public void testStack(){
65+
try {
66+
StackV00 stack = new StackV00();
67+
stack.push("ccc");
68+
stack.push(null);
69+
stack.push("bbb");
70+
stack.push("aaa");
71+
System.out.println("栈的大小："+stack.size());
72+
System.out.println("栈是否为空："+stack.isEmpty());
73+
System.out.println("栈是否为空："+stack);
74+
System.out.println(stack.pop());
75+
System.out.println(stack.pop());
76+
System.out.println(stack.pop());
77+
System.out.println(stack.pop());
78+
stack.clear();
79+
System.out.println("清空后，栈大小："+stack.size());
80+
System.out.println("栈是否为空："+stack.isEmpty());
81+
} catch (MyException e) {
82+
System.out.println(e);
83+
} catch (Exception e) {
84+
e.printStackTrace();
85+
}
86+
}
87+
88+
@Test
89+
public void testQueue(){
90+
try {
91+
QueueV00 queue = new QueueV00();
92+
System.out.println("队列是否为空:"+queue.isEmpty());
93+
queue.add("aaa");
94+
queue.add("bbb");
95+
queue.add("ccc");
96+
queue.add("ddd");
97+
System.out.println(queue);
98+
System.out.println("queue.peek结果:"+queue.peek());
99+
System.out.println("peek后队列长度:"+queue.length());
100+
System.out.println("queue.poll结果:"+queue.poll());
101+
System.out.println("poll后队列长度:"+queue.length());
102+
System.out.println("队列是否为空:"+queue.isEmpty());
103+
} catch (MyException e) {
104+
System.out.println(e.getMessage());
105+
} catch (Exception e) {
106+
e.printStackTrace();
107+
}
108+
}
109+
110+
@Test
111+
public void testArrayLinked(){
112+
try {
113+
ArrayListV00 arrayList = new ArrayListV00();
114+
LinkedListV00 linkedList = new LinkedListV00();
115+
long start1 = System.currentTimeMillis();
116+
for(int i = 0;i<10000;i++){
117+
arrayList.add("abc"+i);
118+
}
119+
long end1 = System.currentTimeMillis();
120+
for(int i = 0;i<10000;i++){
121+
linkedList.add("abc"+i);
122+
}
123+
long end2 = System.currentTimeMillis();
124+
System.out.println("ArrayList的时间："+(end1-start1));
125+
System.out.println("LinkedList的时间："+(end2-end1));
126+
} catch (MyException e) {
127+
e.printStackTrace();
128+
}
129+
}
130+
131+
public String getRandomString(int length){
132+
String base = "abcdefghijklmnopqrstuvwxyz0123456789";
133+
Random random = new Random();
134+
StringBuffer sb = new StringBuffer();
135+
for(int i = 0;i<length;i++){
136+
int number = random.nextInt(base.length());
137+
sb.append(base.charAt(number));
138+
}
139+
return sb.toString();
140+
}
141+
}

0 commit comments

Comments
 (0)