Skip to content

Commit 65b0d9b

Browse files
heyucoolheyucool
authored
Merge pull request onlyliuxin#11 from zhoubofeng/master
ArrayList,LinkedList,Queue,Stack
2 parents 96dd311 + 820adc2 commit 65b0d9b

File tree

5 files changed

+465
-0
lines changed

5 files changed

+465
-0
lines changed

‎group14/598808350/20170219.txt

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
���� CPU���ڴ棬 Ӳ�̣�ָ��֮��Ĺ�ϵ
2+
3+
http://blog.sina.com.cn/s/blog_986d02cd0102xncn.html
4+
5+
QQ:598808350

‎group14/598808350/2017project/src/org/learning/container/ArrayList.java

Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,186 @@
1+
package org.learning.container;
2+
3+
4+
public class ArrayList {
5+
6+
private Object [] objs = null;
7+
private int index = -1;
8+
public ArrayList(){
9+
objs = new Object[5];
10+
}
11+
public ArrayList(int size){
12+
objs = new Object[size];
13+
}
14+
/**
15+
* 返回一个新的数组
16+
* @param src
17+
* @param src_index
18+
* @param dest
19+
* @param dest_index
20+
* @param length
21+
* @return
22+
*/
23+
private static Object[] copy(Object[] src,int src_index,Object[] dest,int dest_index,int length){
24+
System.arraycopy(src, src_index, dest, dest_index, length);
25+
return dest;
26+
}
27+
28+
public void add(Object obj){
29+
if(this.index == objs.length-1) {
30+
Object[] dest = new Object[objs.length+5];
31+
objs = copy(objs,0,dest,0,objs.length);
32+
}
33+
this.index ++;
34+
objs[this.index] = obj;
35+
}
36+
37+
public void add(int index,Object obj){
38+
if(index-1 > this.index || index < 0){
39+
throw new IndexOutOfBoundsException();
40+
}
41+
Object[] dest = new Object[objs.length+5];
42+
if(index == 0){
43+
dest[index] = obj;
44+
dest =copy(objs,index,dest,index+1,getSize());
45+
objs = dest;
46+
}else if(index == getSize()){
47+
objs[index] = obj;
48+
}else{
49+
dest = copy(objs,0,dest,0,index);//前部分
50+
dest[index] = obj; //中间部分
51+
dest =copy(objs,index,dest,index+1,getSize()-index);//后部分
52+
objs = dest;
53+
}
54+
this.index++;
55+
}
56+
57+
public Object get(int index){
58+
if(index > this.index || index <0){
59+
throw new IndexOutOfBoundsException();
60+
}
61+
return objs[index];
62+
}
63+
64+
public boolean isEmpty(){
65+
if(objs == null || this.index == -1){
66+
return true;
67+
}
68+
return false;
69+
}
70+
71+
public int getSize(){
72+
return this.index+1;
73+
}
74+
75+
public boolean remove(int index){
76+
if (index <0 || index > objs.length){
77+
throw new IndexOutOfBoundsException();
78+
}
79+
Object[] dest = new Object[this.index];
80+
dest = copy(objs,0,dest,0,index);//前部分
81+
dest = copy(objs,index+1,dest,index,this.index-index);//后部分
82+
objs = dest;
83+
this.index --;
84+
return true;
85+
}
86+
public boolean remove(Object obj){
87+
for(int i=0;i<=this.index;i++){
88+
if(obj==null ? get(i)==null : obj.equals(get(i))) {
89+
remove(i); //i 即 当前元素的下标识
90+
return true;
91+
}
92+
}
93+
return false;
94+
}
95+
public static void print(Object obj){
96+
System.out.println(obj);
97+
}
98+
99+
public static void main(String [] args){
100+
ArrayList al = new ArrayList();
101+
/*print(al.isEmpty());
102+
al.add("a1");
103+
print(al.isEmpty());
104+
print(al.getSize());
105+
print(al.get(0));
106+
print(al.get(1));*/
107+
al.add("a0");
108+
al.add("a1");
109+
al.add("a2");
110+
al.add("a3");
111+
al.add("a4");
112+
al.add("a5");
113+
114+
//al.remove(0);
115+
//al.remove(5);
116+
//al.remove(2);
117+
/*boolean flag = al.remove("a7");
118+
print(flag);
119+
for(int i=0;i<al.getSize();i++){
120+
print(al.get(i));
121+
}*/
122+
/*print(al.get(0));
123+
print(al.get(5));
124+
print(al.get(6));*/
125+
//print(al.getSize());
126+
//print(al.get(-1)); ok
127+
//print(al.get(0));
128+
//print(al.get(5));
129+
130+
//print(al.get(6));
131+
132+
/*for(int i=0;i<al.getSize();i++){
133+
print(al.get(i));
134+
}
135+
print("---------------------以上内容为add");*/
136+
137+
al.add(0, "a00");
138+
al.add(5, "a6");
139+
for(int i=0;i<10;i++){
140+
print(al.get(i));
141+
}
142+
print("---------------------以上内容为add(index,obj)");
143+
144+
/*al.add(6, "a6");
145+
al.add("a7");
146+
for(int i=0;i<al.getSize();i++){
147+
print(al.get(i));
148+
}
149+
print("---------------------以上内容为add(index,obj)");*/
150+
/*al.add("a0");
151+
al.add("a1");
152+
al.add("a2");
153+
al.add("a3");
154+
al.add("a4");
155+
al.add("a5");
156+
al.add("a6");
157+
print(al.isEmpty());
158+
print(al.getSize());
159+
print(al.get(0));
160+
print(al.get(5));
161+
//al.add(5,"5.5");
162+
163+
for(int i=0;i<al.getSize();i++){
164+
print("i"+i+":"+(al.get(i)));
165+
}
166+
167+
//print(al.remove("a4"));
168+
print(al.getSize());
169+
print(al.remove(2));
170+
print("删除后");
171+
print(al.getSize());
172+
for(int i=0;i<al.getSize();i++){
173+
print("i"+i+":"+(al.get(i)));
174+
}
175+
print("-----------add a7");
176+
al.add("a7");
177+
al.add(2,"a2");*/
178+
179+
/*for(int i=0;i<al.getSize();i++){
180+
print("i"+i+":"+(al.get(i)));
181+
}
182+
print(al.get(6));*/
183+
184+
}
185+
186+
}

