Skip to content

Commit 6e681b2

Browse files
zhijiaxinyuzhijiaxinyu
committed
完成了ArrayList 和 LinkedList
1 parent abe5ce8 commit 6e681b2

File tree

5 files changed

+407
-0
lines changed

5 files changed

+407
-0
lines changed

‎group10/630505243/src/com/coding/basic/ArrayList.java

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package com.coding.basic;
2+
3+
public class ArrayList implements List {
4+
5+
private int size = 0;
6+
7+
private Object[] elementData = new Object[100];
8+
9+
public void add(Object o){
10+
if(o!=null){
11+
elementData[size] = o;
12+
if(size<100-1){
13+
size++;
14+
}else{
15+
Object[] temp = new Object[(size+1)+100];
16+
System.arraycopy(elementData, 0, temp, 0, size);
17+
elementData = temp;
18+
size++;
19+
}
20+
}
21+
22+
}
23+
public void add(int index, Object o){
24+
if(index<=size){
25+
26+
if(index<elementData.length-1){
27+
//新增元素位置处于数组内部
28+
Object tmp = elementData[index];
29+
//新增元素位置后的所有元素后移一位
30+
Object[] temps = new Object[elementData.length+1];
31+
System.arraycopy(elementData, 0, temps, 0, elementData.length);
32+
for(int i=temps.length;i>=index;i--){
33+
if(i==index){
34+
temps[index] = tmp;
35+
}else{
36+
temps[i]=temps[i-1];
37+
}
38+
}
39+
elementData = temps;
40+
41+
}else if(index==elementData.length-1){
42+
//新增元素位置处于数组右边界
43+
Object[] temp = new Object[(size+1)+100];
44+
System.arraycopy(elementData, 0, temp, 0, size);
45+
elementData = temp;
46+
elementData[index] = o;
47+
}
48+
}
49+
}
50+
51+
public Object get(int index){
52+
if(index<=size){
53+
return elementData[index];
54+
}else{
55+
return null;
56+
}
57+
}
58+
59+
public Object remove(int index){
60+
Object rtnObj = null;
61+
if(index<=size){
62+
if(index<elementData.length-1){
63+
rtnObj = elementData[index];
64+
for(int i=index;i<size;i++){
65+
elementData[i] = elementData[i+1];
66+
}
67+
elementData[size] = null;
68+
size--;
69+
return rtnObj;
70+
71+
}else if(index==elementData.length-1){
72+
rtnObj = elementData[size];
73+
elementData[size] = null;
74+
size--;
75+
return rtnObj;
76+
}
77+
}
78+
return null;
79+
}
80+
81+
public int size(){
82+
return this.size;
83+
}
84+
85+
public Iterator iterator(){
86+
return null;
87+
}
88+
89+
}

‎group10/630505243/src/com/coding/basic/ArrayListTest.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.coding.basic;
2+
3+
import static org.junit.Assert.*;
4+
5+
import org.junit.After;
6+
import org.junit.Before;
7+
import org.junit.Test;
8+
9+
public class ArrayListTest {
10+
ArrayList list = null;
11+
Integer a = new Integer(1);
12+
Integer b = new Integer(2);
13+
Integer c = new Integer(3);
14+
15+
@Before
16+
public void setUp() throws Exception {
17+
list = new ArrayList();
18+
}
19+
20+
@After
21+
public void tearDown() throws Exception {
22+
}
23+
24+
@Test
25+
public void testAddObject() {
26+
list.add(a);
27+
list.add(b);
28+
list.add(c);
29+
System.out.println(list.size());
30+
for(int i=0;i<list.size();i++){
31+
System.out.println(list.get(i));
32+
}
33+
System.out.println("-----------------");
34+
list.remove(3);
35+
for(int i=0;i<list.size();i++){
36+
System.out.println(list.get(i));
37+
}
38+
fail("Not yet implemented");
39+
}
40+
41+
@Test
42+
public void testAddIntObject() {
43+
fail("Not yet implemented");
44+
}
45+
46+
@Test
47+
public void testGet() {
48+
fail("Not yet implemented");
49+
}
50+
51+
@Test
52+
public void testRemove() {
53+
fail("Not yet implemented");
54+
}
55+
56+
@Test
57+
public void testSize() {
58+
fail("Not yet implemented");
59+
}
60+
61+
@Test
62+
public void testIterator() {
63+
fail("Not yet implemented");
64+
}
65+
66+
}

