Skip to content

Commit baf1e68

Browse files
conf1102conf1102
committed
Basic Data Structure implementation In Java
1 parent 25ef1af commit baf1e68

File tree

4 files changed

+165
-30
lines changed

4 files changed

+165
-30
lines changed

‎group20/404130810/src/com/basic/datastructure/ArrayList.java

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -97,12 +97,14 @@ private Object[] growIfNeeded() {
9797

9898
public static void main(String[] args) {
9999
ArrayList list = new ArrayList();
100-
for (int i = 1; i <= 11; i++) {
100+
for (int i = 0; i <= 11; i++) {
101101
list.add(String.valueOf(i));
102102
}
103-
list.add(10,"test");
104-
list.get(10);
105-
list.remove(10);
106-
System.out.println(list);
103+
System.out.println(list.get(11));
104+
//list.add(10,"test");
105+
//list.get(10);
106+
//list.remove(10);
107+
//System.out.println(list);
107108
}
109+
108110
}

‎group20/404130810/src/com/basic/datastructure/LinkedList.java

Lines changed: 84 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -6,27 +6,32 @@ public class LinkedList implements List {
66

77
private int size;
88

9-
public void add(Object o) {
10-
addLast(o);
9+
public void add(Object item) {
10+
addLast(item);
1111
}
1212

13-
public void add(int index, Object o) {
13+
public void add(int index, Object item) {
1414
checkRange(index);
1515
if (index == 0) {
16-
addFirst(o);
16+
addFirst(item);
1717
} else if (index == size) {
18-
addLast(o);
18+
addLast(item);
1919
} else {
20-
20+
Node tmpNode = new Node(item);
21+
Node preNode = get(index - 1);
22+
Node nextNode = get(index + 1);
23+
preNode.next = tmpNode;
24+
tmpNode.next = nextNode;
25+
size ++;
2126
}
2227
}
2328

24-
public Object get(int index) {
29+
public Node get(int index) {
2530
checkRange(index);
2631
if(size > 0){
2732
int loopTimes = 0;
2833
Node p = first;
29-
while(index > loopTimes){
34+
while(index > loopTimes){
3035
p = p.next;
3136
loopTimes ++;
3237
}
@@ -37,47 +42,77 @@ public Object get(int index) {
3742
}
3843

3944
public Object remove(int index) {
40-
return null;
45+
checkRange(index);
46+
Node tmpNode = null;
47+
if(index == 0){
48+
removeFirst();
49+
}else if(index == size -1){
50+
removeLast();
51+
}else{
52+
tmpNode = get(index);
53+
Node preNode = get(index-1);
54+
Node nextNode = get(index + 1);
55+
preNode.next = nextNode;
56+
size --;
57+
}
58+
59+
return tmpNode;
4160
}
4261

4362
public int size() {
4463
return size;
4564
}
4665

47-
private void addFirst(Object o) {
66+
public void addFirst(Object item) {
4867
if (size == 0) {
49-
first = new Node(o);
68+
first = new Node(item);
5069
last = first;
5170
} else {
52-
Node tmpNode = new Node(o);
71+
Node tmpNode = new Node(item);
5372
tmpNode.next = first;
5473
first = tmpNode;
5574
}
5675
size++;
5776
}
5877

59-
private void addLast(Object o) {
78+
public void addLast(Object item) {
6079
if (size == 0) {
61-
first = new Node(o);
80+
first = new Node(item);
6281
last = first;
6382
} else {
64-
last.next = new Node(o);
83+
last.next = new Node(item);
6584
last = last.next;
6685
}
6786
size++;
6887
}
6988

7089
public Object removeFirst() {
7190
Node tmpNode = first;
72-
first = first.next;
73-
size--;
91+
if(tmpNode == null){
92+
last = null;
93+
}else if(size == 2){
94+
first = last;
95+
last = null;
96+
size --;
97+
}else{
98+
first = first.next;
99+
size--;
100+
}
74101
return tmpNode;
75102
}
76103

77104
public Object removeLast() {
78-
Node tmpNode = last;
79-
80-
return null;
105+
Node tmpNode = null;
106+
if(size == 1){
107+
this.removeFirst();
108+
}else if(size >0){
109+
int index = size - 1;
110+
tmpNode = last;
111+
get(index - 1).next = null;
112+
last = get(index - 1);
113+
size --;
114+
}
115+
return tmpNode;
81116
}
82117

83118
private void checkRange(int index) {
@@ -99,19 +134,43 @@ public String toString() {
99134
private static class Node {
100135
private Object item;
101136
private Node next;
102-
103137
Node(Object item) {
104138
this.item = item;
105139
}
106140
}
107141

108142
public static void main(String[] args) {
143+
144+
/*Test add
109145
LinkedList list = new LinkedList();
110-
for (int i = 0; i < 5; i++) {
146+
for (int i = 0; i <= 5; i++) {
111147
list.add(i);
112-
}
113-
list.get(5);
114-
148+
}
149+
list.add(3, "test");
150+
System.out.println(list);
151+
*/
152+
153+
/*Test remove
154+
list.remove(3);
155+
System.out.println(list);
156+
*/
157+
158+
/*Test removeLast and removeFirst
159+
System.out.println(list);
160+
list.removeLast();
161+
System.out.println(list);
162+
list.removeLast();
163+
System.out.println(list);
164+
list.removeLast();
115165
System.out.println(list);
166+
*/
167+
168+
/*Test from Java API
169+
java.util.LinkedList<String> linkedList = new java.util.LinkedList<String>();
170+
linkedList.add("test");
171+
linkedList.removeFirst();
172+
System.out.println(linkedList);
173+
*/
174+
116175
}
117176
}

‎group20/404130810/src/com/basic/datastructure/Queue.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.basic.datastructure;
2+
3+
public class Queue {
4+
LinkedList list = new LinkedList();
5+
private int size;
6+
7+
public void enQueue(Object o){
8+
list.add(o);
9+
size ++;
10+
}
11+
12+
public Object deQueue(){
13+
size --;
14+
return list.removeLast();
15+
}
16+
17+
public boolean isEmpty(){
18+
return list.size() == 0;
19+
}
20+
21+
public int size(){
22+
return size;
23+
}
24+
25+
public static void main(String[] args) {
26+
Queue queue = new Queue();
27+
for (int i = 0; i < 10; i++) {
28+
queue.enQueue(i);
29+
}
30+
queue.deQueue();
31+
System.out.println("Finished");
32+
}
33+
}

‎group20/404130810/src/com/basic/datastructure/Stack.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.basic.datastructure;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
private int size;
6+
7+
public void push(Object o){
8+
elementData.add(o);
9+
size++;
10+
}
11+
public Object pop(){
12+
size --;
13+
return elementData.remove(elementData.size() - 1);
14+
}
15+
16+
/**
17+
* Looks at the object at the top of this stack without removing it from the stack.
18+
* @return Object
19+
*/
20+
public Object peek(){
21+
return elementData.get(elementData.size() - 1);
22+
}
23+
public boolean isEmpty(){
24+
return size == 0;
25+
}
26+
public int size(){
27+
return size;
28+
}
29+
30+
public static void main(String[] args) {
31+
Stack stack = new Stack();
32+
for (int i = 0; i < 10; i++) {
33+
stack.push(i);
34+
}
35+
System.out.println(stack.peek());
36+
37+
stack.pop();
38+
System.out.println("Finished");
39+
}
40+
41+
}

0 commit comments

Comments
 (0)