Skip to content

Commit afde9da

Browse files
C-BoBoC-BoBo
committed
HomeWork0226
ArrayList,LinkList,Stack,Queue的实现
1 parent d4a25d6 commit afde9da

File tree

12 files changed

+1435
-0
lines changed

12 files changed

+1435
-0
lines changed

‎group05/183127807/HomeWork0226/.idea/misc.xml

Lines changed: 22 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎group05/183127807/HomeWork0226/.idea/modules.xml

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎group05/183127807/HomeWork0226/.idea/vcs.xml

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎group05/183127807/HomeWork0226/.idea/workspace.xml

Lines changed: 1056 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎group05/183127807/HomeWork0226/HomeWork0226.iml

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

‎group05/183127807/HomeWork0226/src/com/coding/basic/ArrayList.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
public class ArrayList implements List {
7+
8+
private static final int DEFAULT_CAPACITY = 100;
9+
10+
private int size = 0;
11+
12+
private Object[] elementData = new Object[DEFAULT_CAPACITY];
13+
14+
public void add(Object o){
15+
ensureCapacity(size+1);
16+
elementData[size] = o;
17+
size++;
18+
}
19+
public void add(int index, Object o){
20+
if (index > size || index < 0) {
21+
throw new ArrayIndexOutOfBoundsException();
22+
}
23+
ensureCapacity(size+1);
24+
for (int i = size;i>index;i--) {
25+
elementData[i] = elementData[i - 1];
26+
}
27+
elementData[index] = o;
28+
size++;
29+
}
30+
31+
public Object get(int index){
32+
if (index > size || index < 0) {
33+
throw new ArrayIndexOutOfBoundsException();
34+
}
35+
return elementData[index];
36+
}
37+
38+
39+
public Object remove(int index){
40+
Object[] removeData = (Object[]) elementData[index];
41+
for (int i =index;i<size()-1;i++) {
42+
elementData[i] = elementData[i + 1];
43+
}
44+
elementData[size] = null;
45+
size--;
46+
47+
return removeData;
48+
}
49+
50+
public int size(){
51+
return size;
52+
}
53+
54+
public Iterator iterator(){
55+
56+
return new ArrayListIterator();
57+
}
58+
59+
private class ArrayListIterator implements Iterator {
60+
private int current = 0;
61+
@Override
62+
public boolean hasNext() {
63+
return current<size();
64+
}
65+
66+
@Override
67+
public Object next() {
68+
if (!hasNext()) {
69+
throw new NoSuchElementException();
70+
}
71+
return elementData[current++];
72+
}
73+
}
74+
75+
76+
public void ensureCapacity(int minCapacity) {
77+
if (minCapacity < elementData.length) {
78+
return;
79+
} else if (minCapacity > elementData.length) {
80+
81+
elementData = Arrays.copyOf(elementData, minCapacity + DEFAULT_CAPACITY);
82+
}
83+
}
84+
85+
}

‎group05/183127807/HomeWork0226/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object data) {
13+
this.data = data;
14+
}
15+
public BinaryTreeNode getLeft() {
16+
return left;
17+
}
18+
public void setLeft(BinaryTreeNode left) {
19+
this.left = left;
20+
}
21+
public BinaryTreeNode getRight() {
22+
return right;
23+
}
24+
public void setRight(BinaryTreeNode right) {
25+
this.right = right;
26+
}
27+
28+
public BinaryTreeNode insert(Object o){
29+
return null;
30+
}
31+
32+
}

‎group05/183127807/HomeWork0226/src/com/coding/basic/Iterator.java

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

