一、链表介绍

链表是有序的列表，但是他的内存中是存储如下

1. 链表是以节点的方式来存储，是链式存储
2. 每个节点包括 data 域，next 域：指向下一个字节
3. 如果：链表的各个节点不一定是连续存储
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表（带头节点）逻辑结构示意图

二、单向链表的应用实例

使用带head头的单项链表实现 -水浒英雄排行榜管理完成对英雄任务的增删改查操作

1. 第一种方法在添加影响时，直接添加到链表的尾部。

思路分析示意图：

1. 第二种方式在添加英雄时，根据排名（no）将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）

思路分析示意图

1. 修改节点功能

思路分析：
先找到该节点，通过遍历
temp.name = newHeroNode.name;
temo.nickname = newHeroNode.nickname

1. 删除节点

思路分析的示意图：

1. 代码演示 ```java package datastructures.linkedlist;

/**

• @author : [Zara-cat]
• @version : [v1.0]
• @className : SingleLinkedList
• @description : [单向链表]
• @createTime : [2021/10/11 14:14]
• @updateUser : []
• @updateTime : [2021/10/11 14:14]

• @updateRemark : [描述说明本次修改内容] */ public class SingleLinkedList { //初始化一个头节点，头节点不要动,不存放任何数据 private HeroNode head = new HeroNode(0,””,””);

  /**

  • 添加节点到单向链表

  • @param heroNode 节点 */ public void add(HeroNode heroNode){ //思路：当不考虑编号顺序时 // 1.找到当前链表的最后节点 // 2.将最后这个节点的next 指向新的节点 //因为head节点不能动，因此我们需要一个辅助变量（指针）temp HeroNode temp = head; //遍历链表，找到最后 while (true){

     //找到链表最后
     if (temp.next == null){
         break;
     }
     //如果没有找到最后,就将temp后移，把原来temp的next重新赋值给这个temp临时变量（指针）
     temp = temp.next;

    } //当推出while循环时，temp就指向了链表的最后 temp.next = heroNode; }

    /**

  • 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
  • 如果有这个排名，则添加失败，并给出提示

  • @param heroNode */ public void addByOder(HeroNode heroNode){ //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 //因为是单列表，因此我们找的temp 是位于添加位子的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false; //标志添加的编号是否存在，默认位false while (true){

     if (temp.next == null){ //找到链表最后了
         break;
     }
     if (temp.next.no > heroNode.no){ //位置找到 就在temp的后边插入
         break;
     }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode已经存在
         flag = true;
         break;
     }
     temp = temp.next; //后移

    } //判断flag的值 if (flag){

     System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);

    }else{

     heroNode.next = temp.next;
     temp.next = heroNode;

    } }

    /**

  • 修改节点的信息，根据no编号来修改，即no编号不能改
  • 说明：
  • 1.根据 newHeroNode 的 no 来修改节点

  • @param newHeroNode */ public void update(HeroNode newHeroNode){ //判断是否空 if (head.next == null){

     System.out.println("链表为空");
     return;

    } //找到需要修改的节点，根据 no 编号 //先定义一个辅助变量 HeroNode temp = head.next; boolean flag = false; //表示是否找到该节点 while (true){

     if (temp == null){
         break;//以及遍历完列表
     }
     if (temp.no == newHeroNode.no){
         //这里的temp就是我们将要修改的节点
         //找到了
         flag = true;
         break;
     }
     temp = temp.next;

    } //根据flag，判断是否找到需要修改的节点 if (flag){

     //flag 为 true 找到
     temp.name = newHeroNode.name;
     temp.nickName = newHeroNode.nickName;

    }else {

     //没有找到
     System.out.printf("没有找到 %d 的节点,不能修改\n",newHeroNode.no);

    } }

    /**

  • 删除节点
  • 思路：
  • 1.head节点不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  • 2.我们在比较时，是temp.next.no 和 需要删除的节点的no比较 */ public void delete(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.printf(“没有找到 %d ，不存在\n”,no); } } /**

  • 显示链表【遍历】 */ 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.next;

    } } public static void main(String[] args) { //进行测试 //先创建节点 HeroNode heroNode1 = new HeroNode(1, “宋江”, “及时雨”); HeroNode heroNode4 = new HeroNode(4, “林冲”, “豹子头”); HeroNode heroNode2 = new HeroNode(2, “卢俊义”, “玉麒麟”); HeroNode heroNode3 = new HeroNode(3, “吴用”, “智多星”);

    //创建列表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入 /singleLinkedList.add(heroNode1); singleLinkedList.add(heroNode2); singleLinkedList.add(heroNode3); singleLinkedList.add(heroNode4);/ //编号顺序 singleLinkedList.addByOder(heroNode1); singleLinkedList.addByOder(heroNode3); singleLinkedList.addByOder(heroNode4); singleLinkedList.addByOder(heroNode2); //singleLinkedList.addByOder(heroNode1); System.out.println(“修改前的链表：”); singleLinkedList.list(); //测试修改节点 HeroNode newHeroNode2 = new HeroNode(2, “小卢”, “玉麒麟~~”); singleLinkedList.update(newHeroNode2); System.out.println(“修改后的链表：”); singleLinkedList.list(); //删除节点 singleLinkedList.delete(1); singleLinkedList.delete(4); singleLinkedList.delete(2); singleLinkedList.delete(3); System.out.println(“删除后的链表：”); singleLinkedList.list(); }

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

public HeroNode (int hno,String hname,String hnickName){
    this.no = hno;
    this.name = hname;
    this.nickName = hnickName;
}
@Override
public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            ", nickName='" + nickName + '\'' +
            '}';
}

}

6. **运行结果**
![image.png](https://cdn.nlark.com/yuque/0/2021/png/12768333/1634280439933-c57158b7-e047-4c9e-a48e-a6b788b93337.png#clientId=ue20c43cb-2d16-4&from=paste&height=299&id=u6ffea8dd&margin=%5Bobject%20Object%5D&name=image.png&originHeight=299&originWidth=443&originalType=binary&ratio=1&size=30972&status=done&style=shadow&taskId=u1f42e11d-5f6a-4415-86cf-3d5c0074af5&width=443)
<a name="MmhYi"></a>
# 三、单向链表的面试题
**单链表的常见面试题有如下：**
1. **求单链表中有效节点的个数**
**代码如下：**
```java
    /**
     * 获取到单链表的节点的个数（如果是带头节点的链表，不统计头节点）
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }
注意：这里就是依靠一个辅助cur来进行while遍历链表，然后length计数就可以了。
      记得在循环体中要cur = cur.next后移一下条件

1. 查找单链表中的倒数第k个节点【新浪面试题】

代码如下：

     /**
     * 查找单链表中的倒数第k个节点【新浪面试题】
     * 思路：
     *      编写一个方法，传入head index
     *      index是导数第index个节点
     *      先把链表从头到尾遍历，得到链表总的有效节点个数 getLength()
     *      得到size后，我们从链表头开始遍历（size - index）个，就可以得到
     * @param head 头节点
     * @param index 导数第index个
     * @return 得到返回HeroNode 否者返回null
     */
    public static HeroNode findLastIndexHeroNode(HeroNode head,int index){
        if (head.next == null){
            return null;
        }
        //得到有效节点个数
        int size= getLength(head);
        //在做index校验
        if (index<=0||index>size){
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp ;
    }
 注意 ：size - index这一点就可以了。

1. 单链表的反转【腾讯面试题】

思路分析图解：

思路：

     1. 先定义一个节点 reverseHead = new HeroNode();
     1. 从头到尾遍历原来的链表，没遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
     1. 原来的链表的head.next = reverseHead.next

代码如下：

    /**
     * 将单链表反转
     * @param head
     */
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null){
            return;
        }
        // 定义一个辅助的指针（变量）,帮助我们遍历原来的链表
        HeroNode cur = head.next;
        //指向当前节点【cur】的下个节点
        HeroNode next = null;
        HeroNode reversetHead = new HeroNode(0,"","");
        //遍历原来的链表，并从头到位遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表revershtHead的最前端
        while (cur != null){
            next = cur.next; //先暂时保存当前节点的下一个节点，while遍历使用
            //将reversetHead.next这个节点放在cur【当前节点的next后】，然后将reversetHead.next 重新赋值cur
            //这样就在reverset头部插入了【头插法】
            cur.next = reversetHead.next;
            reversetHead.next = cur;
            // 继续遍历
            cur = next;
        }
        head.next = reversetHead.next;
    }
