数据结构与算法 - 实战：单链表的增加（添加到链尾，按顺序添加）、删除、查询、修改。

前言

一、单链表（Linked List）介绍

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

特点：

1、链表是以节点的方式来存储，是链式存储；
2、 每个节点包含data域，next域：指向下一个节点；
3、如图：发现链表的各个节点不一定是连续存储；
4、链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定；
5、 链表head节点不存放数据，最后一个节点的next域为null；
6、单链表（带头结点）逻辑结构示意图如下：；

二、应用实例

使用带head头的 单向链表 实现 –水浒英雄排行榜管理

1、完成对英雄人物的增删改查操作.；
2、添加英雄的第一种方法，直接添加到链表的尾部；
3、添加英雄的第二种方法，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)；

2.1 第一种添加思路

添加思路：

先创建一个head 头节点，作用就是表示单链表的头

后面我们每添加一个节点，就直接加入到链表的最后

遍历思路：

通过一个辅助变量遍历，帮助遍历整个链表

代码是 SingleLinkedList 类的 addLinked(HeroNode newNode) 方法。
图解如下：

2.2 第二种添加思路

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

添加思路

需要按照编号的顺序添加

首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定

新的节点 next = temp.next

将temp.next = 新的节点

代码是 SingleLinkedList 类的 addLinkedByOrder(HeroNode newNode) 方法。
思路的分析示意图：

2.3 修改节点

思路

1、通过遍历，先找到该节点temp.no==newNode.no，辅助节点temp就是该节点；
2、 temp.name=newNode.name;；
temp .nickname =newNode.nickname

代码是 SingleLinkedList 类的 updateNode(HeroNode newNode)方法。

2.4 删除节点

删除节点思路：

我们 先找到需要删除的这个节点的前一个节点 temp

temp.next = temp.next.next

被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

代码是 SingleLinkedList 类的 deleteNode(int no)方法。
思路分析的示意图：

三、代码实现

3.1 项目结构

HeroNode：定义的节点类。
SingerLinkedList: 单链表方法。
SingleLinkedListMain: 测试 Main 方法。
TestStack: 测试栈这个数据结构。

3.2 HeroNode.java 单链表节点

package com.feng.ch03_singlelinkedlist;

/*
* 定义 HeroNode ，每个 HeroNode 对象就是一个节点, 就是一个 Javabean
* */
public class HeroNode {
   
     
    // data域 ：数据
    public int no;
    public String name;
    public String nickname;
    // next域 ：指向下一个节点
    public HeroNode next;