‎group10/630505243/src/com/coding/basic/LinkedList.java

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
package com.coding.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;//头节点
6+
private Node last;//尾节点
7+
private int size=0;//长度
8+
9+
public void add(Object o){
10+
if(last==null){
11+
head = new Node(o, null);
12+
last = head;
13+
}else{
14+
Node nod = last;
15+
nod.next = new Node(o,null);
16+
last = nod.next;
17+
}
18+
size++;
19+
}
20+
public void add(int index , Object o){
21+
if(last==null){
22+
head = new Node(o,null);
23+
last = head;
24+
}else{
25+
//找到index的前一节点
26+
Node preNode = getNextNode(head, index-1);
27+
//index的原有节点
28+
Node node = getNextNode(preNode,index);
29+
//放在index前节点之后，放在原有index节点之前
30+
preNode.next = new Node(o,node);
31+
}
32+
this.size++;
33+
34+
}
35+
36+
public Object get(int index){
37+
return getNextNode(head,index);
38+
}
39+
public Object remove(int index){
40+
//获取删除点的前一节点
41+
Node preNode = getNextNode(head,index-1);
42+
Node node = getNextNode(head,index);
43+
if(node.next!=null){
44+
preNode.next = getNextNode(head,index+1);
45+
}else{
46+
preNode.next = null;
47+
}
48+
this.size--;
49+
return node;
50+
}
51+
52+
/**
53+
* 递归寻找下一节点
54+
* @param node 参照节点
55+
* @param index 距离参照节点的距离
56+
* @return
57+
*/
58+
private Node getNextNode(Node node,int index){
59+
if(index==0){
60+
return node;
61+
}
62+
Node rtnNode = null;
63+
if(node.next==null){
64+
return rtnNode;//最后一个节点的下一节点为空
65+
}else{
66+
return getNextNode(node.next,index-1);
67+
}
68+
}
69+
70+
public int size(){
71+
return this.size;
72+
}
73+
74+
public void addFirst(Object o){
75+
Node node = new Node(o,head);
76+
this.head = node;
77+
this.size++;
78+
}
79+
public void addLast(Object o){
80+
Node newLast = new Node(o, null);
81+
Node node = last;
82+
node.next = newLast;
83+
last = newLast;
84+
this.size++;
85+
}
86+
public Object removeFirst(){
87+
if(head==null){
88+
return null;
89+
}else{
90+
if(head.next==null){
91+
head.data = null;
92+
size--;
93+
return head;
94+
}else{
95+
Node node = head;
96+
head = node.next;
97+
size--;
98+
return node;
99+
}
100+
}
101+
}
102+
public Object removeLast(){
103+
if(last==null){
104+
return null;
105+
}else{
106+
//获取原倒数第二节点
107+
Node preLast = getNextNode(head, size-2);
108+
Node orgLast = last;
109+
preLast.next = null;
110+
last = preLast;
111+
size--;
112+
return orgLast;
113+
}
114+
}
115+
public Iterator iterator(){
116+
return null;
117+
}
118+
119+
120+
private static class Node{
121+
Object data;
122+
Node next;
123+
public Node(Object o,Node next){
124+
this.data = o;
125+
this.next = next;
126+
}
127+
@Override
128+
public String toString() {
129+
StringBuffer sb = new StringBuffer();
130+
sb.append("[");
131+
sb.append("data = "+this.data);
132+
if(next!=null){
133+
sb.append(" ; next = "+this.next.data+" \n");
134+
}else{
135+
sb.append(" ; next = null");
136+
}
137+
sb.append("]");
138+
return sb.toString();
139+
}
140+
141+
142+
}
143+
}

0 commit comments

Comments
 (0)