注意： 这里有一个临时next节点。    
    这几行重点代码：
        cur.next = reversetHead.next;
        reversetHead.next = cur;
         head.next = reversetHead.next;

1. 从尾到头打印单链表

思路分析图解：

代码实现：
写了一个小demo ，测试Stack的使用

/**
 * @author : [Zara-cat]
 * @version : [v1.0]
 * @className : TestStack
 * @description : [这里先简单的了解一下栈stack的基本使用]
 * @createTime : [2021/10/26 14:28]
 * @updateUser : [Zara-cat]
 * @updateTime : [2021/10/26 14:28]
 * @updateRemark : [描述说明本次修改内容]
 */
public class TestStack {
    //栈的先进后出
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        //入栈
        stack.add("jack");
        stack.add("tom");
        stack.add("smith");
        //出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}

单链表的逆序打印代码：

    /**
     * 方式2：
     * 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现里逆序打印的效果
     * （这样做就不破坏原来链表的结构）
     * @param head
     */
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }
        //创建一个栈，将各个节点压入栈中
        Stack<HeroNode> heroNodeStack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while (cur != null){
            heroNodeStack.push(cur);
            cur = cur.next;
        }
        //将栈中的节点进行打印
        while (heroNodeStack.size() > 0){
            System.out.println(heroNodeStack.pop());
        }
    }

