Java中双链表的操作

绝地灬酷狼 2023-10-05 01:53 10阅读 0赞

#### Java中双链表的操作 ####

1.  双链表根据内容添加结点
2.  双链表根据内容删除结点
3.  双链表根据内容修改（新内容替换旧内容）
4.  双链表根据内容查找结点索引 索引从0开始
5.  根据下标添加结点内容
6.  根据下标删除
7.  根据下标查找值
8.  根据下标修改值

public class DBNode {
        
        // 双向链表和单链表
        // 三个域
    
        // 值域
        String value;
        // 前结点
        DBNode pre;
        // 后结点
        DBNode next;
    
        // 构造方法
        public DBNode(String value, DBNode pre, DBNode next) {
        
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    
        // 重写
    
        @Override
        public String toString() {
        
            return "{" +
                    "value='" + value + '\'' +
                    ", next=" + next +
                    '}';
        }
    }

public class MyDBLinked {
        
        // 头结点
        private DBNode top;
        // 尾结点
        private DBNode end;
        private int size;
    
        /**
         * 双链表根据内容添加结点
         *
         * @param str 添加内容
         *
         * @return 添加成功返回true，失败则返回false
         */
    
        public boolean add(String str) {
        
            // 判断原本的链表是不是空链表
            if (top == null) {
        
                // 原本的链表为空
                top = new DBNode(str, null, null);
                // 此时链表只有一个结点，尾结点头结点均为同一个结点；
                end = top;
                // 链表长度加一
                size++;
                return true;
            }
            // 程序走到这里就代表原本的链表不为空
            // new一个链表结点，新结点的前驱结点为end;
            DBNode node = new DBNode(str, end, null);
            // 在双链表的末尾加上node结点
            end.next = node;
            end = node;
            size++;
            return true;
        }
    
        /**
         * 双链表根据内容删除结点
         *
         * @param str 需要删除的内容
         *
         * @return 返回删除结点的内容
         */
        public String remove(String str) {
        
            // 判断双链表是否为空
            if (size == 0) {
        
                // 为空则抛出异常
                throw new RuntimeException("双链表为空");
            }
            // 判断删除的结点是否为头结点
            if (top.value.equals(str)) {
        
                // 删除头结点
                top = top.next;
                // 如果双链表原本就一个结点
                if (size == 1) {
        
                    end = null;
                } else {
        
                    // 只有原本的链表多于一个结点的时候，才需要把后移的top的前指向去除
                    top.pre = null;
                }
                size--;
                return str;
            }
            // 删除的不是头结点
            DBNode mid = top;
            // 对结点进行遍历判断,mid=top  即mid为头结点
            // mid.next为当前结点
            while (mid.next != null && !mid.next.value.equals(str)) {
        
                mid = mid.next;
            }
            // 程序走到这里，说明结点为尾结点，或者是符合删除要求的结点,或者是未找到符合删除条件的结点
    
            if (mid.next == null) {
        
                // 未找到结点
                return null;
            }
            // 单独对尾结点进行删除处理
            // mid.next.next即为当前结点的下一个结点
            // mid.next.next == null 即当前结点mid.next为尾结点
            if (mid.next.next == null) {
        
                //即要删除的结点为尾结点
                // 先记录尾结点旧值
                String oldValue = mid.next.value;
                // 把当前的尾结点置为null
                mid.next = null;
                // 当前尾结点mid.next已被置为null，所以需要把尾结点标记迁移
                end = mid;
                // 整体size-1;
                size--;
                // 返回删除的值
                return oldValue;
            }
            // 程序走到这，说明mid.next一定就是被找到的符合删除条件的结点
            // mid则为符合删除条件结点的前一个结点
    
            // 要删除的目标结点
            DBNode targetNode = mid.next;
            // 要删除结点的前驱结点的后继结点=要删除结点的后继结点
            targetNode.pre.next = targetNode.next;
            // 要删除结点的后继结点的前驱结点=要删除结点的前驱结点
            targetNode.next.pre = targetNode.pre;
    
            // 到此为止，结点删除成功
            size--;
            return targetNode.value;
        }
    
