栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构与算法-线性结构-单链表 SingleLinkedList

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构与算法-线性结构-单链表 SingleLinkedList

单链表数据格式 : 数据 +指针  指针是指向下一个元素的 地址

增加(在最后节点增加):直接遍历

增加(根据 节点序号  去添加,有序[升序]):遍历 找到 插入位置的上节点 因为需要用到上节点的指针域    temp.next.getno()> heroNode.getno() [ parameter ]  从而找到了 上节点 修改上节点的下指针与参数节点的下指针域就行了
删: 遍历 找到与 parameterNode no匹配的即可  也是需要找到上节点  修改指针 

改:遍历 找到parameterNode no 匹配 直接修改

查:逆向查询 需要 知道当前节点长度   指针后移次数(cur.length  - lastIndex)

反转 :思路1:

        借助辅助节点  每次 都将被反转链表的下一个节点 放入辅助节点的 第一位

        核心:两个辅助节点 一个装  被反转链表下一个(不然会断) 一个是辅助头节点 

        最后将被反转链表指向 辅助节点的下一个节点 完成反转

             思路2:栈

栈:stack   add入栈 pop出栈

package com.qf.linkedlistdemo;

//单向链表

import java.util.Stack;


public class SingleLinkedList {
    //初始化头节点 ,不存放数据, 成员变量都有默认初始化值
    static final HeroNode head = new HeroNode(0, "", "");

    
    public void addNode(HeroNode heroNode) {
        //辅助节点
        HeroNode temp = head;
        //遍历链表
        while (true) {
            //遍历到最后
            if (temp.getNext() == null) {
                break;
            }
            //如果没有 遍历到最后 temp 后移
            temp = temp.getNext();

        }
        //退出while 节点已经是最后一个了   添加
        temp.setNext(heroNode);
    }


    
    public void addNodeByOrder(HeroNode heroNode) {
        //因为头节点不能动 所以 需要 一个辅助节点 来帮助 找到添加的位置
        //并且 因为是单链表 加入节点 所以
        // 必须 要找到 添加位置 的前一个节点 不然没法加入 因为需要指针

        HeroNode temp = head;
        boolean flag = false; //编号是否存在 默认不存在

        //遍历链表
        while (true) {
            //遍历到最后一个 ,说明要插入的地方 在最后一个
            if (temp.getNext() == null) {
                break;
            }
            // 找到要插入的位置  temp  不能 与 前面的一个比较 要跟后面的比较 这样才能找到 temp(插入位置的前一个介节点)
            //后面的节点 肯定 要比插入的节点大
            if (temp.getNext().getNo() > heroNode.getNo()) {
                break;
            }
            if (temp.getNext().getNo() == heroNode.getNo()) {
                //改变flag 值
                flag = true;
                break;
            }
            //后移
            temp = temp.getNext();
        }

        //证明 已经遍历完毕 判断 flag 是否改变
        if (flag) { //存在
            System.out.println("节点已存在");
        } else {
            //修改 next 指向
            heroNode.setNext(temp.getNext());
            temp.setNext(heroNode);
        }

    }

    
    public void updateByNodeNO(HeroNode heroNode) {
        if (head.getNext() == null) {
            System.out.println("空链表");
            //表示当前链表为空 直接返回即可
            return;
        }
        //借助 辅助 变量
        HeroNode temp = head.getNext();
        // 定义表示 是否找到 后续需要根据 其进行修改
        boolean flag = false;

        //变量 当前 链表
        while (true) {

            //表示最后一个元素
            if (temp == null) {
                break; //遍历完
            }
            //表示找到了
            if (temp.getNo() == heroNode.getNo()) {
                flag = true;
                break;
            }
            //后移
            temp = temp.getNext();
        }
        //根据 flag 去判断是否找到
        if (flag) { //找到了
            temp.setName(heroNode.getName());
            temp.setNickName(heroNode.getNickName());
        } else {
            System.out.println("未找到 你所指定的节点" + heroNode.getNo());
        }

    }

    
    public void deleteByNodeNo(int no) {
        //空链表
        if (head.getNext() == null) {
            System.out.println("这是一个空链表");
            return;
        }
        //声明辅助变量 ,头节点 可以忽略
        HeroNode temp = head.getNext();
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//表示到最后一个
            }
            if (temp.getNext().getNo() == no) {
                //表示找到 该节点的 上一个节点
                flag = true;
                break;
            }
            //后移
            temp = temp.getNext();
        }
        //判断 true 就是 找到了该节点的上一个节点
        if (flag) {
            //修改节点指向
            temp.setNext(temp.getNext().getNext());
        } else {
            System.out.println("未找到要删除的 节点" + no);
        }

    }

    
    public void showSingleLinkedList() {

        //判断链表是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空");
            return;
        }

        //遍历 借助 辅助接点 节点就不遍历了
        HeroNode temp = head.getNext();
        while (true) {
            //说明到最后了 ,不用next  如果用了 下一个节点 为空的话 就会产生最后一个数据 不能正常打印
            //主要是 当前链表也需要做操作 所以使用temp
            if (temp == null) {
                break;
            }
            //不是最后一个节点
            System.out.println(temp);
            //后移
            temp = temp.getNext();
        }
    }

    
    public static int getLength() {
        //链表为空
        if (head.getNext() == null) {
            return 0;
        }
        //声明变量
        int length = 0;
        //借助辅助变量 去遍历
        HeroNode cur = head.getNext();
        while (cur != null) {
            length++;
            cur = cur.getNext();
        }
        return length;
    }

    
    public static HeroNode findHeroNodeByLastIndex(int lastIndex) {
        //判断 当前链表是否为空
        if (head.getNext() == null) {
            return null;
        }
        //检验输入数据是否合法
        if (lastIndex < 0 || lastIndex > getLength()) {
            throw new RuntimeException("输入数据不合法");
        }
        //当前指针指向第一个元素
        HeroNode cur = head.getNext();
        //四个数 倒数 第二个  指针需要移动 2 次 类推
        for (int i = 0; i < getLength() - lastIndex; i++) {
            cur = cur.getNext();
        }

        return cur;

    }

    
    public void reverseCurrentHeroNode() {
        //判断是否为空 或者当前链表只有一个单个数据
        if (head.getNext() == null || head.getNext().getNext() == null) {
            return;
        }
        //定义辅助变量
        HeroNode cur = head.getNext();//第一个元素
        HeroNode next;
        //定义反转 单链表的头节点
        HeroNode reverseHead = new HeroNode(0, "", "");

        // 遍历原来的链表 每遍历一个 放在新链表的最前端
        while (cur != null) {
            next = cur.getNext();//保存当前节点的下一个元素 因为后面要用 不然找不到了
            cur.setNext(reverseHead.getNext());//将 当前元素的下一个 元素 指向新 链表的头
            reverseHead.setNext(cur); //把当前已经拿到的对象 放在 新的单链表的首部
            cur = next;//后移 (之前保存的 下一个元素直接赋值 )
        }
        head.setNext(reverseHead.getNext());
    }

    
    public void reverseCurrentPrintHeroNode(HeroNode headNode) {
        //判断是否为空
        if (headNode.getNext() == null) {
            return;//为空
        }

        //不为空
        //声明空间
        Stack heroNodeStack = new Stack<>();
        HeroNode cur = headNode.getNext();
        while (cur != null) {
            //压栈
            heroNodeStack.add(cur);
            cur = cur.getNext();
        }
        //出栈
        while (heroNodeStack.size() > 0) {
            //出栈
            System.out.println(heroNodeStack.pop());
        }


    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950722.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号