小胡博客

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

  package com.xiaohu.suanfa.linkList;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author 小胡哥哥
 * NO BB show your code
 * 单向链表
 * 模拟用单向链表实现水浒传英雄的增删改查
 * 每一个HeroNode代表一个英雄
 * 建议之后画个图
 */
public class SimpleLinkListDemo1 {
    //定义一个heroNode

    class HeroNode {
        //编号id
        private int nodeId;
        //姓名
        private String name;
        //昵称
        private String nickName;
        //下一个对象的指针
        private HeroNode next;

        //构造方法
        public HeroNode(int nodeId, String name, String nickName) {
            this.nodeId = nodeId;
            this.name = name;
            this.nickName = nickName;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "nodeId=" + nodeId +
                    ", name='" + name + '\'' +
                    ", nickName='" + nickName + '\'' +

                    '}';
        }
    }

    /**
     * 用来管理英雄的操作行为
     */
    class LinkListManger {
        //链表大小,
        private AtomicInteger size = new AtomicInteger();

        public LinkListManger(AtomicInteger size) {
            this.size = size;
        }

        public LinkListManger() {

        }

        //先定义一个头结点，只是占位置，不让它存放数据
        HeroNode head = new HeroNode(0, "", "");


        /**
         * 添加英雄结点
         *
         * @param heroNode
         */
        HeroNode temp = head;

        /**
         * 无排序
         *
         * @param heroNode
         */
        public void addNode(HeroNode heroNode) {

            //添加结点,  头结点不能动，定义一个辅助指针
            //刚开始让temp指向head结点，从head结点位置开始遍历
            while (true) {
                //代表temp辅助指针遍历到最后一个元素
                if (temp.next == null) {
                    //则将要添加的元素插入到这位置(尾插)
                    temp.next = heroNode;
                    size.incrementAndGet();
                    temp = temp.next;
                    System.out.println("添加成功");
                    break;
                }
            }
        }

        /**
         * 添加元素按编号排序
         *
         * @param heroNode
         */
        public void addNodeByOrder(HeroNode heroNode) {
            //标记是否为重复元素，既链表存在相同的nodeId
            boolean flag = false;
            HeroNode temp = head;
            while (true) {
                //代表已经遍历到链表尾部
                if (temp.next == null) {
                    break;
                }
                //非法的id和如果传入的id大于了temp结点后的id都为添加失败
                //正确的元素添加位置为 temp和链表结点之间
                if (!isNodeId(heroNode.nodeId) && heroNode.nodeId > temp.next.nodeId) {
                    throw new RuntimeException("添加失败，编号有误");

                }
                // 进行排序,找到添加的正确位置
                if (temp.next.nodeId > heroNode.nodeId) {
                    break;
                }
                //添加重复的元素
                if (temp.next.nodeId == heroNode.nodeId) {
                    flag = true;
                    break;
                }

                //都不满足的话，让temp后移
                temp = temp.next;
            }
            if (flag) {
                System.out.println("链表元素编号已存在，添加失败");
                return;
            }

            //代表条件成立,则temp.next.id>heroNode.nodeId ,找到位置
            //添加元素 新元素的next指针指向原来的temp.next
            heroNode.next = temp.next;
            //之后再让temp下一位元素指向要添加的元素
            temp.next = heroNode;
            size.incrementAndGet();
            System.out.println("添加成功");
        }

        /**
         * 获得英雄结点
         *
         * @return
         */
        public HeroNode getNode(int heroId) {
            HeroNode temp = head.next;
            if (!isNodeId(heroId)) {
                throw new RuntimeException("数组索引越界,id有误");
            }
            HeroNode heroNode;
            while (true) {
                if (temp.nodeId == heroId) {
                    heroNode = temp;

                    //size.decrementAndGet();

                    return heroNode;

                }
                //跳出if判断，代表id不符合，后移一位
                temp = temp.next;

            }
        }

