[数据结构与算法]算法_链表篇

单链表和双向链表

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

链表简介

单链表（单向链表）：

由两部分组成 数据域（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 +
                '}';
    }
}

逻辑实现类：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.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
//        根据flag,判断是否找到要修改的节点
        if (flag) {
            temp.name = newHero.name;
            temp.nickName = newHero.nickName;
            System.out.println("更新成功！");
        } else {
            System.out.println("未查到编号为" + newHero.no + "的英雄,不能更该");
        }
    }

    /**
     * @return void
     * @Description //TODO  删除相应编号的节点英雄
     * @Param [heroNo]
     **/
    public void deleteHero(int heroNo) {
        /* 1. 先找到待删除的节点的前一个节点
        *  2. temp.next=temp.next.next;
        *  3. 被删除的节点，不会有其它指向的引用，会被jvm垃圾回收机制回收
        * */
        HeroNode temp=head;
        boolean flag=false;
        while(true){
            if (temp==null){
                break;
            }
            if (temp.next.no==heroNo){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.println("未找到该编号的英雄，删除失败~");
        }
    }

    /**
     * @return
     * @Description //TODO  遍历单链表
     * @Param
     **/
    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.toString());
//             将temp后移
            temp = temp.next;
        }
    }
}

测试类

/**
 * @description: 单链表测试
 */
public class HeroRoles {
    public static void main(String[] args) {
        HeroNode hero1=new HeroNode(1,"诸葛亮","卧龙");
        HeroNode hero2=new HeroNode(2,"关羽","美髯公");
        HeroNode hero3=new HeroNode(3,"张飞","万夫不当");
        HeroNode hero4=new HeroNode(4,"孟获","南蛮王");
        HeroNode hero5=new HeroNode(4,"曹操","魏武帝");
        HeroNode hero6=new HeroNode(5,"孟获","南蛮王");

        SingleLinkedList singleLinkedList=new SingleLinkedList();
//        添加入链表，不按编号顺序添加
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

//        按照编号顺序添加
        System.out.println("==========添加========");
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero6);

//        展示链表
        singleLinkedList.list();

//        修改节点英雄
        System.out.println("==========修改========");
        singleLinkedList.updateHero(hero5);
        singleLinkedList.list();

//        删除节点英雄
        System.out.println("==========删除========");
        singleLinkedList.deleteHero(4);
        singleLinkedList.list();
    }

}

运行结果示例：

==========添加========
插入成功！
插入成功！
插入成功！
插入成功！
待插入的英雄编号4已存在！不能添加此编号的英雄~
插入成功！
HeroNode{no=1, name='诸葛亮', nickName='卧龙'}
HeroNode{no=2, name='关羽', nickName='美髯公'}
HeroNode{no=3, name='张飞', nickName='万夫不当'}
HeroNode{no=4, name='孟获', nickName='南蛮王'}
HeroNode{no=5, name='孟获', nickName='南蛮王'}
==========修改========
更新成功！
HeroNode{no=1, name='诸葛亮', nickName='卧龙'}
HeroNode{no=2, name='关羽', nickName='美髯公'}
HeroNode{no=3, name='张飞', nickName='万夫不当'}
HeroNode{no=4, name='曹操', nickName='魏武帝'}
HeroNode{no=5, name='孟获', nickName='南蛮王'}
==========删除========
HeroNode{no=1, name='诸葛亮', nickName='卧龙'}
HeroNode{no=2, name='关羽', nickName='美髯公'}
HeroNode{no=3, name='张飞', nickName='万夫不当'}
HeroNode{no=5, name='孟获', nickName='南蛮王'}

Process finished with exit code 0

例题:删除链表的倒数第 n 个节点

算法实现

双向链表的节点类

/**
 * @description: DataNode对象就是一个节点
 */
public class DataNode {

    public int no;
    public String value;
    public DataNode next;   //默认null
    public DataNode pre;   //默认null

    public DataNode(int no, String value) {
        this.no = no;
        this.value = value;
    }

    @Override
    public String toString() {
        return "DataNode{" +
                "no=" + no +
                ", value='" + value + '\'' +
//                ", next=" + next +
//                ", pre=" + pre +
                '}';
    }
}

