Singly Linked List

Last updated on January 9, 2023 pm

单向链表——data+next,只能从头向后遍历,头节点(head node)不存储信息。

定义结点(node)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class HeroNode {
public int no;
public String name;
public String nickName;
public HeroNode next;

//constructor
public HeroNode(int hNo, String hName, String hNickName) {
this.no = hNo;
this.name = hName;
this.nickName = hNickName;
}

@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickName + "]";
}
}

定义单链表(Singly Linked List)

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
//singly linked list and the create and delete of it
class SingleLinkedList {
//head node
private HeroNode head = new HeroNode(0, "", "");

//create
public void add(HeroNode heroNode) {
HeroNode temp = head;
//find the last node of the linked list
while (true) {
if (temp.next == null) {
break;
}

temp = temp.next;
}
temp.next = heroNode;
}

public HeroNode getHead() {
return head;
}

//another create
//add the new node to the right place by order
//if the no has existed, print error message
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean isExist = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > heroNode.no) {
break;
}
if (temp.next.no == heroNode.no) {
isExist = true;
break;
}
temp = temp.next;
}

if (isExist) {
System.out.println("This hero could not be added for the no of him(her) has existed.");
System.out.println("The no is " + heroNode.no + ".");
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}

//print out
public void showList() {
if (head.next == null) {
System.out.println("This linked list is empty.");
return;
}

HeroNode temp = head.next;
while (true) {
if (temp == null) {
break;
}

System.out.println(temp);
temp = temp.next;
}
}

//delete
public void delNode(int no) {
HeroNode temp = head;
boolean flag = false; //whether we found the node we need to delete
while (true) {
if (temp.next == null) { //whether we reach the end of the nodelist
break;
}
if (temp.next.no == no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("The node doesn't exist.");
}
}
}

其他方法

获取链表长度(get the length of the List)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* get the number of node in a linked list
*
* @param head head node
* @return number of node
*/
public static int getNodeLength(HeroNode head) {
if (head.next == null) {
return 0;
}
int length = 0;
HeroNode temp = head.next;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}

查找单链表中的倒数第k个结点(find the last k one node of a singly linked list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//查找单链表中倒数第k个结点
//1. 编写一个方法,接收head结点与index值
//2. index表示单链表中的倒数第k个结点
//3. 先把链表从头到尾遍历一遍,得到总长度size
//4. 从链表头开始遍历到第(size - index)个
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}
int size = getNodeLength(head);
if (index <= 0 || index > size) {
return null;
}
HeroNode temp = head.next;
for (int i = 0; i < size - index; i++) {
temp = temp.next;
}
return temp;
}

反转单链表(reverse a singly linked list)

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
/**
* 反转单链表
* 1、遍历原链表
* 2、将每个结点的下一个结点存储到next
* 3、将处理中的结点的下一个结点,改为反转结点头后第一个结点
* 4、将处理中的结点连接到反转结点头之后
* 5、移动到next结点、继续处理上述步骤
*
* @param head
*/
public static void reverseList(HeroNode head) {
if (head.next == null || head.next.next == null) {
return;
}

HeroNode cur = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0, "", "");
//遍历原链表,每遍历一个结点就将其取出、放在新链表reverseHead的最前端
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
head.next = reverseHead.next;
}

倒序打印单链表 (print a singly linked list from last one to the first one)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 倒序打印单向链表
* 使用栈(stack)实现
*
* @param head
*/
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return;
}
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (stack.size() > 0){
System.out.println(stack.pop());
}
}

Singly Linked List
http://hihiko.zxy/2023/01/09/Singly-Linked-List/
Author
Posted on
January 9, 2023
Licensed under