Java数据结构与算法-java数据结构与算法(二)

简介: Java数据结构与算法-java数据结构与算法

Java数据结构与算法-java数据结构与算法(一)https://developer.aliyun.com/article/1469487


链表

链表(Linked List)介绍  :

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

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

单向链表

单向链表存储节点思路图

单链表的应用实例

使用带 head 头的单向链表实现  –水浒英雄排行榜管理完成对英雄人物的增删改查操作

我们都知道 水浒传里有108位英雄吧

我们这里随便举例四个,我们想用链表的方式把他们放入我们的英雄榜里(单向链表)

新增,修改,删除的思路

添加英雄:

根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)  思路的分析示意图:

修改节点功能

古时候,有武功的人士逗喜欢为了排名去争斗,所以我们制作英雄榜需要有更换排名的功能

排名是固定的,他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可

  • 先找到该节点,通过遍历,
  • temp.name =  newHeroNode.name ; temp.nickname= newHeroNode.nickname

删除节点

这个功能呢可以理解为,有英雄不想争夺排名了,退休回家种田耕地享受生活了,我们需要把不需要位置的英雄占有的位置腾出来。

单向链表的增删改查

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.LinkedList
 * @className: LinkedlistDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/17 16:24
 * @version: 1.0
 */
public class LinkedlistDemo {
    public static void main(String[] args) {
        // 设置一些英雄对象
        HeroNode heroNode = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头");
        // 声明单向链表
        SingleLinkedlist linkedlist = new SingleLinkedlist();
        //加入我们的英雄节点
        //linkedlist.add(heroNode);
        //linkedlist.add(heroNode1);
        //linkedlist.add(heroNode2);
        //linkedlist.add(heroNode3);
        //加入按照编号
        linkedlist.addByOrder(heroNode);
        linkedlist.addByOrder(heroNode3);
        linkedlist.addByOrder(heroNode2);
        linkedlist.addByOrder(heroNode1);
        //输出节点信息
        linkedlist.List();
        System.out.println("更新数据后");
        linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师"));
        //输出节点信息
        linkedlist.List();
        System.out.println("删除数据后输出");
        linkedlist.DeleteNode(1);
        linkedlist.List();
    }
}
class SingleLinkedlist {
    //创建一个头结点
    HeroNode head = new HeroNode(0, "", "");
    //加入链表
    public void add(HeroNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //跳出while证明找到了最后的节点,将我们的新节点加入到最后的节点的next即可
        temp.next = node;
    }
    //添加节点 第二种方法
    public void addByOrder(HeroNode node) {
        /*
         * 因为头结点不能动,我们通过指针来记录头节点来帮助找到添加的位置
         *因为是单链表我们找的是 Temp是位于添加位置的前一个节点,否则插入不了
         * */
        //创建一个临时变量
        HeroNode temp = head;
        //用来标识 英雄是否存在 默认为不存在(false)
        boolean flag = false;
        while (true) {
            //找到最后为空的位置
            if (temp.next == null) {
                break;
            }
            //如果temp的下一个no 大于 我们加入的节点,就往temp加入
            if (temp.next.No > node.No) {
                break;
            }
            //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点
            else if (temp.next.No == node.No) {
                //将flag 修改为 true 代表已经存在
                flag = true;
                break;
            }
            //如果上面的都没达成就代表当前节点位置不对,向后继续遍历
            temp = temp.next;
        }
        //    判断 flag的值
        if (flag) {
            //如果为 true 代表节点已经存在
            System.out.printf("当前节点%d已经存在了,不能加入\n", node.No);
        } else {
            //    如果为false 那代表符合插入条件并且不存在与当前链表
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改节点信息
    public void updateNode(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改,我用 temp 来指向头结点
        HeroNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newHeroNode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newHeroNode.NickName;
            temp.Name = newHeroNode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newHeroNode.No);
        }
    }
    //删除节点信息
    public void DeleteNode(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;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除,这里我们只需要指向空 GC会回收
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 没有找到", 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);
            //后移一位
            temp = temp.next;
        }
    }
}
/**
 * 编写 水浒传英雄 节点
 *  用于存放每个英雄的属性
 * */
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 + '\'' +
                '}';
    }
}