        /**
         * 双链表根据内容修改（新内容替换旧内容）
         *
         * @param oldStr 旧结点内的内容
         * @param newStr 修改之后的内容
         *
         * @return 修改成功返回true，失败则返回false
         */
        public boolean set(String oldStr, String newStr) {
        
            // 参数校验
            // 判断双链表是否为空
            if (top == null) {
        
                throw new RuntimeException("Linked is null");
            }
            // 声明遍历链表时的记录结点mid
            DBNode mid = top;
            //对结点进行遍历，如果结点不为空，即不为尾结点
            //或结点不符合替换条件，就继续向后遍历链表
            while (mid != null && !mid.value.equals(oldStr)) {
        
                mid = mid.next;
            }
            // 程序走到这里，说明此时的结点为以下两种情况之一
            // 1，mid为null，即未找到符合修改条件的结点
            // 2，结点符合修改条件
    
            // 先对mid为null，即未找到符合修改条件的结点   进行判断
            if (mid == null) {
        
                // 未找到符合修改条件的结点
                return false;
            }
            // 此时只剩下结点符合修改条件这一种情况，直接替换修改即可
            mid.value = newStr;
            return true;
        }
    
        /**
         * 双链表根据内容查找结点索引 索引从0开始
         *
         * @return 返回结点的索引
         */
        public int getIndex(String str) {
        
            //判断链表是否为空
            if (top == null) {
        
                throw new RuntimeException("Linked is null");
            }
            // 记录结点
            DBNode mid = top;
            //定义变量，记录索引值
            int count = 0;
            // 对结点进行遍历，直到查到尾结点或者找到符合要求的结点
            while (mid != null && !mid.value.equals(str)) {
        
                mid = mid.next;
                count++;
            }
            // 未找到符合要求的结点
            if (mid == null) {
        
    
                return -1;
            }
            // 程序走到这里，说明已经找到符合要求的结点，返回索引记录值
            return count;
    
        }
    
        /**
         * 根据下标添加结点内容
         *
         * @param index 添加元素位置
         * @param str   添加内容
         *
         * @return 添加成功返回true，失败则返回false
         */
        public boolean addByIndex(int index, String str) {
        
            // 校验需要添加的位置是否合法
            if (index > size || index < 0) {
        
                throw new RuntimeException("index is Illegal");
            }
            // 参数合法，继续执行
    
            // 创建需要添加的结点的对象
            DBNode dbNode = new DBNode(str, null, null);
            // 需要添加的结点是头结点，即index为0，size=0
            if (index == 0) {
        
    
                // 新结点的下一个结点指向原结点的头结点
                dbNode.next = top;
                if (top != null) {
        
                    // 如果原链表不为空，原结点的前驱结点指向新节点
                    top.pre = dbNode;
                } else {
        
                    // 原链表为空，尾结点指向新节点
                    end = dbNode;
                }
                // 把头结点标记前移
                top = dbNode;
                // 结点长度+1
                size++;
                return true;
            }
            // 程序既然执行到这里，size就不会为0
    
            // 如果需要添加的结点为尾结点，即index=size
            if (index == size) {
        
                // 新结点的前驱指向原旧结点
                dbNode.pre = end;
                // 原尾结点的后继指向该添加到尾部的结点
                end.next = dbNode;
                // 尾结点后移
                end = dbNode;
                size++;
                return true;
            }
            // 程序走到这里就说明需要添加的位置在头结点和尾结点之间
    
            // mid用来标记要添加位置的前一个位置
            DBNode mid = top;
            // 声明count记录链表位置
            int count = 1;
            // 对链表进行遍历
            while (index != count) {
        
                mid = mid.next;
                count++;
            }
            // 当index==count时，就会跳出循环，即满足添加条件
            // 把新结点添加到mid和mid.next中间
            dbNode.next = mid.next;
            dbNode.pre = mid;
            dbNode.next.pre = dbNode;
            mid.next = dbNode;
            size++;
            return true;
        }
    
