Skip to content

Commit 836f511

Browse files
author
hugetom
committed
xinda作业
List等方法实现
1 parent d4a25d6 commit 836f511

File tree

11 files changed

+485
-0
lines changed

11 files changed

+485
-0
lines changed

‎group17/865797761/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group17/865797761/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group17/865797761/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>865797761</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group17/865797761/.settings/org.eclipse.jdt.core.prefs

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
eclipse.preferences.version=1
2+
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
3+
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.8
6+
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
7+
org.eclipse.jdt.core.compiler.debug.localVariable=generate
8+
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
9+
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
10+
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
11+
org.eclipse.jdt.core.compiler.source=1.8

‎group17/865797761/src/Collection/ArrayList.java

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
package Collection ;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
/**
7+
Created by william on 2017/2/25.
8+
*/
9+
public class ArrayList<T> implements List<T> {
10+
private static final int DEFAULT_CAPACITY = 10;
11+
private int size;
12+
private Object[] elementData;
13+
14+
public ArrayList() {
15+
elementData = new Object[DEFAULT_CAPACITY];
16+
}
17+
18+
public ArrayList(int initialCapacity) {
19+
if (initialCapacity < 0)
20+
throw new RuntimeException("非法初始化大小参数!");
21+
elementData = new Object[initialCapacity];
22+
}
23+
24+
public boolean add(T ele) {
25+
grow();
26+
elementData[size] = ele;
27+
size++;
28+
return true;
29+
}
30+
31+
public T get(int index) {
32+
checkBounds(index);
33+
return (T) elementData[index];
34+
}
35+
36+
public T remove(int index) {
37+
checkBounds(index);
38+
T removeEle = (T) elementData[index];
39+
System.arraycopy(elementData, index + 1, elementData, index, size - index);
40+
size--;
41+
return removeEle;
42+
}
43+
44+
public boolean add(int index, T ele) {
45+
checkBounds(index);
46+
size++;//有效元素内容先加，保证长度极限情况grow在添加前生效
47+
grow();
48+
//将原本数组从待插入的index截取，将原本index后的有效值，复制到原本数组index+1之后
49+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
50+
elementData[index] = ele;
51+
return true;
52+
}
53+
54+
@Override
55+
public boolean remove(T ele) {
56+
int index;
57+
if ((index = indexOf(ele)) == -1)
58+
return false;
59+
remove(index);
60+
return true;
61+
}
62+
63+
private void checkBounds(int index) {
64+
if (index < 0 || index >= size)
65+
throw new IndexOutOfBoundsException("index : " + index + ", size : [ 0 - " + size + " ]");
66+
}
67+
68+
public int size() {
69+
return size;
70+
}
71+
72+
private void grow() {
73+
if (size >= elementData.length) {
74+
int curLen = elementData.length;
75+
int newLen = curLen + (curLen >> 1) > Integer.MAX_VALUE ? Integer.MAX_VALUE : curLen + (curLen >> 1);
76+
elementData = Arrays.copyOf(elementData, newLen);
77+
}
78+
}
79+
80+
public boolean isEmpty() {
81+
return size == 0;
82+
}
83+
84+
@Override
85+
public boolean contains(T ele) {
86+
return indexOf(ele) != -1;
87+
}
88+
89+
public int indexOf(T ele) {
90+
for (int i = 0; i < size; i++) {
91+
if (ele == null)
92+
if (null == elementData[i])
93+
return i;
94+
else if (ele.equals(elementData[i]))
95+
return i;
96+
}
97+
return -1;
98+
}
99+
100+
public Iterator<T> iterator() {
101+
return new Itr<T>();
102+
}
103+
104+
private class Itr<T> implements Iterator<T> {
105+
int cursor;//待遍历元素的下标
106+
107+
@Override
108+
public boolean hasNext() {
109+
return cursor != size;
110+
}
111+
112+
@Override
113+
public T next() {
114+
if (cursor >= size)
115+
throw new NoSuchElementException();
116+
return (T) elementData[cursor++];
117+
}
118+
119+
@Override
120+
public void remove() {
121+
if (cursor >= size)
122+
throw new NoSuchElementException();
123+
ArrayList.this.remove(cursor--);
124+
}
125+
}
126+
127+
@Override
128+
public String toString() {
129+
StringBuilder sb = new StringBuilder("[ ");
130+
for (Object ele : elementData) {
131+
sb.append(ele).append(" ");
132+
}
133+
return sb.append("]").toString();
134+
}
135+
}

