实现无头节点的单链表_无头结点空链表

class Node{
public int data;
public Node next;

public Node(int data){
this.data=data;
}
}

public class MyLinkedList{
public Node head;

public void addFirst(int data){
Node node=new node(data);
//判断是否是空链表
if(this.head==null){
this.head=node;
}else{
node.next=this.head;
this.head=node;
}
}
public void addLast(int data){
Node node=new Node(data);
//判断是否是空链表
if(this.head==null){
this.head=node;
}else{
Node cur=this.head;
while(cur.next!=null){
cur=cur.next;
}
cur.next=node;
}
}
public void display(){
//判断是否为空
if(this.head==null){
System.out.pintln("空链表");
return;
}
Node cur=this.head;
while(cur!=null){
System.out.print(cur.data+" ");
cur=cur.next;
}
}
public boolean contains(int data){
Node cur=this.head;
while(cur!=null){
if(cur.data==data){
return true;
}
cur=cur.next;
}
return false;
}
public int size(){
int count=0;
Node cur=this.head;
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
public void addIndex(int index,int data){
if(index==0){
//如果插入的位置是第一个那就是头插
addFirst(data);
}else if(index==size()){
//如果插入的位置是最后一个那就是尾插
addLast(data);
}else{
//找到要插入位置的前一个节点
Node cur=searchIndex(index);
Node node=new Node(data);
node.next=cur.next;
cur.next=node;
}
private Node searchIndex(int index){
if(index<0||index>size(){
//插入位置不合法
throw new RuntimeException("index位置不合法");
}
//找到需要插入的位置的前一个位置
Node cur=this.head;
for(int i=0;i<index-1;i++){
cur=cur.next;
}
return cur;
}
public void remove(int data){
//如果是空链表
if(this.head==null){
System.out.println("空链表无法删除");
return;
}
//如果要删除的是头节点
if(this.head.data==data){
this.head=this.head.next;
return;
}
//找到要删除节点的前一个
Node cur=searchPrev(data);
if(cur!=null){
cur.next=cur.next.next;
}else{
System.out.println("找不到该节点");
}
}
private Node searchPrev(int data){
Node cur=this.head;
while(cur.next!=null){
//找到要删除节点的前一个节点
if(cur.next.data==data){
return cur;
}
cur=cur.next;
}
return null;
}
pubic void removeAllKey(int data){
//删除所有值为data的节点

//如果是空链表
if(this.head==null){
System.out.println("空链表无法删除");
return;
}
//先判断除head以外的节点
Node prev=this.head;
Node cur=prev.next;
while(cur!=null){
if(cur.data==data){
prev.next=cur.next;
cur=cur.next;
}else{
//如果有连续相同的cur，先删除再移动prev
prev=cur;
cur=cur.next;
}
}
//如果要删除的是头节点
if(this.head.data==data){
this.head=this.head.next;
}
}
public void clear(){
//写该函数是为了防止内存泄露
this.head=null;
}
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152