学习学习,不要废话,先上图

线性表的单链表存储图示

用C写半天搞不定,回归java就比较可爱了,记录一下线性表的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
/**
* 单向链表
*
* @author Lison-Liou
*
*/
public class MyLink {

/**
* 单个节点
* @author Lison-Liou
*
*/
public class Node {
int data = 0;
Node next;

public Node() {
}

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

Node head = null;

/**
* 获取长度
* @return
*/
public int size() {
if (head == null)
return 0;

int length = 0;
Node tmp = head;
while (tmp.next != null) {
length += 1;
tmp = tmp.next;
}

return length + 1;
}

/**
* 增加节点, 默认在链表末尾增加
*
* @param data
*/
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
}

/**
* 在指定的索引位置之后增加节点
* @param data
* @param position
*/
public void addNode(int data, int position) {

Node newNode = new Node(data);

Node find = findNode(position);
Node next = find.next;

find.next = newNode;
newNode.next = next;
}

/**
* 删除指定位置的节点
*
* @param position
*/
public void deleteNode(int position) {
Node prev = findNode(position - 1);
Node next = prev.next.next;

prev.next = next;
}

/**
* 按位置查找节点
*
* @param position
* @return
*/
public Node findNode(int position) {
if (head == null && position != 0)
return null;
else if (head != null && position == 0)
return head;
else if (position > size() - 1) {
return null;
} else {
int i = 0;
Node tmp = head;
while (i < position) {
if (i == position)
return tmp;

if (tmp != null)
tmp = tmp.next;

i++;
}

return tmp;
}
}

@Override
public String toString() {
Node tmp = head;

while (tmp != null) {

System.out.print(tmp.data + "\t");
tmp = tmp.next;
}

System.out.println("\r\n");
return 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
MyLink link = new MyLink();

//增加10个节点, 随机数
for (int i = 0; i < 10; i++) {
System.out.print(i + " ");
link.addNode(random.nextInt(10));
}

System.out.println("\r\nLENGTH: " + link.size());
System.out.println("链表数据");
link.toString();

System.out.println("查找索引位置为5的节点");
MyLink.Node find = link.findNode(5);
if (find != null)
System.out.println(find.data);
else
System.out.println("NOT FOUND");

System.out.println("删除索引位置为2的节点");
link.deleteNode(2);
link.toString();

System.out.println("在指定位置增加节点");
link.addNode(99,2);
link.toString();