1
2
3
4
5
6
7
8
9
public interface MyList {
public int size();
public void add(Object obj);
public Object remove(int index);
public void set(int index,Object element);
public Object get(int index);
public boolean contians(Object obj);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import org.apache.log4j.NDC;
import java.util.LinkedList;
public class MyLinkedList implements MyList {
//记录链表中有多少对象
int size;
//准备一个空链表
Node first;
//准备一个空尾
Node last;
private static class Node{
Object item;//记录自己节点的数据
Node prev;//记录上一个节点
Node next;//记录下一个节点
public Node(Node prev,Object item,Node next){
this.prev=prev;
this.item=item;
this.next=next;
}
}
@Override
public int size() {
return this.size;
}
@Override
public void add(Object obj) {
//先把链表的最后一环存放到变量中
Node l = last;//一种l==null 说明链表中没有任何人 l!=null说明链表中有人 把尾环存放到l中
//建造一个新环 把环的上一环设成原来的尾环
Node newNode = new Node(l,obj,null);
//把新环存放到尾环中
last = newNode;
//判断链表中是否第一次存放环 如果是 就把首环设置为新环 如果不是就把原来最后一环的下一环设置为新环
if(l == null) {
first=newNode;
}else {
l.next=newNode;
}
//链表长度+1
size++;
}
@Override
public Object remove(int index) {
if(index>=size) {
throw new IndexOutOfBoundsException("下标越界");
}
//获取要删除的值
Object oldValue = get(index);
// 首先判断用户要删除的是首环 还是尾环
// 删除首环就直接让first指向第二环 第二环的上一环为null
// 删除尾环就直接让last指向倒数第二环 并让倒数第二环的下一环为null
if(index == 0 ) {
//判断链表中有几个元素 如果只有一个元素则让首尾都设置为null
if (size == 1) {
first = last = null;
} else {
first = first.next;
first.prev = null;
}
size--;
}else if(index == size-1){
//删除尾环处理
if(size==1){
first=last=null;
}else {
last=last.prev;
last.next=null;
}
size--;
}else {
//删除中间环
Node delNode = null;
for (int i=0;i<index;i++) {
delNode=delNode.next;
}
//当前删除环的上一环的下一环指向删除环的下一环
delNode.prev.next=delNode.next;
//再让删除环的下一环的上一环指向删除环的上一环
delNode.next.prev=delNode.prev;
}
size--;
return null;
}
@Override
public void set(int index, Object element) {
Node temp = first;
for(int i=0;i<index;i++){
temp=temp.next;
}
temp.item=element;
}
@Override
public Object get(int index) {
Object obj = null;
Node temp=first;
for(int i=0;i<index;i++){
temp=temp.next;
}
return temp.next;
}
@Override
public boolean contians(Object obj) {
boolean has=false;
for (int i=0;i<=size;i++) {
if(get(i)==obj){
has = true;
break;
}
}
return has;
}
@Override
public String toString() {
String str="[";
Node temp = first;
for (int i=0;i<size;i++) {
if (i==size-1) {
str += temp.item;
}else {
str += temp.item+",";
}
temp = temp.next;
str+="]";
}
return str;
}
}