手把手教你写出一个带头单链表_java

第二章：用java语言写带头的单链表

前言：

抛出问题：

解决办法：

目的：

实现：

15. 代码总结

前言：

抛出问题：

我们之前写单链表的时候，一直要考虑头节点的注意事项，贼烦人！无论是插入还是删除，都得考虑这个头节点，就是因为头结点没有前驱。

解决办法：

那么现在就引入一个虚拟头节点的概念： dummyHead（相当于现实中的火车头），只作为链表的头结点使用，不存储有效数值。

目的：

这样做以后，链表中的其他有效结点全都可以一视同仁，都具有前驱节点了。

实现：

1. 单链表的每个节点-车厢类

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
}

2.成员变量要用 private 封装，因为以后调用的类都是单链表 Lin_ked_List_With_Head，因为它是火车的头部，所以方法的定义肯定是在这里面写的。

/**
 * 带头(虚拟头节点)单链表
 */
public class Lin_ked_List_With_Head {
    //有效节点的个数
    private int size;
    //创建一个虚拟头节点
    // 实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();
}

3. 前面基础的写好了，现在可以先写个头插 add

画图分析：头插分为两种情况

3.1 已经存在节点后进行头插，这样写代码：

3.2 之前不存在节点，第一次头插

图：

发现：

示例代码：

    //头插add
    public void addFirst(int val){
        Node newNode = new Node();//创建出一个新节点
        newNode.val = val;//赋值

        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;//有效元素 + 1
    }

注意：记得 size++；

要测试下我们写的程序对不对，我们先写个补充程序toString函数，打印我们的链表

代码示例：

//模拟完善一下toString函数，打印我们写的链表
    public String toString(){
        String rep = "";
        Node prve = dummyHead.next;//第一个节点位置

        while(prve != null){

            rep += prve.val;
            rep += " -> ";
            prve = prve.next;
        }
        rep += "NULL";//表示走到头了
        return rep;
    }

注释：要始终保持虚拟头节点的位置，是不能动的。

不能直接用dummyHead来打印走下一步，不然以后还怎么找头节点？创建一个变量来代替来完成。 Node prve = dummyHead.next; 就是这步。

到 Test里面测试一下：


public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addFirst(1);
        llwh.addFirst(2);
        llwh.addFirst(3);
        llwh.addFirst(4);
        System.out.println(llwh);
    }
}

运行结果：正确，没问题。

注释：新手写代码，最好完成一个功能模块就测试一下，方便找出问题。

4. 其实可以对刚刚的添加代码进行简化，就是运用我们之前学的 ‘构造方法’，对Node类进行设置

Node类修改后：多个三个构造方法

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
    //构造方法
    //1 当传入一个val值的时候，自动给它赋值
    public Node(int val) {
        this.val = val;
    }
    //2 当传入val值和下一个地址的时候，自动给它赋值
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
    //3 再弄的无参的，什么都不做
    public Node(){
        
    }
}

5. 有个Node类里面的构造方法的帮忙，就多出来两种简写办法

新的头插，示例代码：从下往上看！

 //头插add
    public void addFirst(int val){

        //第三种更加简便的，运用的是 之前学的 动态初始化的简写，语法糖
        dummyHead.next = new Node(val, dummyHead.next);//创建出一个新节点
        size++;

        //第二种，简化后的
        /*
        Node newNode = new Node(val, dummyHead.next);//创建出一个新节点
        dummyHead.next = newNode;
        size++;
         */

        //第一种写法
        /*
        Node newNode = new Node();//创建出一个新节点
        newNode.val = val;//赋值

        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;//有效元素 + 1

         */
    }

注释：我们这样简写不是为了简便而简便，而是运用我们之前所学的知识，运用到写代码里面，可以提升代码的水平。

6. 现在开始写一个能在任意索引位置插入的add

6.1 画图先理解，最重要的是找在 ‘前驱’

前驱：就是我们要删除节点的前面一个节点，因为是单链表，只能从前往后找。

前驱的概念非常重要！

发现：要找到前驱，只需要循环 index 次就可以了

