Skip to content

Commit 086eafc

Browse files
592146505592146505
committed
the is List
ArrayList and LinkedList
1 parent b300f43 commit 086eafc

File tree

4 files changed

+638
-0
lines changed

4 files changed

+638
-0
lines changed

‎group20/592146505/data _structure/src/cn/wsc/util/ArrayList.java

Lines changed: 233 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,233 @@
1+
package cn.wsc.util;
2+
3+
import java.util.Arrays;
4+
import java.util.ConcurrentModificationException;
5+
import java.util.Iterator;
6+
import java.util.NoSuchElementException;
7+
8+
/**
9+
* ArrayList类
10+
*
11+
* @author c_malina007
12+
* @param <E>
13+
*/
14+
public class ArrayList<E> implements List<E> {
15+
16+
/** 元素个数 */
17+
private int size;
18+
19+
/** 默认容量 */
20+
private static final int DEFAULT_CAPACITY = 10;
21+
22+
/** 默认最大容量 */
23+
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
24+
25+
/** 默认数组 */
26+
private static final Object[] EMPTY_ELEMENTDATA = {};
27+
28+
/** 用于存放元素 */
29+
private Object[] elementData;
30+
31+
/**
32+
* 无参构造将使用默认数组
33+
*/
34+
public ArrayList() {
35+
elementData = EMPTY_ELEMENTDATA;
36+
}
37+
38+
@Override
39+
public int size() {
40+
return size;
41+
}
42+
43+
@Override
44+
public boolean isEmpty() {
45+
return size == 0;
46+
}
47+
48+
// @Override
49+
// public boolean contains(Object o) {
50+
// // TODO Auto-generated method stub
51+
// return false;
52+
// }
53+
54+
@Override
55+
public Iterator<E> iterator() {
56+
return new Itr();
57+
}
58+
59+
private class Itr implements Iterator<E> {
60+
int cursor; // 当前索引
61+
int lastRet = -1;//
62+
63+
@Override
64+
public boolean hasNext() {
65+
return cursor != size;
66+
}
67+
68+
@SuppressWarnings("unchecked")
69+
@Override
70+
public E next() {
71+
if (cursor > size) {
72+
throw new NoSuchElementException();
73+
}
74+
Object[] elementData = ArrayList.this.elementData;
75+
if (cursor >= elementData.length) {
76+
throw new ConcurrentModificationException();
77+
}
78+
return (E) elementData[lastRet = cursor++];
79+
}
80+
81+
public void remove() {
82+
if (lastRet < 0)
83+
throw new IllegalStateException();
84+
try {
85+
ArrayList.this.remove(lastRet);
86+
cursor = lastRet;
87+
lastRet = -1;
88+
size--;
89+
} catch (IndexOutOfBoundsException ex) {
90+
throw new ConcurrentModificationException();
91+
}
92+
}
93+
94+
}
95+
96+
// @Override
97+
// public Object[] toArray() {
98+
// // TODO Auto-generated method stub
99+
// return null;
100+
// }
101+
//
102+
// @Override
103+
// public <T> T[] toArray(T[] a) {
104+
// // TODO Auto-generated method stub
105+
// return null;
106+
// }
107+
108+
@Override
109+
public boolean add(E element) {
110+
// 保证数组长度正确
111+
ensureCapacityInternal(size + 1);
112+
// 使用后缀自操作符
113+
elementData[size++] = element;
114+
return true;
115+
}
116+
117+
@Override
118+
public boolean add(int index, E element) {
119+
rangeCheckForAdd(index);// 进行添加操作的索引范围检查
120+
// 保证数组长度正确
121+
ensureCapacityInternal(size + 1);
122+
// 源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到目标数组中的 destPos 到
123+
// destPos+length-1 位置
124+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
125+
elementData[index] = element;
126+
size++;
127+
return true;
128+
}
129+
130+
private void ensureCapacityInternal(int minCapacity) {
131+
if (elementData == EMPTY_ELEMENTDATA)
132+
minCapacity = Math.max(minCapacity, DEFAULT_CAPACITY);
133+
// 传入最小容量大于当前数组长度，则扩容
134+
if (minCapacity > elementData.length)
135+
grow(minCapacity);
136+
}
137+
138+
/**
139+
* 扩容
140+
*
141+
* @param minCapacity
142+
*/
143+
private void grow(int minCapacity) {
144+
int oldCapacity = elementData.length;// 获取原数组长度
145+
// 计算新容量
146+
int newCapacity = oldCapacity + (oldCapacity >> 1);// 原容量+(原容量/2)，使用位移符提高运行速度
147+
newCapacity = newCapacity < minCapacity ? minCapacity : newCapacity;
148+
if (newCapacity > MAX_ARRAY_SIZE)
149+
newCapacity = hugeCapacity(newCapacity);
150+
// 将原数组数据复制到一个长度为newCapacity的新数组中
151+
elementData = Arrays.copyOf(elementData, newCapacity);
152+
}
153+
154+
/**
155+
* 传入容量是否大于最大容量常量，如大于最大容量，则返回int类型所能表示的最大值 ArrayList最大容量为int类型所能表示的最大值
156+
*
157+
* @param minCapacity
158+
* @return
159+
*/
160+
private int hugeCapacity(int minCapacity) {
161+
if (minCapacity < 0) {
162+
throw new OutOfMemoryError("The index cannot be negative");
163+
}
164+
return minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
165+
}
166+
167+
@SuppressWarnings("unchecked")
168+
@Override
169+
public E get(int index) {
170+
rangeCheck(index);// 进行索引的范围检查
171+
return (E) elementData[index];
172+
}
173+
174+
@SuppressWarnings("unchecked")
175+
@Override
176+
public E set(int index, E element) {
177+
rangeCheck(index);// 进行索引的范围检查
178+
// 取到指定索引元素，将新元素置入该索引位，并返回原元素
179+
E oldValue = (E) elementData[index];
180+
elementData[index] = element;
181+
return oldValue;
182+
}
183+
184+
@SuppressWarnings("unchecked")
185+
@Override
186+
public E remove(int index) {
187+
rangeCheck(index);// 进行索引的范围检查
188+
// 获取指定索引处元素
189+
E rmValue = (E) elementData[index];
190+
// 源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到目标数组中的 destPos 到
191+
// destPos+length-1 位置
192+
System.arraycopy(elementData, index + 1, elementData, index, size - (index - 1));
193+
size--;
194+
return rmValue;
195+
}
196+
197+
// @Override
198+
// public int indexOf(Object o) {
199+
// // TODO Auto-generated method stub
200+
// return 0;
201+
// }
202+
203+
/**
204+
* 添加时的索引范围检查
205+
*
206+
* @param index
207+
*/
208+
private void rangeCheckForAdd(int index) {
209+
if (index > this.size || index < 0)// 添加可以往末位插入，所以这里索引等于元素个数也可以
210+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
211+
}
212+
213+
/**
214+
* 索引范围检查
215+
*
216+
* @param index
217+
*/
218+
private void rangeCheck(int index) {
219+
if (index < 0 || index >= this.size)
220+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
221+
}
222+
223+
/**
224+
* 以字符串形式返回索引和元素个数信息
225+
*
226+
* @param index
227+
* @return
228+
*/
229+
private String outOfBoundsMsg(int index) {
230+
return "Index: " + index + ", Size: " + this.size;
231+
}
232+
233+
}

0 commit comments

Comments
 (0)