Skip to content

Commit 2768aaf

Browse files
author
Rong Huang
authored
Merge pull request onlyliuxin#21 from ZhoufeifeiJAVA/master
MyArrayList,MyLinkedList,Queue,Stack By 793337535
2 parents e539934 + a0ef984 commit 2768aaf

File tree

10 files changed

+377
-0
lines changed

10 files changed

+377
-0
lines changed

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public interface Iterator {
4+
public boolean hasNext();
5+
public Object next();
6+
7+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public interface List {
4+
public void add(Object o);
5+
public void add(int index, Object o);
6+
public Object get(int index);
7+
public Object remove(int index);
8+
public int size();
9+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/MyArrayList.java

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public class MyArrayList implements List {
4+
5+
private int size = 0;
6+
7+
private Object[] elementData = new Object[10];
8+
9+
public void add(Object o){
10+
if(size == elementData.length){
11+
elementData = arrayGrow(elementData,size/2);
12+
}
13+
elementData[size] = o;
14+
size ++;
15+
}
16+
public void add(int index, Object o)throws RuntimeException{
17+
if(index > size)
18+
throw new RuntimeException("index is bigger than the size of MyArrayList");
19+
if(size == elementData.length){
20+
elementData = arrayGrow(elementData,size/2);
21+
}
22+
if(index == size)
23+
add(o);
24+
else{
25+
for(int i=size;i>index;i--){
26+
elementData[i] = elementData[i-1];
27+
}
28+
elementData[index] = o;
29+
}
30+
size ++;
31+
}
32+
private Object[] arrayGrow(Object[] src,int size){
33+
Object[] target = new Object[src.length+size];
34+
System.arraycopy(src, 0, target, 0, src.length);
35+
return target;
36+
}
37+
public Object get(int index){
38+
if(index >= size)
39+
return null;
40+
else
41+
return elementData[index];
42+
}
43+
44+
public Object remove(int index)throws IndexOutOfBoundsException{
45+
if(index>=size || index<0)
46+
throw new IndexOutOfBoundsException("index is bigger than the size of MyArrayList");
47+
Object removeObject = elementData[index];
48+
for(int i=index;i<size-1;i++)
49+
elementData[i] = elementData[i+1];
50+
size --;
51+
return removeObject;
52+
}
53+
54+
public int size(){
55+
return size;
56+
}
57+
58+
private class MyArrayListIterator implements Iterator{
59+
private int pointer;
60+
MyArrayListIterator(){
61+
pointer = 0;
62+
}
63+
public boolean hasNext() {
64+
if(pointer < size)
65+
return true;
66+
else
67+
return false;
68+
}
69+
public Object next() {
70+
pointer ++;
71+
return elementData[pointer-1];
72+
}
73+
74+
}
75+
public Iterator iterator(){
76+
return new MyArrayListIterator();
77+
}
78+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/MyArrayListTest.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
public class MyArrayListTest{
3+
public static void main(String[] args){
4+
MyArrayList al = new MyArrayList();
5+
al.add("string0");
6+
al.add("string1");
7+
al.add("string2");
8+
al.add("string3");
9+
al.add("string4");
10+
al.add("string5");
11+
al.add("string6");
12+
al.add("string7");
13+
al.add("string8");
14+
al.add("string9");
15+
al.add("string10");
16+
al.add("string11");
17+
al.add("string12");
18+
al.add("string13");
19+
al.add("string14");
20+
al.add(11,"string10.5");
21+
sop(al.remove(4).toString());
22+
sop(al.get(10));
23+
sop(al.get(11));
24+
sop(al.get(12));
25+
sop("the size of al is "+al.size());
26+
sop("the iterator method used,so the result is as follows:");
27+
for(Iterator it = al.iterator();it.hasNext();){
28+
sop(it.next());
29+
}
30+
}
31+
public static void sop(Object o){
32+
System.out.println(o);
33+
}
34+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/MyLinkedList.java

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public class MyLinkedList implements List {
4+
5+
private Node head,tail;
6+
private int size = 0;
7+
8+
public void add(Object o){
9+
if(size == 0){
10+
head = new Node();
11+
tail = head;
12+
head.data = o;
13+
}
14+
else{
15+
Node newNode = new Node();
16+
newNode.data = o;
17+
newNode.next = null;
18+
tail.next = newNode;
19+
tail = newNode;
20+
}
21+
size ++;
22+
}
23+
public void add(int index , Object o)throws IndexOutOfBoundsException{
24+
if(index>size || index<0)
25+
throw new IndexOutOfBoundsException("the index is bigger than the size of MyLinkedList");
26+
Node newNode = new Node();
27+
newNode.data = o;
28+
if(index == 0){
29+
newNode.next = head;
30+
head = newNode;
31+
}
32+
else{
33+
int i = 0;
34+
Node pointer = head;
35+
while(i<index-1){
36+
i++;
37+
pointer = pointer.next;
38+
}
39+
newNode.next = pointer.next;
40+
pointer.next = newNode;
41+
}
42+
size++;
43+
}
44+
public Object get(int index){
45+
if(index<0 || index>size-1)
46+
return null;
47+
Node pointer = head;
48+
while(index>0){
49+
pointer = pointer.next;
50+
index --;
51+
}
52+
return pointer.data;
53+
54+
}
55+
public Object remove(int index)throws IndexOutOfBoundsException{
56+
if(index<0 || index>size-1)
57+
throw new IndexOutOfBoundsException("the index is not legal");
58+
Node pointer = head;
59+
if(index == 0){
60+
head = head.next;
61+
size --;
62+
return pointer.data;
63+
}
64+
else{
65+
while(index>1){
66+
pointer = pointer.next;
67+
index --;
68+
}
69+
Node temp = pointer.next;
70+
pointer.next = pointer.next.next;
71+
size --;
72+
return temp.data;
73+
}
74+
}
75+
76+
public int size(){
77+
return size;
78+
}
79+
80+
public void addFirst(Object o){
81+
add(0,o);
82+
}
83+
public void addLast(Object o){
84+
add(size,o);
85+
}
86+
public Object removeFirst(){
87+
return remove(0);
88+
}
89+
public Object removeLast(){
90+
return remove(size-1);
91+
}
92+
93+
private static class Node{
94+
Object data;
95+
Node next;
96+
}
97+
private class MyLinkedListIterator implements Iterator{
98+
private Node pointer;
99+
MyLinkedListIterator(){
100+
pointer = head;
101+
}
102+
public boolean hasNext() {
103+
if(pointer.next != null)
104+
return true;
105+
else
106+
return false;
107+
}
108+
public Object next() {
109+
Node temp = pointer;
110+
pointer = pointer.next;
111+
return temp.data;
112+
}
113+
}
114+
public Iterator iterator(){
115+
return new MyLinkedListIterator();
116+
}
117+
//public void showData(int index){
118+
// System.out.println("the data of "+index+" is "+get(index).data);
119+
//}
120+
}
121+
122+
123+
124+
125+
126+
127+

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/MyLinkedListTest.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
public class MyLinkedListTest{
3+
public static void main(String[] args){
4+
MyLinkedList al = new MyLinkedList();
5+
al.add("string0");
6+
al.add("string1");
7+
al.add("string2");
8+
al.add("string3");
9+
al.add("string4");
10+
al.add("string5");
11+
al.add("string6");
12+
al.add("string7");
13+
al.add("string8");
14+
al.add("string9");
15+
al.add("string10");
16+
al.add("string11");
17+
al.add("string12");
18+
al.add("string13");
19+
al.add("string14");
20+
al.add(11,"string10.5");
21+
sop(al.remove(4));
22+
sop(al.get(10));
23+
sop(al.get(11));
24+
sop(al.get(12));
25+
sop("the size of al is "+al.size());
26+
sop("the iterator method used,so the result is as follows:");
27+
for(Iterator it = al.iterator();it.hasNext();){
28+
sop(it.next());
29+
}
30+
}
31+
public static void sop(Object o){
32+
System.out.println(o);
33+
}
34+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/Queue.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public class Queue {
4+
private MyLinkedList llist = null;
5+
Queue(){
6+
llist = new MyLinkedList();
7+
}
8+
public void enQueue(Object o){
9+
llist.add(o);
10+
}
11+
12+
public Object deQueue(){
13+
return llist.removeFirst();
14+
}
15+
16+
public boolean isEmpty(){
17+
if(llist.size() != 0)
18+
return true;
19+
else
20+
return false;
21+
}
22+
23+
public int size(){
24+
return llist.size();
25+
}
26+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/QueueTest.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
public class QueueTest{
3+
public static void sop(Object o){
4+
System.out.println(o);
5+
}
6+
public static void main(String[] args){
7+
Queue q = new Queue();
8+
q.enQueue("String0");
9+
q.enQueue("String1");
10+
q.enQueue("String2");
11+
sop("the queue is not empty "+q.isEmpty());
12+
sop("the size of queue is "+q.size());
13+
sop("out queue "+q.deQueue());
14+
sop("out queue "+q.deQueue());
15+
sop("the size of queue is "+q.size());
16+
}
17+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/Stack.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
3+
public class Stack {
4+
private MyLinkedList llist = null;
5+
Stack(){
6+
llist = new MyLinkedList();
7+
}
8+
public void push(Object o){
9+
llist.add(o);
10+
}
11+
12+
public Object pop(){
13+
return llist.removeLast();
14+
}
15+
16+
public Object peek(){
17+
return llist.get(llist.size()-1);
18+
}
19+
public boolean isEmpty(){
20+
if(llist.size() != 0)
21+
return true;
22+
else
23+
return false;
24+
}
25+
public int size(){
26+
return llist.size();
27+
}
28+
}

‎group02/793337535/com/github/ZhoufeifeiJAVA/coding2017/basic/StackTest.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package com.github.ZhoufeifeiJAVA.coding2017.basic;
2+
public class StackTest{
3+
public static void sop(Object o){
4+
System.out.println(o);
5+
}
6+
public static void main(String[] args){
7+
Stack s = new Stack();
8+
s.push("String0");
9+
s.push("String1");
10+
s.push("String2");
11+
sop("the queue is not empty "+s.isEmpty());
12+
sop("the size of queue is "+s.size());
13+
sop("out queue "+s.pop());
14+
sop("just watch queue,not delete "+s.peek());
15+
sop("the size of queue is "+s.size());
16+
}
17+
}

0 commit comments

Comments
 (0)