- 分享一下我用java实现的链表
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
152public class LinkList<T> {
private Node<T> head; //头节点
private Node<T> tail; //尾节点
/**
* 构造空链表
*/
public LinkList(){
head = tail = null;
}
/**
* 链表内部的节点类
*/
private static class Node<T>{
T data; //节点的数据
Node<T> next; //该节点指向下一个节点的指针
Node(T data){
this.data = data;
this.next = null;
}
}
/**
* 为空链表增加头节点
*/
public void addHead(T point){
this.head = new Node<T>(point);
if(tail == null){
tail = head;
}
}
/**
* 为链表增加尾节点
*/
public void addTail(T point){
tail = new Node<T>(point);
head.next = tail;
}
/**
* 插入节点（头插法）
*/
public void addNode(T point){
if(this.head==null) //添加头节点
addHead(point);
else if(this.tail==this.head) //在头节点后添加尾节点
addTail(point);
else{
Node<T> newNode = new Node<T>(point);
newNode.next = head.next;
head.next = newNode;
}
}
/**
* 删除节点（通过数据值）
*/
public void deleteNode(T data){
Node<T> curr = head ,pre = null;
boolean flag = false; //判断要删除的节点是否存在
while(curr != null){
if(curr.data.equals(data)){
if (curr==head){ //删除头节点
System.out.println("delete the head Node");
head = curr.next;
flag = true;
}else if (curr==tail){ //删除尾节点
System.out.println("delete the tail Node");
tail = pre;
pre.next = null;
flag = true;
}else { //删除中间节点
System.out.println("delete the center Node");
pre.next = curr.next;
flag = true;
}
}
pre = curr;
curr = curr.next;
}
if (flag == false)
System.out.println("链表中不存在该数据");
}
/**
* 查找链表中的元素（通过位置）
*/
public void findKth(T point){
Node<T> curr = head , pre = null;
int k = 1;
boolean flag = false;
while (curr != null){
if(point.equals(k)){
System.out.println("第"+k+"位的值是"+curr.data);
flag = true;
}
pre = curr;
curr = curr.next;
k++;
}
if(flag==false)
System.out.println("查找的位置在链表中不存在");
}
/**
* 查找链表中的元素（通过值）
*/
public void findByValue(T data){
Node<T> curr = head ;
int k = 1;
boolean flag = false;
while(curr!=null){
if(curr.data==data){
System.out.println("查找的值在链表中的第"+k+"位");
flag = true;
}
curr = curr.next;
k++;
}
if(flag==false)
System.out.println("查找的值在链表中不存在");
}
/**
* 输出链表
*/
public void printlnLink(){
Node<T> curr = this.head;
if(curr==null){
System.out.println("linklist is null");
}else{
while(curr!=null){
System.out.print(curr.data+" ");
curr = curr.next;
}System.out.println();
}
}
public static void main(String[] args){
LinkList linkList = new LinkList<Integer>();
linkList.addNode(5);
linkList.addNode(8);
linkList.addNode(10);
linkList.addNode(6);
linkList.addNode(9);
System.out.println("TailNode: "+linkList.tail.data);
linkList.deleteNode(8);
linkList.printlnLink();
linkList.findByValue(5);
linkList.findKth(10);
System.out.print("");
}
}