Skip to content

Commit 0b3d282

Browse files
author
龚启盼
committed
暂存ArrayList、Stack
1 parent 70b1782 commit 0b3d282

File tree

4 files changed

+174
-34
lines changed

4 files changed

+174
-34
lines changed

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/ArrayList.java

Lines changed: 108 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package org.apn.coding2017.basic;
22

33
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
45

56
/**
67
* Created by QiPan on 2017/2/23.
@@ -16,8 +17,6 @@ public class ArrayList implements List {
1617

1718
private Object[] elementData;
1819

19-
private int modCount = 0;
20-
2120
// 定义一个默认的空的数组,引用不可变
2221
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
2322

@@ -42,28 +41,80 @@ public boolean add(Object o) {
4241
return true;
4342
}
4443

44+
@Override
45+
public boolean add(int index, Object o) {
46+
if (index > size || index < 0) {
47+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
48+
}
49+
ensureCapacityInternal(size + 1);
50+
// 从插入位置开发，所有的数据需要往后移动
51+
System.arraycopy(elementData, index, elementData, index + 1,
52+
size - index);
53+
elementData[index] = o;
54+
size++;
55+
return true;
56+
}
57+
4558
public Object set(int index, Object element) {
46-
return null;
59+
checkIndexOutOf(index);
60+
Object oldEle = elementData[index];
61+
elementData[index] = element;
62+
return oldEle;
4763
}
4864

4965
public Object get(int index) {
50-
return null;
66+
checkIndexOutOf(index);
67+
return elementData[index];
5168
}
5269

5370
public Object remove(int index) {
54-
return null;
71+
checkIndexOutOf(index);
72+
Object oldValue = elementData[index];
73+
74+
// 计算需要移动的位数
75+
int needMoveNum = size - index - 1;
76+
77+
if (needMoveNum > 0) {
78+
/*
79+
* src：源数组；
80+
* srcPos：源数组要复制的起始位置；
81+
* dest：目的数组；
82+
* destPos：目的数组放置的起始位置；
83+
* length：复制的长度。
84+
*/
85+
System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
86+
}
87+
// 避免对象游离,是的gcc能工作回收
88+
elementData[--size] = null;
89+
return oldValue;
5590
}
5691

5792
public int size() {
58-
return 0;
93+
return this.size;
5994
}
6095

6196
public boolean isEmpty() {
62-
return false;
97+
return this.size == 0;
6398
}
6499

65100
public Iterator iterator() {
66-
return null;
101+
return new Itr();
102+
}
103+
104+
105+
private String outOfBoundsMsg(int index) {
106+
return "Index: " + index + ", Size: " + size;
107+
}
108+
109+
/**
110+
* 检查数组越界
111+
*
112+
* @param index
113+
*/
114+
private void checkIndexOutOf(int index) {
115+
if (index >= size) {
116+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
117+
}
67118
}
68119

69120
private void ensureCapacityInternal(int minCapacity) {
@@ -72,13 +123,11 @@ private void ensureCapacityInternal(int minCapacity) {
72123
// 取得为与默认容量相比的较大值
73124
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
74125
}
75-
ensureExplicitCapacity(minCapacity);
76126
// 调用确保有能力放下那么多元素
127+
ensureExplicitCapacity(minCapacity);
77128
}
78129

