Skip to content

Commit b394c4e

Browse files
GreastateGreastate
authored
Merge pull request onlyliuxin#26 from BlankKelly/master
基本数据结构作业提交
2 parents 4f52a98 + 0fafcb9 commit b394c4e

File tree

12 files changed

+495
-2
lines changed

12 files changed

+495
-2
lines changed

‎group08/769638826/2-27/ArrayList.java

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
/**
7+
* Created by huitailang on 17/2/25.
8+
*
9+
* @author zhangkun
10+
* @date 2017年02月25日13:23:30
11+
*/
12+
public class ArrayList implements List {
13+
private int size = 0;
14+
private static final int DEFAULT_SIZE = 16;
15+
private Object[] elementData = null;
16+
private int index;
17+
18+
public ArrayList() {
19+
elementData = new Object[DEFAULT_SIZE];
20+
}
21+
22+
public ArrayList(final int size) {
23+
elementData = new Object[size];
24+
}
25+
26+
public void add(Object o) {
27+
//如果当前元素个数大于数组长度的2/3
28+
if (size() > elementData.length * 2 / 3) {
29+
raiseArray();
30+
}
31+
32+
elementData[index++] = o;
33+
size++;
34+
}
35+
36+
public void add(int index, Object o) {
37+
checkParam(index);
38+
39+
//如果当前元素个数大于数组长度的2/3
40+
if (size() > elementData.length * 2 / 3) {
41+
raiseArray();
42+
}
43+
44+
elementData[index] = o;
45+
size++;
46+
}
47+
48+
public Object get(int index) {
49+
checkParam(index);
50+
51+
return elementData[index];
52+
}
53+
54+
public Object remove(int index) {
55+
checkParam(index);
56+
57+
Object o = elementData[index];
58+
elementData[index] = null;
59+
size--;
60+
return o;
61+
}
62+
63+
private void raiseArray() {
64+
Object[] newElementData = Arrays.copyOf(elementData, size() * 2);
65+
elementData = newElementData;
66+
}
67+
68+
private void checkParam(int index) {
69+
if (index < 0 || index > elementData.length - 1) {
70+
throw new IndexOutOfBoundsException();
71+
}
72+
}
73+
74+
public int size() {
75+
return size;
76+
}
77+
78+
public Iterator iterator() {
79+
return new ListIterator();
80+
}
81+
82+
private class ListIterator implements Iterator{
83+
int cursor;
84+
85+
@Override
86+
public boolean hasNext() {
87+
return cursor != size;
88+
}
89+
90+
public void remove(){
91+
throw new UnsupportedOperationException();
92+
}
93+
94+
@Override
95+
public Object next() {
96+
if(!hasNext()) {
97+
throw new NoSuchElementException();
98+
}
99+
100+
int i = cursor;
101+
if (i >= size)
102+
throw new NoSuchElementException();
103+
104+
Object[] elementData = ArrayList.this.elementData;
105+
106+
cursor = i + 1;
107+
108+
return elementData[i];
109+
}
110+
}
111+
}

‎group08/769638826/2-27/ArrayListTest.java

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.coding.basic;
2+
3+
import org.junit.Assert;
4+
import org.junit.Before;
5+
import org.junit.Test;
6+
7+
/**
8+
* Created by huitailang on 17/2/25.
9+
* test arraylist
10+
*/
11+
public class ArrayListTest {
12+
ArrayList arrayList = null;
13+
14+
@Before
15+
public void setUp() {
16+
arrayList = new ArrayList();
17+
}
18+
19+
@Test
20+
public void testArrayLength() {
21+
int[] array = new int[10];
22+
Assert.assertEquals(10, array.length);
23+
}
24+
25+
@Test
26+
public void testAddElement() {
27+
arrayList.add(11);
28+
Assert.assertEquals(11, arrayList.get(0));
29+
printElementSize(arrayList);
30+
31+
for (int i = 0; i < 18; i++) {
32+
33+
}
34+
}
35+
36+
@Test
37+
public void testAriseArray() {
38+
for (int i = 0; i < 18; i++) {
39+
arrayList.add(i + 1);
40+
}
41+
42+
Assert.assertEquals(18, arrayList.size());
43+
44+
for (int i = 0; i < 18; i++) {
45+
System.out.println(arrayList.get(i));
46+
}
47+
}
48+
49+
@Test
50+
public void testRemoveElement() {
51+
for (int i = 0; i < 18; i++) {
52+
arrayList.add(i + 1);
53+
}
54+
55+
Assert.assertEquals(18, arrayList.size());
56+
57+
arrayList.remove(17);
58+
59+
Assert.assertEquals(17, arrayList.size());
60+
61+
for (int i = 0; i < 18; i++) {
62+
System.out.println(arrayList.get(i));
63+
}
64+
}
65+
66+
@Test(expected = IndexOutOfBoundsException.class)
67+
public void testInValidGet() {
68+
arrayList.get(19);
69+
}
70+
71+
private void printElementSize(ArrayList arrayList) {
72+
System.out.println("array size => " + arrayList.size());
73+
}
74+
}

