Skip to content

Commit 683079a

Browse files
author
luoziyihao
committed
LinkedList 0.1
1 parent 2197ce3 commit 683079a

File tree

3 files changed

+153
-43
lines changed

3 files changed

+153
-43
lines changed

‎group17/1204187480/code/homework/basic/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ public void add(Object o) {
3333
}
3434

3535
public void add(int index, Object o) {
36-
checkIndex(index);
36+
checkForAdd(index);
3737
enLargeElementData();
3838
// 备份 index 处及后面的数据
3939
Object[] elementsBehindIndex = backBehindElements(elementData, index);
@@ -66,6 +66,12 @@ private void checkIndex(int index) {
6666
}
6767
}
6868

69+
private void checkForAdd(int index) {
70+
if (index < 0 || index > size) {
71+
throw new ArrayIndexOutOfBoundsException(String.format("index=%s, size=%s", index, size));
72+
}
73+
}
74+
6975
public Object remove(int index) {
7076
checkIndex(index);
7177
Object[] back = backBehindElements(elementData, index + 1);

‎group17/1204187480/code/homework/basic/src/main/java/com/coding/basic/LinkedList.java

Lines changed: 121 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,125 @@
11
package com.coding.basic;
22

33
public class LinkedList implements List {
4-
5-
private Node head;
6-
7-
public void add(Object o){
8-
9-
}
10-
public void add(int index , Object o){
11-
12-
}
13-
public Object get(int index){
14-
return null;
15-
}
16-
public Object remove(int index){
17-
return null;
18-
}
19-
20-
public int size(){
21-
return -1;
22-
}
23-
24-
public void addFirst(Object o){
25-
26-
}
27-
public void addLast(Object o){
28-
29-
}
30-
public Object removeFirst(){
31-
return null;
32-
}
33-
public Object removeLast(){
34-
return null;
35-
}
36-
public Iterator iterator(){
37-
return null;
38-
}
39-
40-
41-
private static class Node{
42-
Object data;
43-
Node next;
44-
45-
}
4+
5+
private Node head;
6+
private int size = 0;
7+
8+
public void add(Object o) {
9+
Node newNode = new Node(o, null);
10+
if (head == null) {
11+
head = newNode;
12+
} else {
13+
node(size - 1).next = newNode;
14+
}
15+
size++;
16+
}
17+
18+
public void add(int index, Object o) {
19+
checkForAdd(index);
20+
if (index == size) {
21+
add(o);
22+
}else {
23+
Node newNode = new Node(o, null);
24+
if (index == 0){
25+
addFirst(o);
26+
} else {
27+
Node preNode = node(index - 1);
28+
Node now = preNode.next;
29+
preNode.next = newNode;
30+
newNode.next = now;
31+
size++;
32+
}
33+
}
34+
35+
}
36+
37+
private Node node(int index) {
38+
Node x = head;
39+
for (int i = 0; i < index; i++) {
40+
x = x.next;
41+
}
42+
return x;
43+
}
44+
45+
public Object get(int index) {
46+
checkIndex(index);
47+
return node(index).data;
48+
}
49+
50+
/**
51+
* 让被删除的引用的持有者指向下一个节点
52+
* @param index
53+
* @return
54+
*/
55+
public Object remove(int index) {
56+
final Object ret;
57+
checkIndex(index);
58+
if (index == 0) {
59+
Node removeNode = head;
60+
ret = head.data;
61+
head = removeNode.next;
62+
} else {
63+
Node pre = node(index - 1);
64+
Node removeNode = pre.next;
65+
ret = removeNode.data;
66+
pre.next = removeNode.next;
67+
}
68+
size--;
69+
return ret;
70+
}
71+
72+
public int size() {
73+
return size;
74+
}
75+
76+
public void addFirst(Object o) {
77+
head = new Node(o, head);;
78+
size++;
79+
}
80+
81+
public void addLast(Object o) {
82+
add(o);
83+
}
84+
85+
public Object removeFirst() {
86+
if (size == 0){
87+
return null;
88+
}else {
89+
return remove(0);
90+
}
91+
}
92+
93+
public Object removeLast() {
94+
return remove(size - 1);
95+
}
96+
97+
public Iterator iterator() {
98+
return null;
99+
}
100+
101+
private void checkIndex(int index) {
102+
if (index < 0 || index >= size) {
103+
throw new ArrayIndexOutOfBoundsException(String.format("index=%s, size=%s", index, size));
104+
}
105+
}
106+
107+
private void checkForAdd(int index) {
108+
if (index < 0 || index > size) {
109+
throw new ArrayIndexOutOfBoundsException(String.format("index=%s, size=%s", index, size));
110+
}
111+
}
112+
113+
private static class Node {
114+
Object data;
115+
Node next;
116+
117+
public Node() {
118+
}
119+
120+
public Node(Object data, Node next) {
121+
this.data = data;
122+
this.next = next;
123+
}
124+
}
46125
}

‎group17/1204187480/code/homework/basic/src/test/java/com/coding/api/ArrayListTest.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.coding.api;
2+
3+
import org.junit.Test;
4+
import org.slf4j.Logger;
5+
import org.slf4j.LoggerFactory;
6+
7+
import java.util.ArrayList;
8+
import java.util.Arrays;
9+
import java.util.List;
10+
11+
/**
12+
* Created by luoziyihao on 2/25/17.
13+
*/
14+
public class ArrayListTest {
15+
16+
private final Logger logger = LoggerFactory.getLogger(this.getClass());
17+
18+
@Test
19+
public void testAdd(){
20+
List<Object> list = new ArrayList<Object>(Arrays.asList(0, 1, 2, 3));
21+
logger.info("list={}", list);
22+
list.add(5, 2);
23+
logger.info("list={}", list);
24+
}
25+
}

0 commit comments

Comments
 (0)