链表使用效果

总结

我们这次制作了属于自己的英雄榜(单向链表),我们收货了什么呢?

  • 节点之间联系的思路
  • 逐渐适应数据结构的一些思想
  • 动手实操实现的习惯

单向链表各大厂面试题

新浪

/**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 新浪链表面试题 查找链表中的第k个节点
     * 思路:
     * 1.编写一个方法,接收head 节点,同时接收一个index
     * 2,index表示的是倒数第index 个节点
     * 3. 先把链表从头到尾遍历 得到链表的总长度 getlength
     * 4。得到Size之后 我们从链表的第一个开始遍历(Size-index)个,就可以得到
     * 5. 如果找到了 则返回该节点否则返回null
     * @date: 2021/12/18 15:12
     * @param head
     * @param index
     * @return: com.hyc.DataStructure.LinkedList.HeroNode
     */
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        // 如果除去头节点之后没有新的节点就代表链表是空的,返回空对象
        if (head.next == null) {
            return null;
        }
        // 获取到链表的长度
        int Size = SingleLinkedlist.getlength(head);
        //声明一个零时变量指向第一个有效的节点
        HeroNode cur = head.next;
        //假设 我们的例子是一共有三个有效节点 3 这里我们index 为 2 那么3-2 = 1 找到了倒数第二个的节点
        for (int i = 0; i < Size - index; i++) {
            cur = cur.next;
        }
        //找到节点之后我们直接返回即可
        return cur;
    }

腾讯

/**
     * @author 冷环渊 Doomwatcher
     * @context: 腾讯面试题 反转链表
     * 思路:
     * 1.先定义一个节点 reverseHead = new HeroNode();
     * 2.从头遍历原来的链表,每次遍历一个节点就将其取出并且放到信的链表的最前端,
     * 3.原来的链表head.next = reverseHead.Next
     * @date: 2021/12/18 15:38
     * @param head
     * @return: void
     */
    public static void reverseList(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        //需要新的一个空的头
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 获得第一个有效的节点
        HeroNode cur = head.next;
        //指向[cur]的下一个的节点
        HeroNode next = null;
        while (cur != null) {
            //保存当前的节点的下一个位置 有用
            next = cur.next;
            // 将cur的下一个指向 新的链表的最前端
            cur.next = reverseHead.next;
            //将新链表的最前端为cur
            reverseHead.next = cur;
            //cur 继续向后遍历
            cur = next;
        }
        head.next = reverseHead.next;
    }

百度

/**
 * @author 冷环渊 Doomwatcher
 * @context: 百度面试题, 在不破坏链表结构的情况下 反向输出链表
 * 这里我们利用 一个 即将学到的 数据结构叫 栈
 * 栈结构的特点就是 先进后出
 * 将链表的节点按顺序遍历压入栈
 * 利用栈先进后出的特质,就可以保证性能的情况下输出不改变结构的倒序链表
 * @date: 2021/12/19 13:48
 * @param
 * @return: void
 */
public static void showreverseList(HeroNode node) {
    if (node.next == null) {
        return;
    }
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = node.next;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

课后练习

/**
     * @author 冷环渊 Doomwatcher
     * @context: 合并两个链表 并且有序
     * @date: 2021/12/19 14:15
     * @param list1
     * @param list2
     * @return: com.hyc.DataStructure.LinkedList.SingleLinkedlist
     */
    public static HeroNode mergeList(HeroNode list1, HeroNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        HeroNode head = new HeroNode(0, "", "");
        HeroNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.No < list2.No) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (list1 == null) {
            temp.next = list2;
        }
        if (list2 == null) {
            temp.next = list1;
        }
        return head.next;
    }

双向链表

双向链表应用实例,双向链表的操作分析和实现