        /**
         * 修改
         *
         * @param heroNode
         */
        public void setHead(HeroNode heroNode) {
            HeroNode temp = head;
            int nodeId = heroNode.nodeId;

            if (!isNodeId(nodeId)) {
                throw new RuntimeException("数组索引越界,id有误");
            }
            while (true) {
                if (temp.next == null && temp.next.nodeId != nodeId) {
                    throw new RuntimeException("查无此人");

                }
                //id相同，代表找到要修改的位置
                if (temp.next.nodeId == nodeId) {
                    //找到了要修改的位置
                    //设置新的值
                    temp.next.name = heroNode.name;
                    temp.next.nodeId = nodeId;
                    temp.next.nickName = heroNode.nickName;
                    //将原先的值的next指向新值的next，重新串联起来
                    heroNode.next = temp.next.next;
                    // heroNode.next = temp.next.next;
                    System.out.println("修改成功");
                    break;
                }
                //没找到则后移
                temp = temp.next;

            }
        }

        /**
         * 删除
         *
         * @param nodeId
         */
        public void deleteNode(int nodeId) {
            HeroNode temp = head;

            while (true) {
                if (temp.next == null) {
                    System.out.println("链表为空");
                }
                if (temp.next == null && temp.next.nodeId != nodeId) {
                    throw new RuntimeException("查无此人");

                }

               //找到了要删除的结点
                if (temp.next.nodeId == nodeId) {
                    //临时结点
                     HeroNode node1 = temp.next;
                    //将要删除的结点设置为null,方便gc
                    temp.next = null;
                    //将temp.next直接指向要删除的元素的next结点
                    temp.next = node1.next;

                    size.decrementAndGet();
                    System.out.println("删除成功");
                    //将临时结点显示设置为null,垃圾回收
                    node1 = null ;
                    break;
                }
                
                  //不满足条件后移
                temp = temp.next;
            }
        }
          /**
          遍历展示链表
          */
        public void showListNode() {
            if (head.next == null) {
                System.out.println("链表为空");
            }
            //因为跳出判断了head.next不为空，所以肯定至少有1个元素
            HeroNode tmp = head.next;
            while (true) {
                //判断是否到了最后
                if (tmp == null) {
                    break;
                }
                System.out.println("元素为:" + tmp);
                //temp进行后移，不后移永远都是输出第一个
                tmp = tmp.next;
            }
        }

        /**
         * 判断nodeId是否符合
         *
         * @param index
         * @return
         */
        public boolean isNodeId(int index) {
            //输入的英雄编号从1开始，所以索引也得从+1
            return index >= 0 && index <= size.get() + 1;
        }
    }

    public static void main(String[] args) {

        LinkListManger linkListManger = new SimpleLinkListDemo1().new LinkListManger();
        HeroNode heroNode1 = new SimpleLinkListDemo1().new HeroNode(1, "林冲1", "豹子头");
        HeroNode heroNode2 = new SimpleLinkListDemo1().new HeroNode(2, "林冲2", "豹子头");
        HeroNode heroNode3 = new SimpleLinkListDemo1().new HeroNode(3, "林冲3", "豹子头");
        HeroNode heroNode4 = new SimpleLinkListDemo1().new HeroNode(4, "林冲4", "豹子头");
        HeroNode heroNode5 = new SimpleLinkListDemo1().new HeroNode(2, "林冲5", "豹子头");
        linkListManger.addNodeByOrder(heroNode4);
        linkListManger.addNodeByOrder(heroNode3);
        linkListManger.addNodeByOrder(heroNode1);
        linkListManger.addNodeByOrder(heroNode2);
        //linkListManger.addNodeByOrder(heroNode5);
        System.out.println(linkListManger.size);
        System.out.println(linkListManger.getNode(1));
        System.out.println(linkListManger.getNode(2));
        System.out.println(linkListManger.getNode(3));
        //System.out.println(linkListManger.getNode(4));

        System.out.println("=============");
        linkListManger.setHead(heroNode5);
        System.out.println(linkListManger.getNode(2));
        linkListManger.showListNode();


        linkListManger.deleteNode(1);
        linkListManger.deleteNode(4);
        linkListManger.deleteNode(2);
        linkListManger.deleteNode(3);
        System.out.println(linkListManger.size);
        linkListManger.showListNode();
        //System.out.println(linkListManger.getNode(5));

    }


}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