03、数据结构与算法 - 实战:单链表的增加(添加到链尾,按顺序添加)、删除、查询、修改。

前言

一、单链表(Linked List)介绍

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

 

特点

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

二、应用实例

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

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

2.1 第一种添加思路

添加思路

  1. 先创建一个head 头节点, 作用就是表示单链表的头
  2. 后面我们每添加一个节点,就直接加入到 链表的最后
  • 遍历思路
  1. 通过一个辅助变量遍历,帮助遍历整个链表
  • 代码是 SingleLinkedList 类 的 addLinked(HeroNode newNode) 方法。
  • 图解如下:
     

2.2 第二种添加思路

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

添加思路

需要按照编号的顺序添加

  1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
  2. 新的节点 next = temp.next
  3. 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 删除节点

  • 删除节点思路:
  1. 我们 先找到 需要删除的这个节点的 前一个节点 temp
  2. temp.next = temp.next.next
  3. 被删除的节点,将不会有其它引用指向,会被垃圾回收机制回收
  • 代码是 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;
	}

}

  • 日志分析