‎group17/865797761/src/Collection/Iterable.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package Collection;
2+
3+
//
4+
public interface Iterable<T> {
5+
Iterator<T> iterator();
6+
}

‎group17/865797761/src/Collection/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package Collection;
2+
3+
public interface Iterator<E> {
4+
public boolean hasNext();
5+
6+
public E next();
7+
}

‎group17/865797761/src/Collection/List.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package Collection;
2+
3+
//
4+
public interface List<E> {
5+
public void add(E o);
6+
7+
public void add(int index, E o);
8+
9+
public E get(int index);
10+
11+
public E remove(int index);
12+
13+
public int size();
14+
}

‎group17/865797761/src/Collection/MyArrayList.java

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
package Collection;
2+
3+
import java.util.Arrays;
4+
5+
public class MyArrayList<E> implements List<E>, Iterable<E> {
6+
private Object[] elementData;
7+
private static final int DEFAULT_SIZE = 10;
8+
private int size;
9+
10+
public MyArrayList() {
11+
this(DEFAULT_SIZE);
12+
}
13+
14+
public MyArrayList(int initSize) {
15+
if (initSize < 0) {
16+
throw new IllegalArgumentException(initSize + " < 0");
17+
}
18+
if (initSize == 0) {
19+
elementData = new Object[DEFAULT_SIZE];
20+
}
21+
else {
22+
elementData = new Object[initSize];
23+
}
24+
size = 0;
25+
}
26+
27+
public void add(E o) {
28+
growIfNeed();
29+
elementData[size++] = o;
30+
}
31+
32+
public void add(int index, E o) {
33+
if (index < 0 || index > size) {
34+
throw new IllegalArgumentException("index:" + index);
35+
}
36+
growIfNeed();
37+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
38+
elementData[index] = o;
39+
size++;
40+
}
41+
42+
@SuppressWarnings("unchecked")
43+
public E get(int index) {
44+
rangeCheck(index);
45+
return (E) elementData[index];
46+
}
47+
48+
public E remove(int index) {
49+
rangeCheck(index);
50+
E target = get(index);
51+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
52+
size--;
53+
return target;
54+
}
55+
56+
public int size() {
57+
return size;
58+
}
59+
60+
private void rangeCheck(int index) {
61+
if (index >= size) {
62+
throw new NoSuchElementException("index:" + index);
63+
}
64+
}
65+
66+
private void growIfNeed() {
67+
if (size == elementData.length)
68+
grow();
69+
}
70+
71+
private void grow() {
72+
elementData = Arrays.copyOf(elementData, elementData.length * 2);
73+
}
74+
75+
@Override
76+
public Iterator<E> iterator() {
77+
return new ArrayIterator<>();
78+
}
79+
80+
private class ArrayIterator<E> implements Iterator<E> {
81+
private int currentPos = 0;
82+
83+
@Override
84+
public boolean hasNext() {
85+
return currentPos < size;
86+
}
87+
88+
@SuppressWarnings("unchecked")
89+
@Override
90+
public E next() {
91+
rangeCheck(currentPos);
92+
return (E) elementData[currentPos++];
93+
}
94+
95+
}
96+
97+
@Override
98+
public String toString() {
99+
return Arrays.toString(Arrays.copyOf(elementData, size));
100+
}
101+
102+
}
103+
104+
class NoSuchElementException extends RuntimeException {
105+
106+
public NoSuchElementException(String string) {
107+
super(string);
108+
}
109+
110+
}

0 commit comments

Comments
 (0)