示例代码：

    /**
     * 在索引为 index 的位置上 插入 一个节点
     * @return
     */
    public void add(int index, int val){
        //对索引判断
        if(index < 0 || index > size){
            System.out.println("插入的索引错误！");
            return;
        }
        Node prve = dummyHead;//始终充当前驱的身份
        //想要让prve成为要插入位置的前驱，就需要知道要走几步
        //作图得知，插入index位置，需要做 index步
        for (int i = 0; i < index; i++) {
            prve = prve.next;
        }//循环后，prve就是前驱的位置了
        
        //方法1
        //让新节点指向 前驱的 后面的后面一个
        Node node = new Node(val);//要插入的对象
        node.next = prve.next;
        prve.next = node;//前驱指向新节点
        size++;
         
        //方法2 简便写法，跟之前都一样
        //让新节点指向 前驱的 后面的后面一个
//        prve.next = new Node(val, prve.next);//要插入的对象
//        size++;
    }

Test测试代码：

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addFirst(1);
        llwh.addFirst(2);
        llwh.addFirst(3);
        llwh.addFirst(4);
        System.out.println("正常顺序:" + llwh);

        llwh.add(4,9);
        System.out.println("尾插：" + llwh);

        llwh.add(0,8);
        System.out.println("头插：" + llwh);

        llwh.add(3,7);
        System.out.println("中间插：" + llwh);
    }
}

运行结果：没问题，结果正常。

7. 那么现在写个尾插就更是简简单单，直接调用就行

示例代码：

    //尾插
    public void addLase(int val){
        //直接调用 我们上一个写的 add插入就行
        add(size , val);
    }

8. 现在写删除index索引处的节点，要删除一个节点，跟插入思修差不多，都是一个找前驱的过程，因为我们没有头节点的顾虑了，可以直接开始写。

8.1 画图理解

8.2 封装一下判断索引合法性代码

我们写的时候可以发现，插入、删除等，都需要判断给我们的所以是否是正常，合法，为了降低程序的量，直接自定义一个方法来判断： rangeCheck（int index）

教大家一个快捷键 Alt + Ent（回车）

使用方法：先在remove删除方法里面这么写

    /**
     * 删除 索引 位置的节点,并返回删除前的节点的val值
     * @return
     */
    public int remove(int index){
        if( rangeCheck(index) ){
            //如果索引合法走这里
        }
        //索引不合法走这里
        System.out.println("你输入的删除索引不合法！");
        return -1;//不合法我们就返回一个 -1
    }

然后光标放在 rangeCheck 里面按下 Alt + 回车，选择

就会自动生成

判断的方法里面这么写：

    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

8.3 回到 remove删除方法里面，现在是要求写一个删除 index位置处的节点

示例代码：

    /**
     * 删除 索引 位置的节点,并返回删除前的节点的val值
     * @return
     */
    public int remove(int index){
        if( rangeCheck(index) ){
            //如果索引合法走这里
            Node prve = dummyHead;

            for (int i = 0; i < index; i++) {
                prve = prve.next;
            }//此时的 prve就是 处于 待删除节点 前驱的位置
            Node node = prve.next;
            prve.next = node.next;
            size--;
            return node.val;
        }
        //索引不合法走这里
        System.out.println("你输入的删除索引不合法！");
        return -1;//不合法我们就返回一个 -1
    }

Test 测试案例

package 链表.带头单链表;

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(1);
        llwh.addLase(2);
        llwh.addLase(3);
        llwh.addLase(4);
        llwh.addLase(5);
        llwh.addLase(6);
        System.out.println("正常顺序:" + llwh);

        System.out.println(  llwh.remove(5) );
        System.out.println("尾删：" + llwh);

        System.out.println(  llwh.remove(0) );
        System.out.println("头删：" + llwh);

        System.out.println(  llwh.remove(1) );
        System.out.println("中间位置删：" + llwh);

    }
}

运行结果：都返回的删除的值，删除正常

9. 写一个删除所以元素值为 val的方法：采用while循环，走到null就结束删除

    /**
     * 删除链表中 所有值为 val 的元素
     */
    public void removeAllValue(int val){
        Node prve = dummyHead;//前驱
        Node node = prve.next;//用来判断是否是待删除节点
        while(node != null){

            if(node.val == val){
                node = node.next;//跳过
                prve.next = node;
                size--;
            }else{
                //当遇到的不是val值时，prve才会 放心的向后走到不是删除的节点上面
                prve = node;
                node = node.next;
            }


        }
    }

Test测试

package 链表.带头单链表;

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(2);
        llwh.addLase(2);
        llwh.addLase(2);
        llwh.addLase(2);
        llwh.addLase(2);
        llwh.addLase(2);
        System.out.println("正常顺序:" + llwh);

        llwh.removeAllValue(2);
        System.out.println(llwh);

    }
}

10. 写一个查找链表中第一个为 val 的索引值为多少,找不到则返回 -1