‎group14/598808350/2017project/src/org/learning/container/LinkedList.java

Lines changed: 183 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,183 @@
1+
package org.learning.container;
2+
3+
public class LinkedList {
4+
5+
private Node element = new Node(null,null,null);
6+
7+
public LinkedList(){
8+
this.element.next = (this.element.prev = this.element);
9+
}
10+
11+
12+
13+
public Node getElement() {
14+
return element;
15+
}
16+
17+
public void setElement(Node element) {
18+
this.element = element;
19+
}
20+
21+
22+
private int index = 0;
23+
24+
25+
26+
27+
28+
29+
30+
public void add(Object obj){
31+
add(obj,this.element);
32+
}
33+
public Node add(Object obj,Node node){
34+
// 将节点(节点数据是obj)添加到表头(element)之前
35+
// 即，将节点添加到双向链表的末端
36+
Node childNode = new Node(obj,node,node.prev);
37+
childNode.prev.next = childNode;
38+
childNode.next.prev = childNode;
39+
index += 1;
40+
return childNode;
41+
}
42+
43+
/*public void add(int index,Object obj){
44+
for(int i=0;i<size();i++){
45+
if(i == index){
46+
add(obj);
47+
}
48+
}
49+
}*/
50+
51+
public void addFirst(Object obj){
52+
//add(0,obj);
53+
add(obj,this.element.next);
54+
}
55+
56+
public Object getFirst(){
57+
return element.next.obj;
58+
}
59+
60+
public void addLast(Object obj){
61+
//add(size(),obj);
62+
add(obj,this.element);
63+
}
64+
65+
public Object getLast(){
66+
return element.prev.obj;
67+
}
68+
public Node get(int index){
69+
Node obj = null;
70+
for(int i=0;i<size();i++){
71+
if(i == index) obj = element.next;
72+
}
73+
return obj;
74+
}
75+
public int size(){
76+
return this.index ;
77+
}
78+
public Object remove(Node node){
79+
Object e = node.obj;
80+
81+
node.prev.next = node.next;
82+
node.next.prev = node.prev;
83+
84+
node.prev = node.next = null;
85+
node.obj = null;
86+
index -=1;
87+
return e;
88+
}
89+
90+
public void removeFirst(){
91+
remove(this.element.next);
92+
}
93+
public void removeLast(){
94+
remove(this.element.prev);
95+
}
96+
97+
class Node{
98+
Object obj ; //存放主体
99+
Node prev ; //存放上一个对象
100+
Node next ; //存放下一个对象。
101+
public Node(Object obj,Node next,Node prev){
102+
this.obj = obj;
103+
this.next = next;
104+
this.prev = prev;
105+
}
106+
}
107+
108+
109+
public static void main(String [] args){
110+
/*Object [] objs = new Object[3];
111+
112+
Object [] c0 = new Object[2];
113+
c0[0] = "c0";
114+
Object [] c1 = new Object[2];
115+
c1[0] = "c1";
116+
Object [] c2 = new Object[2];
117+
c2[0] = "c2";
118+
119+
c0[1] = c1;
120+
c1[1] = c2;
121+
c2[1] = null;
122+
123+
objs[2] = c2;
124+
objs[1] = c1;
125+
objs[0] = c0;
126+
127+
for(int i=0;i<objs.length;i++){
128+
System.out.println("i="+i);
129+
System.out.println(((Object[])objs[i])[0]);
130+
if((Object[])((Object[])objs[i])[1] == null){
131+
continue;
132+
}
133+
Object[] obj = (Object[])((Object[])objs[i])[1];
134+
135+
System.out.println(obj[0]);
136+
System.out.println(obj[1]);
137+
}*/
138+
LinkedList list = new LinkedList();
139+
list.add("test0");
140+
list.add("test1");
141+
list.add("test2");
142+
143+
list.addFirst("first");
144+
list.addLast("last");
145+
146+
System.out.println(list);
147+
System.out.println("list.getFirst()"+list.getFirst());
148+
System.out.println("list.getLast()"+list.getLast());
149+
150+
151+
for(int i=0;i<list.size();i++){
152+
Node tmp = list.get(i);
153+
print(tmp.obj);
154+
}
155+
156+
System.out.println("----------------------------------------");
157+
java.util.LinkedList linkedList = new java.util.LinkedList();
158+
linkedList.add("object");
159+
linkedList.addFirst("first");
160+
//linkedList.addLast("last");
161+
162+
163+
for(Object obj : linkedList){
164+
print(obj);
165+
}
166+
167+
print("--------------------添加后输出--------------------------------------");
168+
169+
print("-----------------删除first，last---------------------------------------");
170+
171+
linkedList.removeFirst();
172+
linkedList.removeLast();
173+
for(Object obj : linkedList){
174+
print(obj);
175+
}
176+
177+
178+
}
179+
180+
public static void print(Object obj){
181+
System.out.println(""+obj);
182+
}
183+
}

0 commit comments

Comments
 (0)