    // 构造器
    public HeroNode(int hNo, String  hName, String hNickName){
   
     
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

    // 为显示方便，重写 toString()
    @Override
    public String toString() {
   
     
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

3.3 SingleLinkedList.java 单链表

package com.feng.ch03_singlelinkedlist;

/*
 * 定义 SingleLinkedList ，管理英雄
 * */
public class SingleLinkedList {
   
     

    // 初始化一个头结点，头结点不要动, 不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
   
     
        return head;
    }

    // 添加节点到单向链表
    /*
     * 第一种添加方式：直接在链表最后添加
     * 思路： 当不考虑编号顺序时，1、找到当前链表的最后节点  2、将新节点挂载到最后节点上-》将最后这个节点的next 指向 新的节点
     * */
    public void addLinked(HeroNode newNode) {
   
     
        // 因为头结点不能动，因此需要一个辅助节点 temp 来进行遍历
        HeroNode temp = head;
        // 遍历链表，找到最后
        while (true) {
   
     
            if (temp.next == null) {
   
     
                break;
            }
            temp = temp.next;
        }
        // 当退出 循环时，temp就指向了链表的最后
        // 将最后这个节点的next 指向新的节点
        temp.next = newNode;
    }

    /*
     *
     * 第二种方式在添加节点时（英雄），根据顺序（排名）将英雄插入到指定位置
     * （如果有这个排名，则添加失败，并给出提示）
     *  重点：newNode.next = temp.next;  temp.next = newNode;  这两句顺序不能颠倒
     * */
    public void addLinkedByOrder(HeroNode newNode) {
   
     
        // 因为头结点不能动，因此需要一个辅助节点 temp 来帮助找到添加的位置
        // 因为 单链表，我们找的 temp 是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
   
     
            if (temp.next == null) {
   
     
                break;
            }
            if (temp.next.no > newNode.no) {
   
     
                break;
            } else if (temp.next.no == newNode.no) {
   
     
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
   
     
            System.out.printf("准备插入的英雄的编号 %d 已经存在了，不能加入\n", head.no);
        } else {
   
     
            // 先挂载后面，在挂载前面
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    public void updateNode(HeroNode newNode){
   
     
        //
        if (head.next == null){
   
     
            System.out.println("链表为空~");
            return;
        }
        // 定义辅助变量
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
   
     
            if (temp == null){
   
     
                break; // 已经遍历完链表
            }
            if (temp.no == newNode.no){
   
     
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
   
     
            temp.name = newNode.name;
            temp.nickname = newNode.nickname;
        }else{
   
     
            System.out.println("链表中没有该英雄~");
        }
    }

    /*
    * 删除节点
    * 思路：
    * 1、head 不能动，因此 需要一个 temp 辅助节点找到待删除节点的前一个节点
    * 2、说明 我们在比较时， 是 temp.next.no 和 需要删除的节点的 No 比较
    * */
    public void deleteNode(int no){
   
     
        if(head.next == null){
   
     
            System.out.println("链表为空， 无需删除~");
            return;
        }

        HeroNode temp = head;
        boolean flag = false; // 标志是否找到待删除节点
        while (true){
   
     
            if (temp.next == null){
   
     
                break;
            }
            if (temp.next.no == no){
   
     
                flag = true;
                break;
            }
            temp = temp.next; // temp 后移一位， 遍历
        }
        if (flag){
   
      // 找到
            temp.next = temp.next.next;
        }else{
   
      // 没找到
            System.out.printf("要删除的节点 %d 节点不存在", no);
        }
    }

    //显示链表【遍历】
    public void list() {
   
     
        if (head.next == null) {
   
     
            System.out.println("链表为空");
            return;
        }
        // 因为头结点不能动， 因此需要一个辅助节点 temp 来遍历
        HeroNode temp = head.next;
        while (true) {
   
     
            if (temp == null) {
   
     
                return;
            }
            // 输出节点信息
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

3.4 SingleLinkedListMain.java 测试

package com.feng.ch03_singlelinkedlist;

import java.util.Stack;

/*
* 单链表
*
* 单链表的 添加、按顺序添加、删除、修改、遍历 功能
*
* 单链表的面试题：
* 2、 将单链表反转 【腾讯面试题】  ** 有难度，需要思考
* 3、实现单链表的逆序打印【百度面试题】
*   3.1 方式1：先反转，在打印。
*   3.2 方式2：利用栈 这个数据结构，将各个节点压入栈中，然后利用栈的先进先出的特点，实现逆序打印的效果
* */
public class SingleLinkedListMain {
   
     
    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, "林冲", "豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 添加节点 到最后
//        singleLinkedList.addLinked(hero1);
//        singleLinkedList.addLinked(hero2);
//        singleLinkedList.addLinked(hero4);
//        singleLinkedList.addLinked(hero3);

        // 添加节点 按顺序
        singleLinkedList.addLinkedByOrder(hero1);
        singleLinkedList.addLinkedByOrder(hero2);
        singleLinkedList.addLinkedByOrder(hero4);
        singleLinkedList.addLinkedByOrder(hero3);

        // 显示节点
        System.out.println("显示初始添加后的节点~");
        singleLinkedList.list();

        // 测试修改
        System.out.println();
        System.out.println("测试修改后的结果");
        HeroNode updateNode = new HeroNode(2, "小卢", "玉麒麟");
        singleLinkedList.updateNode(updateNode);
        singleLinkedList.list();

        // 测试删除
        System.out.println();
        System.out.println("测试删除后的结果");
        singleLinkedList.deleteNode(2);
        singleLinkedList.deleteNode(3);
        singleLinkedList.list();

        // 测试返回单链表有效个数
        System.out.println();
        System.out.println("单链表有效个数=" + getLength(singleLinkedList.getHead()));

        // 测试 查看倒数第 K 个节点的 数据
        System.out.println();
        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), 1);
        System.out.println("倒数第 K 个节点的 res=" + lastIndexNode);

        // 测试单链表的反转
        System.out.println();
        System.out.println("测试反转后的链表");
        reverseList(singleLinkedList.getHead());
        singleLinkedList.list();

        // 测试单链表的逆序打印
        System.out.println();
        System.out.println("测试单链表的逆序打印");
        reversePrint(singleLinkedList.getHead());
    }

    /*
     * 方法：实现单链表的逆序打印【百度面试题】
     * 方式1：先反转，在打印。
     * 方式2：利用栈 这个数据结构，将各个节点压入栈中，然后利用栈的先进先出的特点，实现逆序打印的效果
     * */
    public static void reversePrint(HeroNode head) {
   
     
        if (head.next == null) {
   
     
            return;
        }

        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null) {
   
     
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
   
     
            System.out.println(stack.pop());
        }
    }

    /*
     * 将单链表反转 【腾讯面试题】
     * */
    public static void reverseList(HeroNode head) {
   
     
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
   
     
            return;
        }

        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        HeroNode temp = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");

        /*
         * 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
         * 动脑筋
         * */
        while (temp != null) {
   
     
            next = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用， 此时，temp 为独立的一个节点
            temp.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端，将反转链表的后面 挂载到 temp 上。
            reverseHead.next = temp;//将cur 连接到新的链表上， 将 temp 挂载到 反转链表的后面，就完成了。
            temp = next;//让cur后移，
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }
    /*
     * 方法：查找单链表中的倒数第k个结点 【新浪面试题】
     * 思路：
     * 1. 编写一个方法，接收head节点，同时接收一个index
     * 2. index 表示是倒数第index个节点
     * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     * 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
     * 5. 如果找到了，则返回该节点，否则返回 null
     * */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
   
     
        //判断如果链表为空，返回null
        if (head.next == null) {
   
     
            return null;
        }
        //第一次遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //先做一个index的校验
        if (index < 0 || index > size) {
   
     
            return null;
        }
        //第二次遍历  size-index 位置，就是我们倒数的第K个节点
        //定义给辅助变量， for 循环定位到倒数的index
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
   
     
            temp = temp.next;
        }
        return temp;
    }

    /*
     * 方法：获取单链表的有效节点个数（如果是带头结点的链表，需要不统计头结点）
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     * */
    public static int getLength(HeroNode head) {
   
     
        if (head.next == null) {
   
     
            return 0;
        }
        HeroNode temp = head.next;
        int count = 0;
        /*while (true){
            if (temp== null){
                break;
            }
            count++;
            temp = temp.next;
        }*/
        while (temp != null) {
   
     
            count++;
            temp = temp.next;
        }
        return count;
    }
}

四、单向环形链表应用场景

4.1 osephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

4.2 单向环形链表介绍

五、Josephu(约瑟夫)问题

5.1Josephu 问题的示意图

Josephu问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
约瑟夫问题-创建环形链表的思路图解
约瑟夫问题-小孩出圈的思路分析图
约瑟夫问题-创建环形链表的思路图解
约瑟夫问题-小孩出圈的思路分析图

5.2 代码实现

package com.feng.ch03_linkedlist;

public class Josephu {
   
     
	public static void main(String[] args) {
   
     
		// 测试一把看看构建环形链表，和遍历是否ok
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
		circleSingleLinkedList.showBoy();

		// 测试一把小孩出圈是否正确
		circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
		// String str = "7*2*2-5+1-5+3-3";
	}
}

class CircleSingleLinkedList {
   
     
	// 创建一个 first 节点,。当前没有编号， 这个就是第一个节点
	private Boy first = null;