四、双向链表的应用实例

对上图说明：

1. 遍历 方法和 单例表一样，知识可以向前，也可以向后查找
2. 添加（默认添加到双向链表的最后）
   • 先找到双向链表的最后这个节点
   • temp.next = newHeroNode
   • newHeroNode.pre = temp
3. 修改 思路和 原来的单向链表一样
4. 删除
   • 因为是双向链表，因此，我们可以实现自我删除某个几点
   • 直接找到要删除的节点，比如temp
   • temp.pre.next = temp.next
   • temp.next.pre = temp.pre
5. 添加（按顺序添加）

代码实现：

package datastructures.linkedlist;

/**
 * @author : [Zara-cat]
 * @version : [v1.0]
 * @className : DoubleLinkedList
 * @description : [双向链表]
 * @createTime : [2021/10/27 10:21]
 * @updateUser : [Zara-cat]
 * @updateTime : [2021/10/27 10:21]
 * @updateRemark : [描述说明本次修改内容]
 */
public class DoubleLinkedList {
    //初始化一个头节点，头节点不要动,不存放任何数据
    private HeroNode2 head = new HeroNode2(0,"","");

    public HeroNode2 getHead() {
        return head;
    }
    /**
     * 添加节点到双向链表的最后
     * @param heroNode 节点
     */
    public void add(HeroNode2 heroNode){
        //思路：当不考虑编号顺序时
        //  1.找到当前链表的最后节点
        //  2.将最后这个节点的next 指向新的节点
        //因为head节点不能动，因此我们需要一个辅助变量（指针）temp
        HeroNode2 temp = head;
        //遍历链表，找到最后
        while (true){
            //找到链表最后
            if (temp.next == null){
                break;
            }
            //如果没有找到最后,就将temp后移，把原来temp的next重新赋值给这个temp临时变量（指针）
            temp = temp.next;
        }
        //当推出while循环时，temp就指向了链表的最后
        //形成双向
        temp.next = heroNode;
        heroNode.pre = temp;
    }
    /**
     * 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
     * 如果有这个排名，则添加失败，并给出提示
     * @param heroNode
     */
    public void addByOder(HeroNode2 heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为是单列表，因此我们找的temp 是位于添加位子的前一个节点，否则插入不了
        HeroNode2 temp = head;
        boolean flag = false; //标志添加的编号是否存在，默认位false
        while (true){
            if (temp.next == null){ //找到链表最后了
                break;
            }
            if (temp.next.no > heroNode.no){ //位置找到 就在temp的后边插入
                break;
            }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode已经存在
                flag = true;
                break;
            }
            temp = temp.next; //后移
        }
        //判断flag的值
        if (flag){
            System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
        }else{
            heroNode.next = temp.next;
            /**
             * 注意：这一需要一个条件 如果正好插入的链表的尾部，就不需要进行这一步操作了
             */
            if (temp.next !=null ){
                temp.next.pre  = heroNode;
            }
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    }
    /**
     * 修改节点的信息，根据no编号来修改，即no编号不能改
     * 说明：
     *      1.根据 newHeroNode 的 no 来修改节点
     * @param newHeroNode
     */
    public void update(HeroNode2 newHeroNode){
        //判断是否空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据 no 编号
        //先定义一个辅助变量
        HeroNode2 temp = head.next;
        boolean flag = false; //表示是否找到该节点
        while (true){
            if (temp == null){
                break;//以及遍历完列表
            }
            if (temp.no == newHeroNode.no){
                //这里的temp就是我们将要修改的节点
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag，判断是否找到需要修改的节点
        if (flag){
            //flag 为 true 找到
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            //没有找到
            System.out.printf("没有找到 %d 的节点,不能修改\n",newHeroNode.no);
        }
    }
    /**
     * 删除节点
     * 思路：
     *      1.head节点不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
     *      2.我们在比较时，是temp.next.no 和 需要删除的节点的no比较
     */
    public void delete(int no){
        HeroNode2 temp = head.next;
        boolean flag = false; //标志是否找到待删除节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next = temp.next;
            //这里其实有风险的，比如我如果删除正好是链表的最后一个节点，temp.next.pre 会报空指针异常的
            //temp.next.pre = temp.pre;
            //现在处理一下
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.printf("没有找到 %d ，不存在\n",no);
        }
    }
    /**
     * 显示链表【遍历】
     */
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此我们需要一个辅助变量进行遍历
        HeroNode2 temp = head.next;
        while (true){
            //判断是否到链表最后了
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp.toString());
            //然后后移
            temp = temp.next;
        }
    }


    public static void main(String[] args) {
        //测试
        System.out.println("双向链表的测试：");
        HeroNode2 heroNode1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 heroNode4 = new HeroNode2(4, "林冲", "豹子头");
        HeroNode2 heroNode2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 heroNode3 = new HeroNode2(3, "吴用", "智多星");
        //创建双向链表对象
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        System.out.println("顺序添加：");
        doubleLinkedList.addByOder(heroNode4);
        doubleLinkedList.addByOder(heroNode1);
        doubleLinkedList.addByOder(heroNode3);
        doubleLinkedList.addByOder(heroNode2);
        doubleLinkedList.list();
       /* doubleLinkedList.add(heroNode1);
        doubleLinkedList.add(heroNode2);
        doubleLinkedList.add(heroNode3);
        doubleLinkedList.add(heroNode4);
        doubleLinkedList.list();*/

        //修改
        HeroNode2 newHeroNode = new HeroNode2(4, "王振宇", "大哥哥");
        System.out.println("修改：");
        doubleLinkedList.update(newHeroNode);
        doubleLinkedList.list();

        //删除
        System.out.println("删除：");
        doubleLinkedList.delete(1);
        doubleLinkedList.list();


    }
}
//定义HeroNode ，每一个HeroNode 对象就是一个节点
class HeroNode2{
    public int no;
    public String name;
    public String nickName;
    public HeroNode2 next; //指向下一个节点，默认为null
    public HeroNode2 pre;//指向前一个节点，默认为null

    public HeroNode2 (int hno,String hname,String hnickName){
        this.no = hno;
        this.name = hname;
        this.nickName = hnickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

运行结果：

下载地址：https://pan.baidu.com/s/1Kg7UUpO3wwALX6x28cWA7A
提取码：8op3