实现算法逻辑的类

/**
 * @description:
 */
public class DoubleLinkedList {
    /** 初始化头节点 **/
    private DataNode head = new DataNode(0, "");

    /** 返回头节点 */
    public DataNode getHead() {
        return head;
    }

    /**
     * @return void
     * @Description //TODO  双向链表的最后一位添加数据
     * @Param [dataNode]
     **/
    public void add(DataNode dataNode) {

//        先让辅助变量temp指向head
        DataNode temp = head;
//        遍历链表，找到最后一位
        while (true) {
//            判断是否为最后一位
            if (temp.next == null) {
                break;
            }
//            若不是最后一位，则将辅助变量后移
            temp = temp.next;
        }
//        将新的 对象赋值给链表的最后一位,形成一个双向链表
        temp.next = dataNode;
        dataNode.pre = temp;
    }

    /**
     * @return void
     * @Description //TODO 更新链表
     * @Param [newData]
     **/
    public void updateHero(DataNode newData) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        DataNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newData.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
//        根据flag,判断是否找到要修改的节点
        if (flag) {
            temp.value = newData.value;
            System.out.println("更新成功！");
        } else {
            System.out.println("未查到编号为" + newData.no + "的数据,不能更改！");
        }
    }


/**
     * @return void
     * @Description //TODO 删除节点
     * @Param [dataNo]
     **/
    public void deleteHero(int dataNo) {
//        判断当前链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        DataNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//链表最后节点的next
            }
            if (temp.no == dataNo) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
//            删除
            temp.pre.next = temp.next;
//            具有风险：如果是最后一个节点，则不需要执行下面这句话.否则会有空指针异常
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.println("未找到该编号的数据，删除失败~");
        }
    }


    /**
     * @return void
     * @Description //TODO  遍历双向链表
     * @Param []
     **/
    public int list() {
        //链表节点个数n
        int n=0;
//        判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return 0;
        } else {
//         头节点无值，且不可以作为游标。因此，使用辅助变量作为游标遍历。
            DataNode temp = head.next;
            while (true) {
//             判断链表是否时最后一个节点
                if (temp == null) {
                    break;
                }
//             输出节点的信息
                System.out.println(temp.toString());
//             将temp后移
                temp = temp.next;
                n++;
            }
            return n;
        }
    }
}

测试类

import java.util.Scanner;

/**
 * @description:测试
 */
public class TestDoubleLinkedList {
    public static void main(String[] args) {
        DataNode dataNode1 = new DataNode(1, "曹操");
        DataNode dataNode2 = new DataNode(2, "刘备");
        DataNode dataNode3 = new DataNode(3, "诸葛亮");
        DataNode dataNode4 = new DataNode(4, "美髯公");
        DataNode dataNode5 = new DataNode(5, "孟获");

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        System.out.println("==============数据===============");
//        增加数据
        doubleLinkedList.add(dataNode1);
        doubleLinkedList.add(dataNode2);
        doubleLinkedList.add(dataNode3);
        doubleLinkedList.add(dataNode4);
        doubleLinkedList.add(dataNode5);
//        遍历输出
        int num=doubleLinkedList.list();
//        System.out.println(num);
//        删除链表的倒数第n个节点
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入你需要删除的倒数第n个节点！");
        int n = scan.nextInt();
//        判断链表是否有倒数第n个节点

        System.out.println("");
        if (n >num) {
            System.out.println("此链表没有那么多节点，无法删除~");
        }else{
            doubleLinkedList.deleteHero(num-n+1);
        }
//        遍历链表
        System.out.println("结果");
        doubleLinkedList.list();
    }

}

输出结果：

==============数据===============
DataNode{no=1, value='曹操'}
DataNode{no=2, value='刘备'}
DataNode{no=3, value='诸葛亮'}
DataNode{no=4, value='美髯公'}
DataNode{no=5, value='孟获'}
请输入你需要删除的倒数第n个节点！
3

结果
DataNode{no=1, value='曹操'}
DataNode{no=2, value='刘备'}
DataNode{no=4, value='美髯公'}
DataNode{no=5, value='孟获'}

Process finished with exit code 0