您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

线性表模拟双链表LinkedList实现(add/remove)操作

实现类

package day03;

/**
 * @Author yqq
 * @Date 2022/05/05 21:35
 * @Version 1.0
 * 模拟双链表
 */
public class DoubleLinkedList {
    /**
     * 用于保存双向链表首节点
     */
    private Node headNode;
    /**
     * 用于保存双向链表的尾结点
     */
    private Node lastNode;
    /**
     * 用于保存双向链表中节点的个数
     */
    private int size;

    /**
     * 获取双向链表中的个数
     * @return
     */
    public int size(){
        return this.size;
    }

    /**
     * 添加元素
     * @param element
     */
    public void add(Object element){
        //把需要添加的元素封装成一个节点对象
        Node node = new Node(element);
        //处理双向链表为空的情况
        if (headNode == null){
            //把node节点设置为头结点
            headNode = node;
            //把node节点设置为尾结点
            lastNode = node;
        }else {
            //设置lastNode的next值为node
            lastNode.next = node;
            //设置node的pre值为lastNode
            node.pre = lastNode;
            //设置node节点为双链表节点的尾结点
            lastNode = node;
        }
        //更新size的值
        size ++;
    }

    /**
     * 根据序号获得元素
     * @param index
     * @return
     */
    public Object get(int index){
        //判断序号是否合法,合法范围[0,size - 1]
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("序号不合法,index:" + index);
        //根据序号获得对应节点对象
        Node node = node(index);
        //获得并返回node节点数据值
        return node.data;
    }

    /**
     * 根据序号删除元素
     * @param index
     */
    public void remove(int index){
        //判断序号是否合理
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("序号不合法,index:" + index);
        //处理删除节点为首节点的情况
        if (index == 0){
            //获得删除节点的下一个节点
            Node nextNode = headNode.next;
            //设置删除节点的值为null(首节点)
            headNode.next = null;
            //判断首节点是否也是尾节点,如果是,则双链表删除后为空链表
            if (nextNode != null)
                //设置nextNode节点pre为null
                nextNode.pre = null;
            //设置nextNode为双链表的首节点
            headNode = nextNode;
        }
        //处理删除节点为尾节点的情况
        else if (index == size - 1){
            //获得删除节点的前一个节点
            Node preNode = lastNode.pre;
            //设置preNode的next为null
            preNode.next = null;
            //设置lastNode的pre为null
            lastNode.pre = null;
            //设置preNode为尾结点
            lastNode = preNode;
        }
        //处理删除节点为中间任何节点的情况
        else {
            //获得删除节点对象
            Node delNode = node(index);
            //获得删除节点的前一个节点
            Node preNode = delNode.pre;
            //获得删除节点的后一个节点
            Node nextNode = delNode.next;
            //设置删除节点的前一个节点指向删除节点的后一个节点
            preNode.next = nextNode;
            //设置删除节点的后一个节点指向删除节点的前一个节点
            nextNode.pre = preNode;
            //设置删除节点的next和pre为null
            delNode.pre = null;
            delNode.next = null;
        }
        //更新size的值
        size --;
    }

    /**
     * 根据序号插入元素
     * @param index
     * @param element
     */
    public void add(int index,Object element){
        //判断序号是否合法,序号合法范围[0,size]
        if (index < 0 || index > index)
            throw new IndexOutOfBoundsException("序号不合法,index:" + index);
        //把需要添加的数据封装成一个节点对象
        Node node = new Node(element);
        //处理插入节点在开头的情况
        if (index == 0){
            //设置node的next为headNode
            node.next = headNode;
            //设置headNode的preNode为node
            headNode.pre = node;
            //将node设置为双链表的首节点
            headNode = node;
        }
        //处理插入节点在末尾的情况
        else if (index == size){
            //插入原理与add方法一样
            add(element);
        }
        //处理插入节点在中间任意位置的情况
        else {
            //获得插入位置所对应的节点对象
            Node curNode = node(index);
            //获得插入位置节点的前一个节点
            Node preNode = curNode.pre;
            //设置node节点和preNode节点之间的连线
            preNode.next = node;
            node.pre = preNode;
            //设置node节点和curNode节点之间的连线
            node.next = curNode;
            curNode.pre = node;
        }
        //更新size的值
        size ++;
    }
    /**
     * 根据序号获得对应的节点对象
     * @param index
     * @return
     */
    private Node node(int index){
        //如果查找的节点在双链表的前半区,则从前往后查找
        if (index < size / 2){
            //定义一个临时节点,用于辅助双链表的遍历
            Node nextNode = headNode;
            //定义一个循环从前往后查找index所对应节点
            for (int i = 0; i < index; i++) {
                nextNode = nextNode.next;
            }
            //返回index对应的节点
            return nextNode;
        }
        //如果查找的节点在双链表的后半区,则从后往前查找
        else {
            //定义一个临时节点辅助双链表的遍历
            Node preNode = lastNode;
            //定义一个循环从后往前查找index对应节点对象
            for (int i = size - 1; i > index; i--) {
                //更新preNode的值
                preNode = preNode.pre;
            }
            //返回index对应的节点对象
            return preNode;
        }
    }
    /**
     * 节点类
     */
    private static class Node{
        /**
         * 用于保存节点中的数据
         */
        private Object data;
        /**
         * 用于保存上一个节点的地址值
         */
        private Node pre;
        /**
         * 用于保存下一个节点的地址值
         */
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }
}

测试类

package day03;

/**
 * @Author yqq
 * @Date 2022/05/05 22:31
 * @Version 1.0
 */
public class Test03 {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();
        list.add("11");
        list.add("22");
        list.add("33");
        //根据序号删除元素
//        list.remove(2);
        //根据序号插入元素
        list.add(3,"1");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
//        System.out.println(list.get(1));
    }
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进