‎group08/769638826/2-27/Iterator.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* Created by huitailang on 17/2/25.
5+
*
6+
* @author zhangkun
7+
* @date 2017年02月25日16:25:42
8+
*/
9+
public interface Iterator {
10+
public boolean hasNext();
11+
12+
public Object next();
13+
}

‎group08/769638826/2-27/LinkedList.java

Lines changed: 190 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,190 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/**
6+
* Created by huitailang on 17/2/25.
7+
*
8+
* @author zhangkun
9+
* @date 2017年02月25日13:57:58
10+
*/
11+
public class LinkedList implements List {
12+
private Node head;
13+
private int size;
14+
15+
public LinkedList() {
16+
head = null;
17+
size = 0;
18+
}
19+
20+
@Override
21+
public void add(Object o) {
22+
if (head == null) {
23+
Node newNode = new Node();
24+
newNode.data = o;
25+
head = newNode;
26+
}
27+
28+
Node oldhead = head;
29+
head = new Node();
30+
head.data = o;
31+
head.next = oldhead;
32+
size++;
33+
}
34+
35+
@Override
36+
public void add(int index, Object o) {
37+
Node newNode = new Node();
38+
newNode.data = o;
39+
40+
if (head == null) {
41+
head = newNode;
42+
}
43+
44+
if (index < 1 || index > size + 1) {
45+
throw new IllegalArgumentException("invalid index, it's should be 1 and" + size + 1);
46+
}
47+
48+
if (index == 1) {
49+
newNode.next = head;
50+
} else {
51+
Node currentNode = head;
52+
int count = 1;
53+
while (count < index - 1) {
54+
count++;
55+
currentNode = currentNode.next;
56+
}
57+
newNode.next = currentNode.next;
58+
currentNode.next = newNode;
59+
}
60+
}
61+
62+
@Override
63+
public Object get(int index) {
64+
if (head == null) {
65+
return null;
66+
}
67+
68+
if (index == 1) {
69+
return head.next.data;
70+
} else {
71+
Node currentNode = head;
72+
int count = 1;
73+
while (count < index - 1) {
74+
count++;
75+
currentNode = currentNode.next;
76+
}
77+
78+
return currentNode.next.data;
79+
}
80+
}
81+
82+
@Override
83+
public Object remove(int index) {
84+
Object result = null;
85+
86+
if (index < 1 || index > size) {
87+
throw new IllegalArgumentException("invalid index, it's should be 1 and " + size);
88+
}
89+
90+
if (index == 1) {
91+
Node currentNode = head.next;
92+
head = null;
93+
return currentNode;
94+
} else {
95+
Node prevNode = head;
96+
97+
int count = 1;
98+
while (count < index - 1) {
99+
prevNode = prevNode.next;
100+
count++;
101+
}
102+
Node currentNode = prevNode.next;
103+
prevNode.next = currentNode.next;
104+
result = currentNode.data;
105+
currentNode = null;
106+
}
107+
108+
return result;
109+
}
110+
111+
@Override
112+
public int size() {
113+
return size;
114+
}
115+
116+
public void addFirst(Object o) {
117+
add(1, o);
118+
}
119+
120+
public void addLast(Object o) {
121+
add(size + 1, o);
122+
}
123+
124+
public Object removeFirst() {
125+
return remove(1);
126+
}
127+
128+
public Object removeLast() {
129+
return remove(size);
130+
}
131+
132+
public Iterator iterator() {
133+
return new ListIterator();
134+
}
135+
136+
public void print() {
137+
if (head == null) {
138+
System.out.println("No elements in the list!");
139+
}
140+
141+
Node currentNode = head;
142+
while (currentNode != null) {
143+
System.out.println(currentNode.data + "->");
144+
currentNode = currentNode.next;
145+
}
146+
147+
System.out.println();
148+
}
149+
150+
public int length() {
151+
int count = 0;
152+
153+
Node currentNode = head;
154+
while (currentNode != null) {
155+
count++;
156+
currentNode = currentNode.next;
157+
}
158+
159+
return count;
160+
}
161+
162+
private static class Node {
163+
Object data;
164+
Node next;
165+
}
166+
167+
private class ListIterator implements Iterator {
168+
private Node current = head;
169+
170+
@Override
171+
public boolean hasNext() {
172+
return current != null;
173+
}
174+
175+
public void remove() {
176+
throw new UnsupportedOperationException();
177+
}
178+
179+
@Override
180+
public Object next() {
181+
if (!hasNext()) {
182+
throw new NoSuchElementException();
183+
}
184+
185+
Object o = current.data;
186+
current = current.next;
187+
return o;
188+
}
189+
}
190+
}

0 commit comments

Comments
 (0)