管理单向链表的缺点分析:

  1. 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
  2. 向链表不能自我删除,需要靠辅助节点  ,而双向链表,则可以自我删除,所以前面我们单链表删除  时节点,总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
  3. 分析了双向链表如何完成遍历,添加,修改和删除的思路

双向链表实现思路

分析  双向链表的遍历,添加,修改,删除的操作思路===》代码实现

  1. 遍历 方和 单链表一样,只是可以向前,也可以向后查找
  2. 添加 (默认添加到双向链表的最后)
  1. (1)  先找到双向链表的最后这个节点
  2. (2) temp.next =  newHeroNode
  1. newHeroNode.pre = temp;
  2. 修改 思路和  原来的单向链表一样.  4)  删除
    (1) 因为是双向链表,因此,我们可以实现自我删除某个节点
    (2)  直接找到要删除的这个节点,比如 temp
    (3)  temp.pre.next  = temp.next
    (4) temp.next.pre = temp.pre;

实现链表节点

/**
 * 双向链表要用的节点
 * */
class ListNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个节点
    public ListNode next;
    //上一个节点
    public ListNode pre;
    public ListNode(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 + '\'' +
                '}';
    }
}

双向链表实现

class DoubleLinkedList {
    //创建一个头结点
    ListNode head = new ListNode(0, "", "");
    public ListNode getHead() {
        return head;
    }
    public void setHead(ListNode head) {
        this.head = head;
    }
    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }
    //加入双向链表
    public void add(ListNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //指向下一个节点
        temp.next = node;
        //指向上一个节点
        node.pre = temp;
    }
    //修改双向链表,和单向链表基本一致不需要过多的修改
    //修改节点信息
    public void updateNode(ListNode newlistnode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改,我用 temp 来指向头结点
        ListNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newlistnode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newlistnode.NickName;
            temp.Name = newlistnode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newlistnode.No);
        }
    }
    /*
     * 双向链表删除
     * 对于双向链表来说就不需要找到上一个节点来删除了,
     * 可以找到自己删除
     * */
    public void DeleteNode(int no) {
        if (head.next == null) {
            System.out.println("链表为空 不需要删除");
            return;
        }
        ListNode temp = head.next;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除,这里我们只需要指向空 GC会回收
            //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了
            /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/
            temp.pre.next = temp.next;
            /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点,相当于向前的pre 直接快过当前的节点指向上一个
             * 如果当前节点是最后一节点,就不执行后面这个将下一个节点的指向更改,不然会出现空指针
             * */
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
            /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
}

总结

双向链表在之前的基础上

  1. 对比单向链表 双向链表可以自己删除,
  2. 双线链表正反遍历更加的容易

环形链表

认识单向环形链表

这里我们以单向环形链表为例子

就是我们最后一个节点的next域指向头结点,形成闭环

引用场景以及问题

Josephu(约瑟夫、约瑟夫环)  问题

Josephu 问题为:设编号为 1,2,… n 的 n  个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数  到 m 的那个人出列,它的下一位又从  1 开始报数,数到 m  的那个人又出列,依次类推,直到所有人出列为止,由

此产生一个出队编号的序列。

思路提示:

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

Josephu 问题解题思路

认识约瑟夫问题,以及我们想要实现的场景,

  1. 编写实现 单向环形链表
  2. 约瑟夫问题的要求 根据区间报数 报数的小孩出列
  3. coding 出我们需要的需求

实现单向循环链表

思路

大体上和我们的单向链表有雷同的地方,区别在于:

  1. 我们需要在创建链表的时候将尾结点的最后一个指向头结点,这也就意味着我们需要有至少两个指针来记录头尾节点。
  2. 遍历的方式也要有些许的变化,结束循环的条件从head.next = null改变成CurBoy.next(指向尾部节点的指针) = first;最后为头节点的时候遍历为第二个

我们简单的先创建一个实现链表需要的节点对象

约瑟夫问题环形链表的节点

//环形链表 约瑟夫问题 节点
class Boy {
    private int No;
    private Boy Next;
    public Boy(int no) {
        this.No = no;
    }
    public int getNo() {
        return No;
    }
    public void setNo(int no) {
        No = no;
    }
    public Boy getNext() {
        return Next;
    }
    public void setNext(Boy next) {
        Next = next;
    }
}