	/**
	 * 添加小孩节点，构建成一个环形的链表
	 * 
	 * @param nums
	 */
	public void addBoy(int nums) {
   
     
		// nums 做一个数据校验
		if (nums < 1) {
   
     
			System.out.println("没有小孩");
			return;
		}
		// 辅助指针，帮助构建环形链表
		Boy curBoy = null;
		// 使用for来创建我们的环形链表
		for (int i = 1; i <= nums; i++) {
   
     
			// 根据编号，创建小孩节点
			Boy boy = new Boy(i);
			// 如果是第一个小孩
			if (i == 1) {
   
     
				first = boy; // 生成的第一个节点 赋给原先设定好的 first
				first.setNext(first); // 构建环形链表
				curBoy = first; // 让curBoy指向第一个小孩
			} else {
   
     
				curBoy.setNext(boy); // 在后面添加
				boy.setNext(first); // 环形链表
				curBoy = boy; // 将最后一个 赋给 辅助指针。
			}
		}

	}

	/**
	 * 遍历当前的环形链表
	 */
	public void showBoy() {
   
     
		// 判断链表是否为空
		if (null == first) {
   
     
			System.out.println("链表为空~~");
			return;
		}
		// 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
		Boy curBoy = first;
		while (true) {
   
     
			System.out.printf("小孩的编号 %d \n", curBoy.getNo());
			if (curBoy.getNext() == first) {
   
     // 说明已经遍历完毕
				break;
			}
			curBoy = curBoy.getNext();// curBoy后移

		}
	}