79130
private void ensureExplicitCapacity(int minCapacity) {
80-
modCount++;
81-
82131
// 防止容量溢出。所需的最小容器大于数组长度
83132
if (minCapacity - elementData.length > 0) {
84133
grow(minCapacity);
@@ -87,16 +136,17 @@ private void ensureExplicitCapacity(int minCapacity) {
87136

88137
/**
89138
* 扩充容量
139+
*
90140
* @param minCapacity
91141
*/
92-
private void grow(int minCapacity){
142+
private void grow(int minCapacity) {
93143
int oldCapacity = elementData.length;
94144
// 得到一个新的容量大小，为 oldCapacity 的1.5倍
95145
int newCapacity = oldCapacity + (oldCapacity >> 1);
96146
// 如果扩容后的大小比，最小容量（DEFAULT_CAPACITY： 10）小
97-
if (newCapacity - minCapacity < 0){
147+
if (newCapacity - minCapacity < 0) {
98148
newCapacity = minCapacity;
99-
}else if (newCapacity - MAX_ARRAY_SIZE > 0){ // 扩容后比最大的还大，考虑溢出
149+
} else if (newCapacity - MAX_ARRAY_SIZE > 0) { // 扩容后比最大的还大，考虑溢出
100150
//
101151
newCapacity = hugeCapacity(minCapacity);
102152
}
@@ -106,15 +156,57 @@ private void grow(int minCapacity){
106156

107157
/**
108158
* 这个很少用到这个判断，毕竟基本不会使用那么大容量存储
159+
*
109160
* @param minCapacity
110161
* @return
111162
*/
112-
private static int hugeCapacity(int minCapacity){
113-
if (minCapacity < 0){
163+
private static int hugeCapacity(int minCapacity) {
164+
if (minCapacity < 0) {
114165
throw new OutOfMemoryError();
115166
}
116167
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
117168
}
118169

170+
private class Itr implements Iterator {
171+
172+
/**
173+
* 当前游标
174+
*/
175+
int cursor;
176+
int lastRet = -1; // 是否是返回最后一个结果
177+
178+
@Override
179+
public boolean hasNext() {
180+
return cursor != size;
181+
}
182+
183+
@Override
184+
public Object next() {
185+
int i = cursor;
186+
// 游标已经超过数组的大小
187+
if (i >= size) {
188+
throw new NoSuchElementException();
189+
}
190+
Object[] elementData = ArrayList.this.elementData;
191+
192+
// 指向下一个元素
193+
cursor = i + 1;
194+
Object elementDatum = elementData[i];
195+
lastRet = i;
196+
return elementDatum;
197+
}
198+
199+
@Override
200+
public void remove() {
201+
if (lastRet < 0) {
202+
throw new IllegalStateException();
203+
}
204+
// 实际上这个时候的 lastRet,为 next方法时候的 i = cursor
205+
ArrayList.this.remove(lastRet);
206+
cursor = lastRet;
207+
lastRet = -1;
208+
}
209+
}
210+
119211

120212
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/LinkedList.java

Lines changed: 27 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -7,22 +7,19 @@ public class LinkedList implements List {
77

88
Node last;
99

10-
private static class Node {
11-
Object item;
12-
Node next;
13-
}
1410

1511
public boolean add(Object o) {
1612

17-
return true;
13+
return true;
1814
}
1915

2016
public Object set(int index, Object element) {
2117
return null;
2218
}
2319

24-
public void add(int index, Object o) {
20+
public boolean add(int index, Object o) {
2521

22+
return true;
2623
}
2724

2825
public Object get(int index) {
@@ -44,7 +41,30 @@ public boolean isEmpty() {
4441
public Iterator iterator() {
4542
return null;
4643
}
44+
45+
private static class Node {
46+
Object item;
47+
Node next;
4748

48-
49+
Node(Object item, Node next) {
50+
this.item = item;
51+
this.next = next;
52+
}
53+
public Object getItem() {
54+
return item;
55+
}
56+
57+
public void setItem(Object item) {
58+
this.item = item;
59+
}
60+
61+
public Node getNext() {
62+
return next;
63+
}
64+
65+
public void setNext(Node next) {
66+
this.next = next;
67+
}
68+
}
4969

5070
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/List.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@ public interface List {
88

99
boolean add(Object o);
1010

11+
boolean add(int index, Object o);
12+
1113
Object set(int index, Object element);
1214

1315
Object get(int index);

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Stack.java

Lines changed: 37 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -3,23 +3,49 @@
33
/**
44
* Created by QiPan on 2017/2/23.
55
*/
6-
public class Stack {
7-
private ArrayList elementData = new ArrayList();
6+
public class Stack<E> {
87

9-
public void push(Object o){
8+
private E[] elements;
9+
// 记录元素当前位置
10+
private int N;
11+
12+
public Stack(int cap) {
13+
elements = (E[]) new Object[cap];
14+
}
15+
16+
public boolean isEmpty() {
17+
return N == 0;
1018
}
1119

12-
public Object pop(){
13-
return null;
20+
public int size() {
21+
return N;
1422
}
1523

16-
public Object peek(){
17-
return null;
24+
public void push(E e) {
25+
// 如果 N 和数组的长度已经相同，就进行扩容
26+
if (N == elements.length) {
27+
resize(2 * elements.length);
28+
}
29+
elements[N++] = e;
1830
}
19-
public boolean isEmpty(){
20-
return false;
31+
32+
public E pop() {
33+
E element = elements[--N];
34+
elements[N] = null;// 避免对象游离
35+
// 如果元素值剩下容量的1/4，那么就把数组容量变成现在的一半
36+
if (N > 0 && N == elements.length / 4) {
37+
resize(elements.length / 2);
38+
}
39+
return element;
2140
}
22-
public int size(){
23-
return -1;
41+
42+
private void resize(int max) {
43+
E[] elementTmps = (E[]) new Object[max];
44+
for (int i = 0; i < N; i++) {
45+
elementTmps[i] = elements[i];
46+
}
47+
// 指向扩容的数组
48+
elements = elementTmps;
2449
}
50+
2551
}

0 commit comments

Comments
 (0)