算法_链表篇_链表前驱节点与后继节点

单链表和双向链表

本文主要通过单链表的增删改查的学习与实践，从而理解链表的数据结构，进而实践双向链表的算法例题等。已对此数据结构逐渐有了深层次的认识。

---

链表简介

单链表（单向链表）：

由两部分组成 数据域（Data）和结点域(Node)。这样原理的实现是通过Node结点区的头指针head实现的，每个结点都有一个指针，每个节点指针的指向都是指向自身结点的下一个结点，最后一个结点的head指向为null,这样一来就连成了链，对单链表的操作只能从一端开始，如果需要查找链表中的某一个结点，则需要从头开始进行遍历。


双链表（双向链表）：

对于双向链表来说，它的每个节点要指向“直接前驱”和“直接后继”，所以节点类需要含有两个指针域。指向直接前驱的指针使用pre表示，指向后继的指针使用next表示。双向链表是在单向链表基础上的一个改进，每个节点指向其直接前驱和直接后继节点。因此，从双向链表的任意位置开始，都能访问所有的节点。

双向链表从节点的结构上可以看出，双向链表的所需的存储空间大于单向链表。同时，对于插入和删除等操作来说，双向链表的节点操作更加复杂，涉及到节点的前后两个节点。

---

单向链表的增、删、改、查节点的实现

实体类 HeroNode.java

/**
 * @description:定义一个HeroNode，HeroNode对象就是一个节点
 */
public class HeroNode {
   
    /** 编号 **/
    int no;
    /** 姓名 **/
    String name;
    /** 昵称 **/
    String nickName;
    /** 指向下一个英雄节点域 **/
    HeroNode next;
    
 	public HeroNode(){
   }
 	
    public HeroNode(int no, String name, String nickName) {
   
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    /**
     * @return java.lang.String
     * @Description //TODO  重写
     * @Param []
     **/
    @Override
    public String toString() {
   
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
//                ", next=" + 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

逻辑实现类：SingleLinkedList.java

/**
 * @description: 管理英雄
 */
public class SingleLinkedList {
   
    /**
     * * 添加（创建）
     * * 1. 先创建一个head头节点，作用就是表示单链表的头。
     * * 2. 后面我们没添加一个节点，就直接加入到链表的最后。
     * * 3. 遍历。
     * **/

    /**
     * 先初始化一个头节点
     * 头节点不存放具体的数据
     */
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * @return
     * @Description //TODO  不按编号顺序添加节点
     * @Param HeroNode
     **/
    public void add(HeroNode heroNode) {
   
//        先让辅助变量temp指向head
        HeroNode temp = head;
//        遍历链表，找到最后一位
        while (true) {
   
//            判断是否为最后一位
            if (temp.next == null) {
   
                break;
            }
//            若不是最后一位，则将辅助变量后移
            temp = temp.next;
        }
//        将新的英雄对象赋值给链表的最后一位
        temp.next = heroNode;
    }

    //    按照编号插入新的英雄节点
    public void addByOrder(HeroNode heroNode) {
   
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
   
            if (temp.next == null) {
   
                break;
            }
            if (temp.next.no > heroNode.no) {
   
//                位置找到，就在temp的后面插入即可
                break;
            } else if (temp.next.no == heroNode.no) {
   
                //编号已存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
   
            System.out.println("待插入的英雄编号" + heroNode.no + "已存在！不能添加此编号的英雄~");
        } else {
   
//            将此编号的英雄插入链表
            heroNode.next = temp.next;
            temp.next = heroNode;
            System.out.println("插入成功！");
        }
    }

    /**
     * @return void
     * @Description //TODO  根据编号修改英雄信息
     * @Param [newHero]
     **/
    public void updateHero(HeroNode newHero) {
   
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
   
            if (temp == null) {
   
                break;
            }
            if (temp.no == newHero
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