java实现单向链表_java算法:定义单项链表

java原声实现单向链表

什么是单向链表

如下图就是一个单向链表的实例，头指针不存放数据，只有指向下一个数据的地址，下图中，头指针指向下一个地址为150的数据，数据为a1,a1的下一个节点地址为110，数据为a2，a2的下一个节点地址为180，数据为a3，a3的下一个节点地址130…单向链表每个节点都有两个部分，一部分是自己的数据，一部分是指向下一个节点的地址。

下面这张图更加直观的看出链表的结构。

单链表节点的定义

首先我们定义一个单向链表的节点类，假如这个节点类是个HeroNode，这个类我们就放置4个属性，分别为no(英雄编号)、name(英雄名称)、nickname(英雄小名)、next(下一个节点的引用)，我们定义一个构造函数，为了后面输出好看，我们重写toString方法。

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

    @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

我们现在就需要定义一个单链表SingleLinkedList类，用来管理节点，构成单向链表

我们定义这个单链表需要初始化头节点，同时需要创建添加节点、更新节点、删除节点以及输出链表。
初始化头节点，头节点的next属性为null；

    //先初始化一个头节点，头节点不能动，不存放具体数据
    HeroNode head = new HeroNode(0, "", "");
1
2

添加节点：
添加节点，我们需要传递过来一个节点，然后从头节点开始先进行判断，该节点是不是最后一个节点(最后一个节点的next为null)，不是最后一个的时候，节点往后移，如果是最后一个节点的时候，只需要把最后一个节点的next指向传进来的节点即可，需要定义一个节点承接遍历的每个节点。

    //添加英雄
    public void addHero(HeroNode hero) {
        //先进行判断，该节点是不是最后一个节点(最后一个节点的next为null)
        //不是最后一个的时候，节点往后移
        //定义一个中间变量
        HeroNode heroNode = head;
        while (true) {
            if (heroNode.next == null) {
                heroNode.next = hero;
                break;
            }
            heroNode = heroNode.next;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

更新节点：
更新节点也需要定义一个节点承接遍历的每个节点，还需要定义一个临时变量，用于标记是否找到了需要更新的节点，定义为false，当找到需要更新的节点，就设置成true，然后结束遍历。在遍历链表之前需要判断该链表是否为空链表，因为空链表和遍历完链表都是，next为null,所以根据最后一个节点为的后一个节点是否为null，来判断。更新节点是根据no来遍历节点，直到找到一个no和需要更新的no相同的节点，然后跳出循环，此时临时承接每个节点的节点就是需要更新的节点，然后对其更新。如果空链表或者遍历完都没有找到的时候，临时变量依旧为false，只有找到了才为true，所以，最后根据这个临时变量flag来进行是更新还是输出没有找到节点。

    //更新链表节点的数据
    public void updateHero(HeroNode heroNode) {
        //定义一个临时变量和一个标记
        HeroNode temp = head;
        boolean flag = false;//标记是否找到该节点
        while (true) {
            if (temp.next == null) {
                break;//空链表或者已经遍历完了
            }
            if (temp.next.no == heroNode.no) {//找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 判断是否找到要修改的节点
        if (flag) {
            temp.next.name = heroNode.name;
            temp.next.nickname = heroNode.nickname;
        } else {//没有找到
            System.out.printf("没有找到编号 %d 的节点，不能修改\n", heroNode.no);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

删除节点：
删除节点和上面更新节点差不多，都是根据no找到对应的节点，然后进行删除，但是这个不一样的是，需要找到的不是更新的节点，而是待更新节点的前一个结点，以为是单向链表，你找到待更新的节点之后，就不知道上一个节点了，所以只能找到待删除节点的前一个结点。删除的方式其实就是让待删除的节点的前一个结点的next直接指向需要删除的节点后面的节点即可。

    //删除单链表节点
    public void deleteHero(int no) {
        //定义一个临时变量和一个标记
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//到链表尾部
                break;
            }
            //找到待删除的节点的前一个节点
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //删除
        if (flag){
            temp.next = temp.next.next;
        }else{
            System.out.println("找不到该节点");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

输出链表：
输出链表就是和上面一样，遍历链表，遍历一个输出一个，知道节点的下一个节点为null。

    //输出链表
    public void showHero() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode node = head.next;
        //输出链表的数据
        while (true) {
            System.out.println(node);
            //判断下一个节点是否为空
            if (node.next == null) {
                break;
            }
            node = node.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上面已经实现了单向链表的基本操作，我们测试一下

    public static void main(String[] args) {
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //创建英雄
        HeroNode hero1 = new HeroNode(1, "疾风剑豪", "亚索");
        HeroNode hero2 = new HeroNode(2, "无双剑姬", "菲奥娜");
        HeroNode hero3 = new HeroNode(3, "无极剑圣", "易");
        HeroNode hero4 = new HeroNode(4, "暗裔剑魔", "亚托克斯");
        singleLinkedList.addHero(hero1);
        singleLinkedList.addHero(hero4);
        singleLinkedList.addHero(hero2);
        singleLinkedList.addHero(hero3);
/*        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);*/
        singleLinkedList.showHero();
        System.out.println("--------------------------------------------------");
        singleLinkedList.updateHero(new HeroNode(4, "傲之追猎者", "狮子狗"));
        singleLinkedList.showHero();
        System.out.println("--------------------------------------------------");
        singleLinkedList.deleteHero(1);
        singleLinkedList.showHero();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

结果：

HeroNode{no=1, name='疾风剑豪', nickname='亚索'}
HeroNode{no=4, name='暗裔剑魔', nickname='亚托克斯'}
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
--------------------------------------------------
HeroNode{no=1, name='疾风剑豪', nickname='亚索'}
HeroNode{no=4, name='傲之追猎者', nickname='狮子狗'}
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
--------------------------------------------------
HeroNode{no=4, name='傲之追猎者', nickname='狮子狗'}
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
1
2
3
4
5
6
7
8
9
10
11
12
13

其实大家可以发现，这个顺序是按照我们放入的顺序来的，如何能让他按照每个节点的no由小到大来插呢？
如下，判空、定义辅助变量和标记就不用多说了，主要说说怎么找到位置，我们只需要用传入的节点的no跟每一个节点进行比较，直到遇到一个节点A的后一个节点B的no比传入的节点no大，这时候就是找到位置了，我们只需要把数据节点插入到A后面B前面，具体插入方法就是让A的next B赋给传进来的节点的next，然后让A的next指向传进来的节点即可。
具体实现如下：

    //第二种添加英雄的方法：根据排名将英雄插入到指定位置（如果这个排名已经存在，则添加失败，并给出提示）
    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助变量来帮助我们找到添加的位置
        //因为单链表，所以我们找到的temp 是位于添加位置的前一个结点，否则无法插入
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//temp已经在最后的位置了
                break;
            }
            if (temp.next.no > heroNode.no) {//找到位置
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;//编号存在
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag) {//编号存在
            System.out.printf("准备插入的英雄编号%d已经存在,不能加入\n", heroNode.no);
        } else {
            //插入数据到链表
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
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

然后我们使用第二种添加节点测试，得到结果如下：

HeroNode{no=1, name='疾风剑豪', nickname='亚索'}
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
HeroNode{no=4, name='暗裔剑魔', nickname='亚托克斯'}
--------------------------------------------------
HeroNode{no=1, name='疾风剑豪', nickname='亚索'}
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
HeroNode{no=4, name='傲之追猎者', nickname='狮子狗'}
--------------------------------------------------
HeroNode{no=2, name='无双剑姬', nickname='菲奥娜'}
HeroNode{no=3, name='无极剑圣', nickname='易'}
HeroNode{no=4, name='傲之追猎者', nickname='狮子狗'}
1
2
3
4
5
6
7
8
9
10
11
12
13

我们发现此时插入链表的no都是有序的了。

具体程序源码如下：

//单向链表
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //创建英雄
        HeroNode hero1 = new HeroNode(1, "疾风剑豪", "亚索");
        HeroNode hero2 = new HeroNode(2, "无双剑姬", "菲奥娜");
        HeroNode hero3 = new HeroNode(3, "无极剑圣", "易");
        HeroNode hero4 = new HeroNode(4, "暗裔剑魔", "亚托克斯");
/*        singleLinkedList.addHero(hero1);
        singleLinkedList.addHero(hero4);
        singleLinkedList.addHero(hero2);
        singleLinkedList.addHero(hero3);*/
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.showHero();
        System.out.println("--------------------------------------------------");
        singleLinkedList.updateHero(new HeroNode(4, "傲之追猎者", "狮子狗"));
        singleLinkedList.showHero();
        System.out.println("--------------------------------------------------");
        singleLinkedList.deleteHero(1);
        singleLinkedList.showHero();
    }
}

//定义SingleLinkedList管理我们的英雄
class SingleLinkedList {
    //先初始化一个头节点，头节点不能动，不存放具体数据
    HeroNode head = new HeroNode(0, "", "");

    //添加英雄
    public void addHero(HeroNode hero) {
        //先进行判断，该节点是不是最后一个节点(最后一个节点的next为null)
        //不是最后一个的时候，节点往后移
        //定义一个中间变量
        HeroNode heroNode = head;
        while (true) {
            if (heroNode.next == null) {
                heroNode.next = hero;
                break;
            }
            heroNode = heroNode.next;
        }

    }

    //第二种添加英雄的方法：根据排名将英雄插入到指定位置（如果这个排名已经存在，则添加失败，并给出提示）
    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助变量来帮助我们找到添加的位置
        //因为单链表，所以我们找到的temp 是位于添加位置的前一个结点，否则无法插入
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//temp已经在最后的位置了
                break;
            }
            if (temp.next.no > heroNode.no) {//找到位置
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;//编号存在
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag) {//编号存在
            System.out.printf("准备插入的英雄编号%d已经存在,不能加入\n", heroNode.no);
        } else {
            //插入数据到链表
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //更新链表节点的数据
    public void updateHero(HeroNode heroNode) {
        //定义一个临时变量和一个标记
        HeroNode temp = head;
        boolean flag = false;//标记是否找到该节点
        while (true) {
            if (temp.next == null) {
                break;//空链表或者已经遍历完了
            }
            if (temp.next.no == heroNode.no) {//找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 判断是否找到要修改的节点
        if (flag) {
            temp.next.name = heroNode.name;
            temp.next.nickname = heroNode.nickname;
        } else {//没有找到
            System.out.printf("没有找到编号 %d 的节点，不能修改\n", heroNode.no);
        }
    }

    //删除单链表节点
    public void deleteHero(int no) {
        //定义一个临时变量和一个标记
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//到链表尾部
                break;
            }
            //找到待删除的节点的前一个节点
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //删除
        if (flag){
            temp.next = temp.next.next;
        }else{
            System.out.println("找不到该节点");
        }
    }

    //输出链表
    public void showHero() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode node = head.next;
        //输出链表的数据
        while (true) {
            System.out.println(node);
            //判断下一个节点是否为空
            if (node.next == null) {
                break;
            }
            node = node.next;
        }
    }
}

//定义HeroNode，每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167