（Java）以水浒英雄排名为例创建单链表_使用java语言实现链表结构,存储以下表信息:赵云,许诸,关羽,周瑜,张飞

单链表的介绍及创建

定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

今天只讲单链表的创建，之后文章会说单链表单个节点的插入，删除等操作。

以水浒英雄链表为例：

每一个英雄都有自己的姓名，绰号，各个英雄之间还有排名，那么我们可以以排名为准来创立一个链表，来进行对各个人物的储存。

代码如下：

首先是HeroNode的代码，用于创建节点。

//定义HeroNode,每个HeroNode对象就是一个节点
public class HeroNode{
	private int no;
	private String name;
	private String nickname;
	HeroNode next;  //指向下一个节点
	
	//构造器
	public HeroNode(int no, String name, String nickname) {
		super();
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	//为了显示方法，我们重新toString
	
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname="
				+ nickname + "]";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

再写SingleLinkedList类代码：

package 单链表;


//定义SingleLinkedList，管理我们的英雄人物（创建链表）
public class SingleLinkedList {
	//先初始化一个头节点，头节点不要动，不存放具体的数据
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路，当不考虑编号顺序时
	//1，找到当前链表的最后节点
	//2，将最后这个节点的next指向新的节点
	public  void add(HeroNode heroNode){
		//因为head节点不能动，因此我们需要一个辅助变量temp
		HeroNode temp = head;
		
		//遍历链表，走到最后
		while(true){
			
			//找到链表的最后
			if(temp.next==null){
				break;
			}
			//如果没有找到最后，就将temp后移
			temp = temp.next;
		}
		//当推出while循环时，temp已经指向了链表的最后
		
		//将最后这个节点的next指向新的节点
		temp.next = heroNode;
	}
	
	//显示链表【遍历】（为了验证链表已完成）
	public void list(){
		
		//判断链表是否为空
		if(head.next==null){
			System.out.println("链表为空");
			return;
		}
		
		//因为头节点不能动，所以需要一个辅助变量来遍历
		HeroNode temp = head.next;
		
		while(true){
			//判断是否到链表最后
			if(temp == null){
				break;
			}
			
			//输出节点信息
			System.out.println(temp);
			//将temp后移，指向下一个节点
			temp = temp.next;
		}
	}
	
}

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

最后是main类的代码，用于调用数据。

package 单链表;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		//测试一下
		
		//先创建节点
        Scanner input = new Scanner(System.in);
		
		HeroNode h1 = new HeroNode(input.nextInt(),input.next(),input.next());
		HeroNode h2 = new HeroNode(input.nextInt(),input.next(),input.next());
		HeroNode h3 = new HeroNode(input.nextInt(),input.next(),input.next());
		HeroNode h4 = new HeroNode(input.nextInt(),input.next(),input.next());
        
        //创建链表
        SingleLinkedList s1 = new SingleLinkedList();
        
        //添加数据到链表中
        s1.add(h1);
        s1.add(h2);
        s1.add(h3);
        s1.add(h4);
        
        //显示链表
        s1.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

显示结果如下：

1 宋江 及时雨
2 卢俊义 玉麒麟
3 吴用 智多星
4 林冲 豹子头
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]