‎group05/183127807/HomeWork0226/src/com/coding/basic/LinkedList.java

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
package com.coding.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
7+
private int size ;
8+
9+
private Node current = head;
10+
public LinkedList() {
11+
head = null;
12+
size = 0;
13+
}
14+
15+
public void add(Object o){
16+
Node newNode = new Node();
17+
newNode.data = o;
18+
if (current.next == null)
19+
{
20+
current.next = newNode;
21+
}
22+
23+
while (current.next != null){
24+
current = current.next;
25+
}
26+
current.next = newNode;
27+
size++;
28+
29+
}
30+
public void add(int index , Object o){
31+
32+
Node newNode = new Node();
33+
newNode.data = o;
34+
if (index < 0 || index > size) {
35+
throw new IndexOutOfBoundsException();
36+
}
37+
for (int i = 0; i < index - 2; i++) {
38+
39+
current = current.next;
40+
}
41+
42+
newNode.next = current.next;
43+
current.next = newNode;
44+
size++;
45+
}
46+
public Object get(int index){
47+
48+
49+
if (index < 0 || index > size) {
50+
throw new IndexOutOfBoundsException();
51+
} else if (index == 0) {
52+
return head;
53+
}
54+
for (int i = 0;i<index - 1; i++) {
55+
current = current.next;
56+
}
57+
58+
return current;
59+
}
60+
61+
public Object remove(int index){
62+
for (int i = 1; i <= index; i++) {
63+
64+
if (i == index - 1) {
65+
current.next = current.next.next;
66+
size--;
67+
} else {
68+
current = current.next;
69+
}
70+
71+
}
72+
return null;
73+
}
74+
75+
public int size(){
76+
return size;
77+
}
78+
79+
public void addFirst(Object o){
80+
Node newHead = new Node();
81+
newHead.data = o;
82+
newHead.next = head;
83+
head = newHead;
84+
size++;
85+
}
86+
public void addLast(Object o){
87+
Node newNode = new Node();
88+
newNode.data = o;
89+
while (current.next != null){
90+
current = current.next;
91+
}
92+
current.next = newNode;
93+
size++;
94+
}
95+
public Object removeFirst(){
96+
Node removeHead = head;
97+
head.next = head.next.next;
98+
size--;
99+
return removeHead;
100+
}
101+
public Object removeLast(){
102+
Node theNext = current.next;
103+
Node oldLast;
104+
while(theNext.next != null) {
105+
current = theNext;
106+
theNext = theNext.next;
107+
}
108+
oldLast=current.next;
109+
current.next = theNext.next;
110+
111+
size--;
112+
return oldLast;
113+
}
114+
public Iterator iterator(){
115+
return new LinkedListIterator();
116+
}
117+
118+
public Object head() {
119+
return head;
120+
}
121+
private class LinkedListIterator implements Iterator {
122+
@Override
123+
public boolean hasNext() {
124+
return current.next!=null;
125+
}
126+
127+
@Override
128+
public Object next() {
129+
Node data = (Node) current.data;
130+
current.next = current.next.next;
131+
return data;
132+
}
133+
}
134+
135+
136+
private static class Node{
137+
Object data;
138+
139+
Node next;
140+
141+
}
142+
}

‎group05/183127807/HomeWork0226/src/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.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+
}

‎group05/183127807/HomeWork0226/src/com/coding/basic/Queue.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.coding.basic;
2+
3+
public class Queue {
4+
private LinkedList linkedList = new LinkedList();
5+
6+
public void enQueue(Object o){
7+
linkedList.addLast(o);
8+
}
9+
10+
public Object deQueue(){
11+
Object removeQueue = linkedList.removeFirst();
12+
return removeQueue;
13+
}
14+
15+
public boolean isEmpty(){
16+
return linkedList.head()==null;
17+
}
18+
19+
public int size(){
20+
return linkedList.size();
21+
}
22+
}

‎group05/183127807/HomeWork0226/src/com/coding/basic/Stack.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.coding.basic;
2+
3+
import java.util.EmptyStackException;
4+
5+
public class Stack {
6+
private ArrayList elementData = new ArrayList();
7+
int size = elementData.size();
8+
9+
public void push(Object o){
10+
elementData.add(o);
11+
size++;
12+
}
13+
14+
public Object pop(){
15+
if(this.isEmpty()==true)
16+
{
17+
throw new EmptyStackException();
18+
}
19+
ArrayList popData = (ArrayList) elementData.remove(elementData.size()-1);
20+
size--;
21+
22+
return popData;
23+
24+
}
25+
26+
public Object peek(){
27+
return elementData.get(elementData.size()-1);
28+
}
29+
public boolean isEmpty(){
30+
return elementData.size()==0;
31+
}
32+
public int size(){
33+
return size;
34+
}
35+
}

0 commit comments

Comments
 (0)