数据结构之单链表的插入

单链表的完整的代码在这篇文章下面，链接：
https://blog.csdn.net/six_teen/article/details/113253545

什么是链表？

如上图，链表和生活中的链条很相似，链表在逻辑结构上是以链条的形式连接而成的，但物理结构上链表的节点不是连续性存储的。

如图，每一个节点都分为两块区域，data区和next区，data区存储数据，next区存储下一个节点的地址。因为节点的这种特性，所以链表可以充分利用内存中零散的空间。

链表一般分为带头节点的链表和不带头节点的链表（头结点用head表示）后续演示都使用带头节点的链表（一般头结点data区为空，next区指向第一个节点）：

先定义一个节点类：
no表示节点序号，name,nickename是节点携带的一些数据，next就是存放下一个节点的地址的区域

class HeroNode{
    private int no;
    private String name;
    private String nickname;
    private HeroNode next;
	//一个有参构造
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override//重写该类的toString，不带next属性
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
    //属性的 get set 方法省略
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

再定义一个单链表类：

class SingleLinkedList{
	//单链表的头节点初始化next域指向null
    private HeroNode head = new HeroNode(0,"","");

    public void setHead(HeroNode head) {
        this.head = head;
    }

    public HeroNode getHead() {
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

链表的插入方法有以下几种：
1.头插法(对单链表反转有帮助)
2.尾插法
3.按序号插入(对两个有序单链表合并为一个有序单链表有帮助)

此处用图解的方法说明头插法，其他方法是类似的就不一一画图了（ps:实在是画图太折磨人了）

尾插法的关键在于，每次插入时都需要先遍历链表，找到链表最后一个节点。
用while循环遍历，也需要一个temp节点初始化和head节点或者是head.next(即第一个节点)地址相同，temp=head或者temp=head.next
while退出循环的条件是temp.next==null，具体代码如下：
该方法代码在SingleLinkedList类内部，所以可以直接引用到链表的head。

因为在java中类属性的改变需要get set方法，所以和伪代码的.next有所不同

public void add(HeroNode node){
	HeroNode temp = head;
	while(true){
		if(temp.getNext()==null){
			break;
		}
		temp = temp.getNext();
	}
	//循环结束之后，此时的temp就和链表最后一个节点的地址相同
	//操作temp就相当于操作最后一个节点
	//执行尾插法
	node.setNext(temp.getNext());//此时的temp.getNext()==null
	temp.setNext(node);
	//如果链表为空，那么temp还是指向head，照样可以插入节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

按序号插入也是相对较难的插入，先上代码，后面再解释：
该方法还是在单链表类的内部定义的

public void addByNo(HeroNode node){
        HeroNode temp = head;
        Boolean flag = false;//标识编号是否已经存在
        while (true){//while循环结束，找到插入点
            if (temp.getNext()==null){
                break;
            }else if (temp.getNext().getNo() > node.getNo()){
                break;
            }else if (temp.getNext().getNo() == node.getNo()){
                flag = true;
            }
            temp = temp.getNext();
        }
        if (flag){
            System.out.printf("准备插入的节点编号%d已经存在\n",node.getNo());
        }else {
            node.setNext(temp.getNext());
            temp.setNext(node);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

按序号插入的核心在于，要判断当前指针temp所指向的节点的下一个节点temp.next的序号是否大于要插入节点node的序号，如果大于，就把node节点插入到temp和temp.next的中间。如果不大于，temp指针就往链表后面移动一个位置，再进行下一个节点序号与要插入节点序号的判断。下面给个图解释一下：

以上就是单链表的三种插入方法，如有解释不当，还望大佬见谅。