	/**
	 * 根据用户的输入，计算出小孩出圈的顺序
	 * 
	 * @param startNo  表示从第几个小孩开始数数
	 * @param countNum 表示数几下
	 * @param nums     表示最初有多少小孩在圈中
	 */
	public void countBoy(int startNo, int countNum, int nums) {
   
     
		// 先对数据进行校验
		if (first == null || startNo < 1 || startNo > nums) {
   
     
			System.out.println("参数输入有误，请重新输入");
			return;
		}

		// 创建要给辅助指针,帮助完成小孩出圈
		Boy helper = first;
		// 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
		while (true) {
   
     
			if (first == helper.getNext()) {
   
     
				break;
			}
			helper = helper.getNext();
		}

		// 小孩报数前，先让 first 和 helper 移动 k - 1次
		for (int i = 0; i < startNo - 1; i++) {
   
     
			first = first.getNext();
			helper = helper.getNext();
		}
		// 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈
		// 这里是一个循环操作，知道圈中只有一个节点
		while (true) {
   
     
			if (first == helper) {
   
     
				break;
			}
			for (int i = 0; i < countNum - 1; i++) {
   
     
				first = first.getNext();
				helper = helper.getNext();
			}
			// 这时first指向的节点，就是要出圈的小孩节点
			System.out.printf("小孩%d出圈\n", first.getNo());

			// 这时将first指向的小孩节点出圈
			first = first.getNext(); // 改变 first 的值，为原来first 的下一个值
			helper.setNext(first); //
		}
		System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
	}
}

/**
 * 创建一个 Boy 类，表示一个节点
 */
class Boy {
   
     
	private int no; // 编号 数据域简单点
	private Boy next; //

	public Boy(int no) {
   
     
		super();
		this.no = no;
	}

	public int getNo() {
   
     
		return no;
	}

	public void setNo(int no) {
   
     
		this.no = no;
	}

	public Boy getNext() {
   
     
		return next;
	}

	public void setNext(Boy next) {
   
     
		this.next = next;
	}

}

日志分析

03、数据结构与算法 - 实战：单链表的增加（添加到链尾，按顺序添加）、删除、查询、修改。

前言