THIS IS B3c0me

记录生活中的点点滴滴

0%

链表的Java实现

一 、链表介绍

链表(Linked List),是有序列表

  • 链表是以结点的方式来存储的
  • 每个结点包含data域和next域
  • 链表的各个节点不一定是连续存放的
  • 链表分带头结点的链表和没有头结点的链表

1.1 单链表

1.1.1单链表的应用实例

水浒英雄排行榜

1.1.2单链表实现在链表尾部添加节点
  • 按照顺序添加,每个新节点添加到链表的尾部
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
//定义一个HeroNode ,每个HeroNode对象就是一个节点

class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;

//构造器
public HeroNode(int hNo,String hName,String hNickName) {
this.no = hNo;
this.name = hName;
this.nickname = hNickName;
}
//重写toString方法
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}

//定义一个SingleLinkedList管理英雄
class SingleLinkedList1{
//初始化一个头结点
private static final HeroNode head = new HeroNode(0,"","");

//添加节点到单向链表
//思路:当不考虑编号顺序时,找到当前链表的最后一个节点,将最后一个节点的next指向新的节点
public void add(HeroNode heroNode) {
//遍历链表找到最后一个节点
//退出循环时temp指向最后一个节点
HeroNode temp = head;
while(true) {
if(temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}
//显示链表
public void showList() {
//先判断链表是否为空
if(head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while(true) {
if(temp == null) {
break;
}
//输出节点信息
System.out.println(temp.toString());
temp = temp.next;
}
}
}
1.1.3 单链表实现在指定位置插入结点
  • 在SingleLnkedLIst1类中添加新的方法:
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
//第二种添加方式:在指定位置添加
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while(true) {
if(temp.next == null) {
break;
}
if(temp.next.no>heroNode.no) {
break;
}
if(temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if(flag) {
System.out.println("该排行已经有英雄!不能添加");
return;
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
1.1.4 单链表实现节点的修改
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
//根据NO编号来修改信息
public void update(HeroNode heroNode,String name,String nickname) {
if(head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while(true) {
if(temp == null) {
break;
}
if(temp.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if(flag) {
temp.name = name;
temp.nickname = nickname;
} else {
System.out.println("没有找到该节点" );
}
}
1.1.5 单链表实现节点的删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void deleteNode(HeroNode heroNode) {
HeroNode temp = head;
if(temp == null) {
System.out.println("链表空");
return;
}
boolean flag = false;
while(true) {
if(temp.next.no == heroNode.no) {
flag = true;
break;
}
if(temp.next == null) {
break;
}
temp = temp.next;
}
if(flag) {
temp.next = temp.next.next;
return;
}
}

1.2 双向链表

欢迎关注我的其它发布渠道