思路：肯定是从开始循环判断，到尾null就结束。

示例代码:

    /**
     *查找第一个为 val 的 索引值为多少,找不到则返回 -1
     */
    public int getByValue(int val){
        Node prve = dummyHead.next;
        for (int i = 0; prve != null ; i++) {
            if(prve.val == val){
                return i;
            }
            prve = prve.next;
        }
        
        //如果都没找到，则不存在 返回 -1
        return -1;
    }

Test测试

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(1);
        llwh.addLase(2);
        llwh.addLase(2);
        llwh.addLase(4);

        System.out.println("正常顺序:" + llwh);

        System.out.println(llwh.getByValue(1) );
        System.out.println(llwh.getByValue(2) );
        System.out.println(llwh.getByValue(3) );
        System.out.println(llwh.getByValue(4) );

        //System.out.println(llwh);

    }
}

运行结果：因为不存在 3，所以返回 -1.

11. 根据这个查找，我们可以跟轻松的写出：删除链表中第一个为val的节点

调用我们之前写的方法即可轻松实现

    /**
     * 删除链表中第一个值为 val的节点
     */
    public void remoValueOnce(int val){

        int tmp = getByValue(val);
        if( tmp != -1 ){

            remove(tmp);
        }
    }

Test测试

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(2);
        llwh.addLase(1);
        llwh.addLase(2);
        llwh.addLase(4);

        System.out.println("正常顺序:" + llwh);

       llwh.remoValueOnce(2);

        System.out.println(llwh);

    }
}

运行结果：

12. 查找链表中是否包含 val 值的节点，存在返回 true，否则返回 false

    /**
     * 查询链表中 是否包含 val 值
     * @return
     */
    public boolean contains(int val){
        int index = getByValue(val);
        return index != -1;
    }

都是调用之前写的方法。

13. 查找索引为 index 位置上的 val节点值

13.1 先画图理解

13.2 代码实现

    /**
     * 查询索引为 index 的元素 val 为多少,
     * @return
     */
    public int get(int index){
        // 1.判断index的合法性
        if( rangeCheck(index) ){
           Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }
            return x.val;
        }
        //不符合索引要求走到这里
        System.out.println("查询的索引值不合理！");
        return -1;
    }

Test测试

public class Linked_list_Test_4_22 {
    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(6);
        llwh.addLase(9);
        llwh.addLase(7);
        llwh.addLase(5);

        System.out.println("正常顺序:" + llwh);

        System.out.println(llwh.get(3));
        System.out.println(llwh.get(0));
        System.out.println(llwh.get(5));


    }
}

14. 最后一个，弄一个修改。

* 修改索引为 index 位置的节点值，改为 newVal
* 返回修改前的值

原理都跟之前的查找一样，走 index + 1步

    /**
     * 修改索引为 index 位置的节点值，改为 newVal
     * 返回修改前的值
     */
    public int set(int index, int newVal){

        if(rangeCheck(index)){

            Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }//循环后x指向的就是索引位置
            int rep = x.val;//保存待返回的值
            x.val = newVal;
            return rep;
        }
        //到这里说明索引不合理
        System.out.println("输入修改的索引不合理");
        return -1;
    }

Test测试

    public static void main(String[] args) {

        Lin_ked_List_With_Head llwh = new Lin_ked_List_With_Head();

        llwh.addLase(6);
        llwh.addLase(9);
        llwh.addLase(7);
        llwh.addLase(5);

        System.out.println("正常顺序:" + llwh);

        System.out.println(llwh.set(3, 8));
        System.out.println(llwh.set(0, 8));
        System.out.println(llwh.set(5, 8));

        System.out.println(llwh);
    }
}

15. 代码总结

这样下来，带头单链表的增删改插都完成了，一般来说，删除是最难的，应该放在最后写。

完整的单链表代码：

package 链表.带头单链表;

/**
 * 带头(虚拟头节点)单链表
 */
public class Lin_ked_List_With_Head {
    //有效节点的个数
    private int size;
    //创建一个虚拟头节点
    // 实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();

    //头插add
    public void addFirst(int val){

        //第三种更加简便的，运用的是 之前学的 动态初始化的简写，语法糖
        dummyHead.next = new Node(val, dummyHead.next);//创建出一个新节点
        size++;

        //第二种，简化后的
        /*
        Node newNode = new Node(val, dummyHead.next);//创建出一个新节点
        dummyHead.next = newNode;
        size++;
         */

        //第一种写法
        /*
        Node newNode = new Node();//创建出一个新节点
        newNode.val = val;//赋值

        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;//有效元素 + 1

         */
    }

