Java中双链表的操作-蒲公英云

Java中双链表的操作

双链表根据内容添加结点
双链表根据内容删除结点
双链表根据内容修改（新内容替换旧内容）
双链表根据内容查找结点索引索引从0开始
根据下标添加结点内容
根据下标删除
根据下标查找值

根据下标修改值

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 +
                '}';
    }
}