Skip to content

Commit 0e8e418

Browse files
earlywusaearlywusa
committed
assignment 1, basic data structure implementation
1 parent dbd3902 commit 0e8e418

File tree

10 files changed

+566
-47
lines changed

10 files changed

+566
-47
lines changed

‎group17/1282579502/src/com/coding/basic/ArrayList.java

Lines changed: 29 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package com.coding.basic;
22

3-
import java.util.Arrays;
4-
53
public class ArrayList implements List {
64

75
private int size = 0;
@@ -44,8 +42,15 @@ public Object get(int index){
4442
public Object remove(int index) {
4543
if(index <0 || index >= size()) throw new ArrayIndexOutOfBoundsException(index + ": Invalid Index.");
4644
Object item = elementData[index];
47-
if(index<size())
48-
System.arraycopy(elementData, index, elementData, index-1, size-index);
45+
if(size() == 1){
46+
size--;
47+
}else{
48+
if(index<size()){
49+
50+
System.arraycopy(elementData, index+1, elementData, index, size-index);
51+
size--;
52+
}
53+
}
4954
return item;
5055
}
5156

@@ -62,24 +67,39 @@ private void expand(){
6267
System.arraycopy(elementData, 0, newArray, 0, size);
6368
elementData = newArray;
6469
}
70+
71+
public void dump(){
72+
for(int i = 0; i< size(); i++){
73+
System.out.print(elementData[i] + " ");
74+
}
75+
System.out.println();
76+
}
6577

6678
private class ArrayListIterImpl implements Iterator{
6779

68-
ArrayList al = null;
80+
Object[] oArray = null;
81+
int cursor = 0;
6982
public ArrayListIterImpl(ArrayList al){
70-
this.al = al;
83+
if(al == null) throw new NullPointerException("Linkedlist Object is NULL");
84+
oArray = new Object[al.size()];
85+
for(int i = 0; i< al.size(); i++){
86+
oArray[i] = al.get(i);
87+
}
7188
}
7289

7390
@Override
7491
public boolean hasNext() {
75-
// TODO Auto-generated method stub
92+
if(cursor < oArray.length){
93+
return true;
94+
}
7695
return false;
7796
}
7897

7998
@Override
8099
public Object next() {
81-
// TODO Auto-generated method stub
82-
return null;
100+
Object o = oArray[cursor];
101+
cursor ++;
102+
return o;
83103
}
84104

85105
}

‎group17/1282579502/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 39 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,14 @@
22

33
public class BinaryTreeNode {
44

5-
private Object data;
6-
private BinaryTreeNode left;
7-
private BinaryTreeNode right;
5+
private Object data = null;
6+
private BinaryTreeNode left = null;
7+
private BinaryTreeNode right = null;
88

9+
public BinaryTreeNode(){};
10+
public BinaryTreeNode(Object data){
11+
this.data = data;
12+
}
913
public Object getData() {
1014
return data;
1115
}
@@ -24,9 +28,39 @@ public BinaryTreeNode getRight() {
2428
public void setRight(BinaryTreeNode right) {
2529
this.right = right;
2630
}
27-
31+
/*
32+
* this.data > o, return 1
33+
* this.data < o, return -1
34+
* this.data == o, return 0;
35+
*/
2836
public BinaryTreeNode insert(Object o){
29-
return null;
37+
if(!( o instanceof Comparable)) throw new IllegalArgumentException(o + " is NOT comparable. ");
38+
if(data == null) {
39+
data = o;
40+
return this;
41+
}
42+
43+
Comparable cdata = (Comparable) data;
44+
if(cdata.compareTo(o)>0){
45+
if(left == null) {
46+
left = new BinaryTreeNode(o);
47+
return left;
48+
}
49+
else{
50+
return left.insert(o);
51+
}
52+
}
53+
else if(cdata.compareTo(o)<0){
54+
if(right == null){
55+
right = new BinaryTreeNode(o);
56+
return right;
57+
}else{
58+
return right.insert(o);
59+
}
60+
}
61+
else{
62+
throw new IllegalArgumentException(o + " encountered a duplication.");
63+
}
3064
}
3165

3266
}

‎group17/1282579502/src/com/coding/basic/LinkedList.java

Lines changed: 116 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -2,45 +2,147 @@
22

33
public class LinkedList implements List {
44

5-
private Node head;
5+
private Node head = null;
6+
private Node tail = null;
7+
private int size = 0;
68

79
public void add(Object o){
8-
10+
if(head == null){
11+
head = new Node(o);
12+
tail = head;
13+
}else{
14+
tail.next = new Node(o);
15+
tail = tail.next;
16+
}
17+
size ++;
918
}
19+
/**
20+
* Add to index from 0 to size
21+
* Add to index at 0 is equivalent to addFirst
22+
* Add to index at size is equivalent to add and addLast
23+
*
24+
*/
1025
public void add(int index , Object o){
11-
26+
if(index < 0 || index >size+1) throw new IndexOutOfBoundsException(index + ": Invalid Index");
27+
Node newNode = new Node(o);
28+
//manage head node
29+
if(index == 0){
30+
if(head == null){
31+
this.add(o);
32+
}
33+
else{
34+
newNode.next = head;
35+
head = newNode;
36+
size++;
37+
}
38+
}
39+
else if (index == size){
40+
this.add(o);
41+
}
42+
else{
43+
Node prevNode = getNodeAt(index-1);
44+
newNode.next = prevNode.next;
45+
prevNode.next = newNode;
46+
size ++;
47+
}
1248
}
1349
public Object get(int index){
14-
return null;
50+
Node c = getNodeAt(index);
51+
if(c == null ) return null;
52+
return c.data;
53+
}
54+
55+
private Node getNodeAt(int index){
56+
if(index < 0 || index >size-1) throw new IndexOutOfBoundsException(index + ": Invalid Index");
57+
Node c = head;
58+
while(index-- > 0 ){
59+
if(c != null) c = c.next;
60+
else return null;
61+
}
62+
return c;
1563
}
64+
1665
public Object remove(int index){
17-
return null;
66+
if(index<0 || index >size-1) throw new IndexOutOfBoundsException(index + ": Invalid Index");
67+
Node ret = null;
68+
if(index == 0){
69+
ret = head;
70+
head = head.next;
71+
size --;
72+
}else if(index == size -1){
73+
Node nodeBeforeTail = getNodeAt(index -1);
74+
ret = tail;
75+
nodeBeforeTail.next = null;
76+
size --;
77+
}else{
78+
Node nodeBeforeTarget = getNodeAt(index -1);
79+
Node target = nodeBeforeTarget.next;
80+
ret = target;
81+
nodeBeforeTarget.next = target.next;
82+
size --;
83+
}
84+
85+
return ret.data;
1886
}
1987

2088
public int size(){
21-
return -1;
89+
return size;
2290
}
2391

2492
public void addFirst(Object o){
25-
93+
this.add(0, o);
2694
}
95+
2796
public void addLast(Object o){
28-
97+
this.add(o);
2998
}
99+
30100
public Object removeFirst(){
31-
return null;
101+
return remove(0);
32102
}
103+
33104
public Object removeLast(){
34-
return null;
105+
return remove(size-1);
35106
}
107+
36108
public Iterator iterator(){
37-
return null;
109+
return new LinkedListIterator(this);
38110
}
39111

112+
private class Node{
113+
public Object data = null;
114+
public Node next = null;
115+
public Node(Object o){
116+
data = o;
117+
}
118+
}
40119

41-
private static class Node{
42-
Object data;
43-
Node next;
120+
private static class LinkedListIterator implements Iterator{
121+
122+
Object[] oArray = null;
123+
int cursor = 0;
124+
public LinkedListIterator(LinkedList ll){
125+
if(ll == null) throw new NullPointerException("Linkedlist Object is NULL");
126+
oArray = new Object[ll.size()];
127+
for(int i = 0; i< ll.size(); i++){
128+
oArray[i] = ll.get(i);
129+
}
130+
}
131+
132+
@Override
133+
public boolean hasNext() {
134+
if(cursor < oArray.length){
135+
return true;
136+
}
137+
return false;
138+
}
139+
140+
@Override
141+
public Object next() {
142+
Object o = oArray[cursor];
143+
cursor ++;
144+
return o;
145+
}
44146

45147
}
46148
}

‎group17/1282579502/src/com/coding/basic/Queue.java

Lines changed: 16 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,30 @@
11
package com.coding.basic;
22

33
public class Queue {
4+
private LinkedList ll = null;
45

5-
public void enQueue(Object o){
6+
public Queue(){
7+
ll = new LinkedList();
68
}
79

8-
public Object deQueue(){
9-
return null;
10+
public void enQueue(Object o){
11+
ll.add(o);
12+
}
13+
14+
public Object deQueue() throws IndexOutOfBoundsException{
15+
try{
16+
return ll.remove(0);
17+
}catch(IndexOutOfBoundsException ie){
18+
throw new IndexOutOfBoundsException(ie.getMessage());
19+
}
20+
1021
}
1122

1223
public boolean isEmpty(){
13-
return false;
24+
return (ll.size() == 0) ? true : false;
1425
}
1526

1627
public int size(){
17-
return -1;
28+
return ll.size();
1829
}
1930
}

‎group17/1282579502/src/com/coding/basic/Stack.java

Lines changed: 13 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,29 @@
11
package com.coding.basic;
22

33
public class Stack {
4-
private ArrayList elementData = new ArrayList();
4+
private ArrayList al = null;
55

6-
public void push(Object o){
6+
public Stack(){
7+
al = new ArrayList();
8+
}
9+
10+
public void push(Object o){
11+
al.add(o);
712
}
813

914
public Object pop(){
10-
return null;
15+
return al.remove(al.size()-1);
1116
}
1217

1318
public Object peek(){
14-
return null;
19+
return (al.size() == 0) ? null : al.get(al.size() -1);
1520
}
21+
1622
public boolean isEmpty(){
17-
return false;
23+
return (al.size() == 0) ? true : false;
1824
}
25+
1926
public int size(){
20-
return -1;
27+
return al.size();
2128
}
2229
}

0 commit comments

Comments
 (0)