创建环形链表对象实现生成链表和遍历链表,以及解决约瑟夫问题的方(具体的实现思路见代码注释)

// 环形单向链表
class CircleSingleLinkeList {
    Boy first = null;
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 一个环形链表  参数是这个链表有多少节点
     * @date: 2021/12/21 15:47
     * @param nums
     * @return: void
     */
    public void CreateListNode(int nums) {
        if (nums < 1) {
            System.out.println("无法开始游戏,因为链表小于最小的游戏节点数量");
            return;
        }
        // 创建一个 辅助之间用于遍历和指向节点
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            //如果只有一个节点的话 也可以生成环形链表
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;//将辅助指针指向链表的第一个节点 形成闭环
            } else {
                //    如果不是一个的话就生成多个节点
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    public void showListBoy() {
        if (first == null) {
            System.out.println("链表为空,不能遍历");
            return;
        }
        //   frist 节点不能移动 我们创建一个指针
        Boy curboy = first;
        while (true) {
            System.out.printf("小孩的编号是: %d \n", curboy.getNo());
            // 说明已经遍历完毕
            if (curboy.getNext() == first) {
                break;
            }
            //后移 curboy
            curboy = curboy.getNext();
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 这里我们以小孩做游戏来解决约瑟夫问题,
     * @date: 2021/12/22 21:16
     * @param nums 一共有多少个小孩
     * @param start 从那个小孩开始报数
     * @param index 每隔几个小孩报数一次
     * @return: void
     */
    public void JosephuFunc(int nums, int start, int index) {
        if (first == null || start < 1 || start > nums) {
            System.out.println("参数不对,请重新输入参数");
            return;
        }
        Boy helper = first;
        //将 helper遍历到最后一个节点
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        // 小孩子 报数之前,要遍历指针到从start开始的小孩的节点
        for (int i = 0; i < start - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数的时候 让 first和helper 同时移动m-1次 然后出圈
        //这里循环操作 知道圈中的一个节点
        while (true) {
            //说明列表只有一个节点
            if (helper == first) {
                break;
            }
            //循环之后将 指针后移
            for (int i = 0; i < index - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //    这个时候 first选中的节点就是要出圈的小孩
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            //出圈操作
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后剩下的小孩 %d \n", first.getNo());
    }
}

实现结果


Java数据结构与算法-java数据结构与算法(三)https://developer.aliyun.com/article/1469491

目录
相关文章
|
4天前
|
存储 算法 Java
【Java高阶数据结构】并查集-最小生成树(下)
【Java高阶数据结构】并查集-最小生成树
11 3
|
4天前
|
存储 算法 Java
【Java高阶数据结构】并查集-最小生成树(上)
【Java高阶数据结构】并查集-最小生成树(上)
11 2
|
4天前
|
算法 Java
【Java高阶数据结构】图-图的表示与遍历(下)
【Java高阶数据结构】图-图的表示与遍历
13 1
|
4天前
|
算法 安全 Java
性能工具之 JMeter 自定义 Java Sampler 支持国密 SM2 算法
【4月更文挑战第28天】性能工具之 JMeter 自定义 Java Sampler 支持国密 SM2 算法
32 1
性能工具之 JMeter 自定义 Java Sampler 支持国密 SM2 算法
|
2天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
2天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
|
4天前
|
存储 算法 Java
Java 数据结构
5月更文挑战第9天
|
4天前
|
存储 算法 搜索推荐
【Java高阶数据结构】图补充-拓扑排序
【Java高阶数据结构】图补充-拓扑排序
7 1
|
4天前
|
算法 Java
【Java高阶数据结构】图的最短路径问题(下)
【Java高阶数据结构】图的最短路径问题
6 1
|
4天前
|
算法 Java
【Java高阶数据结构】图的最短路径问题(上)
【Java高阶数据结构】图的最短路径问题
6 1