• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

Linked List 单向链表

开发技术 开发技术 3周前 (09-12) 24次浏览

Linked List

链表的理解

Linked List 单向链表

小结

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

单向链表

添加

添加到最后
  1. 找到链表的最后一个节点[通过节点的next == null]
  2. 将最后这个节点的next指向新的节点
//初始化一个头结点,里面什么都不放
    HeroNode head = new HeroNode(0, "", "");

    /**
     * 向链表中添加一个节点
     * 不考虑编号顺序
     */
    public void add(HeroNode heroNode) {
        //因为头节点是不能动的,使用中间变量temp来保存头节点
        HeroNode temp = head;
        //遍历节点,找到最后一个节点【通过最后一个节点next指向为 null】
        while (true) {
            if (temp.next == null) {
                //找到最后一个节点
                break;
            }
            //没有找到就将temp后移一个
            temp = temp.next;
        }
        // 当循环退出的时候temp就指向节点的最后一个
        temp.next = heroNode;
    }
考虑编号顺序添加
  1. 找到新添加节点的位置,通过辅助变量(temp)[遍历找到新节点的位置]

  2. 新的节点.next = temp.next

  3. temp.next = 新的节点

    Linked List 单向链表

/**
     * 考虑排序编号添加
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为头节点是不能动的,使用辅助变量temp寻找位置
        HeroNode temp = head;

        //用来代表当前添加的节点的编号是否存在,默认false不存在
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                //当前temp为链表最后一个
                break;
            }
            if (temp.next.no > heroNode.no) {
                //找到需要添加的位置,就在temp后面添加
                break;
            } else if (temp.next.no == heroNode.no) {
                //需要添加的节点已经存在
                flag = true;
                break;
            }
            //三个条件不成立  temp后移
            temp = temp.next;
        }
        if (flag) {
            //不能添加,编号存在
            System.out.printf("当前添加的英雄编号 %d 已经存在, 不能添加n", heroNode.no);
        } else {
            //在temp后面进行添加
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

修改

  • 使用temp.no == newHeroNode.no判断是否为需要修改的节点
/**
     * 更新节点
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //因为头节点是不能动的,使用中间变量temp来保存头节点
        HeroNode temp = head;
        boolean flag = false;   //用来表示链表中是否存在需要修改的节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;   //temp后移
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.printf("没有找到编号为:%d 节点", newHeroNode.no);
        }
    }

删除

  1. 找到需要删除的节点的前一个节点temp
  2. temp.next = temp.next.next
  3. 被删除的节点 将不会有其他引用指向,会被垃圾回收机制回收
 /**
     * 删除节点
     *
     * @param no
     */
    public void del(int no) {
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //因为头节点是不能动的,使用中间变量temp来保存头节点
        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);
        }

    }

dataStructures: gitee

dataStructures: github


程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2020/09/linked-list-%e5%8d%95%e5%90%91%e9%93%be%e8%a1%a8/
喜欢 (0)