    /**
     * 在索引为 index 的位置上 插入 一个节点
     * @return
     */
    public void add(int index, int val){
        //对索引判断
        if(index < 0 || index > size){
            System.out.println("插入的索引错误！");
            return;
        }
        Node prve = dummyHead;//始终充当前驱的身份
        //想要让prve成为要插入位置的前驱，就需要知道要走几步
        //作图得知，插入index位置，需要做 index步
        for (int i = 0; i < index; i++) {
            prve = prve.next;
        }//循环后，prve就是前驱的位置了

        //方法1
        //让新节点指向 前驱的 后面的后面一个
        Node node = new Node(val);//要插入的对象
        node.next = prve.next;
        prve.next = node;//前驱指向新节点
        size++;

        //方法2 简便写法，跟之前都一样
        //让新节点指向 前驱的 后面的后面一个
//        prve.next = new Node(val, prve.next);//要插入的对象
//        size++;
    }

    //尾插
    public void addLase(int val){
        //直接调用 我们上一个写的 add插入就行
        add(size , val);
    }


    /**
     * 删除 索引 位置的节点,并返回删除前的节点的val值
     * @return
     */
    public int remove(int index){
        if( rangeCheck(index) ){
            //如果索引合法走这里
            Node prve = dummyHead;

            for (int i = 0; i < index; i++) {
                prve = prve.next;
            }//此时的 prve就是 处于 待删除节点 前驱的位置
            Node node = prve.next;
            prve.next = node.next;
            size--;
            return node.val;
        }
        //索引不合法走这里
        System.out.println("你输入的删除索引不合法！");
        return -1;//不合法我们就返回一个 -1
    }

    /**
     * 删除链表中 所有值为 val 的元素
     */
    public void removeAllValue(int val){
        Node prve = dummyHead;//前驱
        Node node = prve.next;//用来判断是否是待删除节点
        while(node != null){

            if(node.val == val){
                node = node.next;//跳过
                prve.next = node;
                size--;
            }else{
                //当遇到的不是val值时，prve才会 放心的向后走到不是删除的节点上面
                prve = node;
                node = node.next;
            }


        }
    }

    /**
     * 删除链表中第一个值为 val的节点
     */
    public void remoValueOnce(int val){

        int tmp = getByValue(val);
        if( tmp != -1 ){

            remove(tmp);
        }
    }

    /**
     *查找第一个为 val 的 索引值为多少,找不到则返回 -1
     */
    public int getByValue(int val){
        Node prve = dummyHead.next;
        for (int i = 0; prve != null ; i++) {
            if(prve.val == val){
                return i;
            }
            prve = prve.next;
        }

        //如果都没找到，则不存在 返回 -1
        return -1;
    }

    /**
     * 查询链表中 是否包含 val 值
     * @return
     */
    public boolean contains(int val){
        int index = getByValue(val);
        return index != -1;
    }

    /**
     * 查询索引为 index 的元素 val 为多少,
     * @return
     */
    public int get(int index){
        // 1.判断index的合法性
        if( rangeCheck(index) ){
           Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }
            return x.val;
        }
        //不符合索引要求走到这里
        System.out.println("查询的索引值不合理！");
        return -1;
    }

    /**
     * 修改索引为 index 位置的节点值，改为 newVal
     * 返回修改前的值
     */
    public int set(int index, int newVal){

        if(rangeCheck(index)){

            Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }//循环后x指向的就是索引位置
            int rep = x.val;//保存待返回的值
            x.val = newVal;
            return rep;
        }
        //到这里说明索引不合理
        System.out.println("输入修改的索引不合理");
        return -1;
    }

    //判断索引是否合格
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

    //模拟完善一下toString函数，打印我们写的链表
    public String toString(){
        String rep = "";
        Node prve = dummyHead.next;//第一个节点位置

        while(prve != null){

            rep += prve.val;
            rep += " -> ";
            prve = prve.next;
        }
        rep += "NULL";//表示走到头了
        return rep;
    }

}

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
    //构造方法
    //1 当传入一个val值的时候，自动给它赋值
    public Node(int val) {
        this.val = val;
    }
    //2 当传入val值和下一个地址的时候，自动给它赋值
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
    //3 再弄的无参的，什么都不做
    public Node(){

    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/729602.html

手把手教你写出一个带头单链表

发表评论

评论列表（0条）