        /**
         * 根据索引删除
         *
         * @param index 需要删除位置的索引
         *
         * @return 返回被删除的内容
         */
        public String removeByIndex(int index) {
        
            // 对链表进行参数校验
            if (top == null) {
        
                throw new RuntimeException("linked is null");
            }
            // 校验要查找的索引是否合法(索引从0开始)
            if (index < 0 || index > size - 1) {
        
                throw new RuntimeException("param is Illegal");
            }
            //为提高查找效率，获取元素所属的范围
            int midIndex = size / 2;
            // 判断需要查找元素所属的范围
            // 声明一个空结点
            DBNode mid = null;
            if (midIndex > index) {
        
                // 要删除的元素在链表的前半部分
                // 头结点
                mid = top;
                int count = 0;
                while (count != index) {
        
                    count++;
                    mid = mid.next;
                }
            } else {
        
                // 要删除的元素在后半部分
                mid = end;
                int count = size - 1;
                while (count != index) {
        
                    count--;
                    mid = mid.pre;
                }
            }
                // mid 就是要删除的结点
                // 如果mid是头结点
                if (mid == top) {
        
                    // 使头结点后移
                    top = top.next;
                    // 如果后移之后结点变为null
                    if (top == null) {
        
                        // 代表原链表仅有一个结点
                        end = null;
                    } else {
        
                        // 代表链表不仅仅只有一个结点
                        top.pre = null;
                    }
                    size--;
                    return mid.value;
                }
                // 如果删除的是尾结点
                if (mid == end) {
        
                    end = end.pre;
                    // 链表和原尾结点断开连接
                    end.next = null;
                    size--;
                    return mid.value;
                }
                // 删除的既不是头结点，也不是尾结点
                mid.pre.next = mid.next;
                mid.next.pre = mid.pre;
                size--;
                return mid.value;
            }
    
    
        /**
         * 根据下标查找值
         * @param index 提供的下标
         * @return 返回查找到的值
         */
        public String get(int index){
        
            // 参数效验
            if (top == null) {
        
                throw new IllegalArgumentException("mylinked is null");
            }
            if (index < 0 || index > size - 1) {
        
                throw new IllegalArgumentException("param is Illegal");
            }
    
    
            // 获取中间位置下标
            int midIndex = size/2;
            DBNode mid = null;
            if (index < midIndex){
        
                // 查找值在前半部分
                mid = top;
                int tag = 0;
    
                // 从头结点向后遍历
                while (tag != index){
        
                    mid = mid.next;
                    tag++;
                }
            } else {
        
                // 查找值在后半部分
                mid = end;
                int tag = size - 1;
                // 从尾结点向前遍历
                while (tag != index){
        
                    mid = mid.pre;
                    tag--;
                }
            }
            return mid.value;
        }
    
    
    
    
        /**
         * 根据下标修改值
         * @param index 需要修改的下标位置
         * @param str  修改的新值
         * @return 被覆盖的旧值
         */
        public String set(int index, String str){
        
            // 参数效验
            if (top == null) {
        
                throw new IllegalArgumentException("mylinked is null");
            }
            if (index < 0 || index > size - 1) {
        
                throw new IllegalArgumentException("param is Illegal");
            }
    
            // 获取中间位置下标
            int midIndex = size/2;
            DBNode mid = null;
            if (index < midIndex){
        
                // 查找值在前半部分
                mid = top;
                int tag = 0;
    
                // 从头结点向后遍历
                while (tag != index){
        
                    mid = mid.next;
                    tag++;
                }
            } else {
        
                // 查找值在后半部分
                mid = end;
                int tag = size - 1;
                // 从尾结点向前遍历
                while (tag != index){
        
                    mid = mid.pre;
                    tag--;
                }
            }
    
            // 保存旧值
            String oldValue = mid.value;
            // 替换新值
            mid.value = str;
    
            return oldValue;
        }
    
        @Override
        public String toString() {
        
            return "DemoLinked1{" +
                    "top=" + top +
                    ", end=" + end +
                    ", size=" + size +
                    '}';
        }
    }