作业及参考

作业及参考

用单向链表实现一个线性表

/**
 * 集合类:
 * 从使用者角度:  数据容器
 * 数据结构:  线性表
 * 底层结构:  链表
 */
public class MyLinkedList {

    private Node head ; // MyLinkedList底层链表的头元素
    private int size ; // 用来保存这个集合类中存储了多少个元素


    /**
     *  添加方法
     * @param str : 添加的内容
     * @return : 添加是否成功
     */
    public boolean add(String str){

        // 判断这个集合类是否为空
        if (isEmpty()){
            // 如果空, 让新添加的元素, 作为头结点
            head = new Node(str, null);
            size++;
            return true;
        }
        // 走到这, 原链表不空 --> 已经存储了一部分数据

        // 把这个元素添加的尾部
        // 首先, 获取尾结点
        Node mid = head;
        while (mid.next != null){
            mid = mid.next;
        }

        // 上述循环结束, mid是尾结点
        mid.next = new Node(str, null);
        size++;

        return true;
    }

    /**
     * 删除方法
     * @param str: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(String str){
        // 如果链表本身没有存储元素
        // if (isEmpty()) return false;
        if (isEmpty())throw new RuntimeException("list is empty");

        if (str == null){
           // 如果要删除的元素值是null, 可以用==比较
            if (str == head.value){
                // 判断要删除的是否是头结点, 如果是
                head = head.next;
                size--;
                return true;
            }
            // 要删除的不是头结点
            Node mid = head;// 定义一个遍历结点

            // mid之后还存在元素, 并且mid之后的这个元素中存储的value 和 str 不相等
            while (mid.next != null && mid.next.value != str){
                mid = mid.next;
            }

            // 上述循环有两个跳出条件
            // 1, mid.next == null,  意味着找到链表的尾部都没有找到这个要删除的值
            // 2, mid.next.valua == str , 意味着mid.next 存储的value, 就是要删除的value

            if (mid.next == null) return false;

            mid.next = mid.next.next;
            size--;

        }else {
            // 如果要删除的元素值不是null--> 普通的字符串, 用equals比较

            if (str.equals(head.value)){
                // 判断要删除的是否是头结点, 如果是
                head = head.next;
                size--;
                return true;
            }
            // 要删除的不是头结点
            Node mid = head;// 定义一个遍历结点

            // mid之后还存在元素, 并且mid之后的这个元素中存储的value 和 str 不相等
            while (mid.next != null && !str.equals(mid.next.value)){
                mid = mid.next;
            }

            // 上述循环有两个跳出条件
            // 1, mid.next == null,  意味着找到链表的尾部都没有找到这个要删除的值
            // 2, mid.next.valua == str , 意味着mid.next 存储的value, 就是要删除的value

            if (mid.next == null) return false;

            mid.next = mid.next.next;
            size--;
        }

        return true;
    }

    /**
     * 查找某个元素是否存在
     * @param str : 要查找的值
     * @return : 是否存在
     */
    public boolean contains(String str){
        // 如果链表本身没有存储元素
        if (isEmpty())throw new RuntimeException("list is empty");

        if (str == null){

            Node mid = head;// 定义一个遍历结点

            // mid不是null,  并且mid这个结点存储的元素也不是要查找的值 --> 向后遍历
            while (mid != null && mid.value != str){
                mid = mid.next;
            }

            // 两种跳出条件
            if (mid == null) return false;

        }else {
            Node mid = head;// 定义一个遍历结点

            // mid不是null,  并且mid这个结点存储的元素也不是要查找的值 --> 向后遍历
            while (mid != null && !str.equals(mid.value)){
                mid = mid.next;
            }

            // 两种跳出条件
            if (mid == null) return false;
        }

        return true;
    }

    /**
     * 修改方法
     * @param oldValue : 被修改的值
     * @param newValue : 新值
     * @return : 修改是否成功
     */
    public boolean set(String oldValue, String newValue){
        // 如果链表本身没有存储元素
        if (isEmpty())throw new RuntimeException("list is empty");

        if (oldValue == null){// 修改的是null
             Node mid = head;

             while (mid != null && mid.value != oldValue){
                 mid = mid.next;
             }

             // 遍历到尾部跳出, 意味着没有存储过这个oldValue
             if (mid == null)return false;

             // mid 就是存储的oldValue
             mid.value = newValue;

        }else {// 修改的是普通字符串
            Node mid = head;

            while (mid != null && !oldValue.equals(mid.value)){
                mid = mid.next;
            }

            // 遍历到尾部跳出, 意味着没有存储过这个oldValue
            if (mid == null)return false;

            // mid 就是存储的oldValue
            mid.value = newValue;
        }

        return true;
    }

    /**
     * 根据下标的添加
     * @param index : 要添加的下标位置
     * @param str : 要添加的内容
     * @return:  添加是否成功
     */
    public boolean add(int index, String str){
        // 判断下标是否合法
        if (index < 0 || index > size )throw new IllegalArgumentException("parame is Illegal");

        if (index == 0){
            // 存储的是头位置
            head = new Node(str, head);
            size++;
            return true;
        }
        // 存储的位置不是头结点
        int tag = 1; // 记录遍历位置下标
        Node mid = head; // 记录遍历结点
        while (tag != index){
            tag++;
            mid = mid.next;
        }

        // 添加
        mid.next = new Node(str, mid.next);
        size++;

        return true;
    }

    /**
     * 根据下标的删除
     * @param index : 要删除的下标位置
     * @return : 被删除的元素
     */
    public String remove(int index ){
        // 链表是否为空
        if (isEmpty()) throw new RuntimeException("list is empty");
        // 下标是否合法
        if (index < 0 || index >= size )throw new IllegalArgumentException("parame is Illegal");

        // 判断要删除的是否是头结点
        if (index == 0){
            String oldValue = head.value;
            head = head.next;
            size--;
            return oldValue;
        }

        // 删除的不是头结点
        Node mid = head;
        int tag = 1;
        while (tag != index){
            mid = mid.next;
            tag++;
        }

        // 上述循环执行完成, 意味着mid是要删除结点的前一个结点 --> 要删除就是mid.next
        String oldValue = mid.next.value;

        mid.next = mid.next.next;
        size--;

        return oldValue;
    }

    /**
     * 根据下标查找
     * @param index : 下标
     * @return : 对应下标所存储的内容
     */
    public String get(int index ){
        // 链表是否为空
        if (isEmpty()) throw new RuntimeException("list is empty");
        // 下标是否合法
        if (index < 0 || index >= size )throw new IllegalArgumentException("parame is Illegal");

        Node mid  = head; // 定义遍历结点
        int tag = 0;
        while (tag != index){
            mid = mid.next;
            tag++;
        }

        // 上述循环结束, mid就是要查找的下标位置
        return mid.value;
    }

    /**
     * 根据下标的修改方法
     * @param index : 被修改的下标位置
     * @param newValue : 用来替换的值
     * @return : 被替换的旧值
     */
    public String set(int index, String newValue){
        // 链表是否为空
        if (isEmpty()) throw new RuntimeException("list is empty");
        // 下标是否合法
        if (index < 0 || index >= size )throw new IllegalArgumentException("parame is Illegal");

        Node mid = head;
        int tag = 0;

        while (index != tag){
            mid = mid.next;
            tag++;
        }

        // mid就是要替换的结点
        String oldValue = mid.value;
        mid.value = newValue;

        return oldValue;
    }

    public boolean isEmpty(){
        return  size == 0;
    }
    public int size(){
        return size;
    }

    class Node{
        String value;
        Node next;

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

用双向链表实现一个线性表

/**
 * 集合类:
 * 从使用者角度:  数据容器
 * 数据结构:  线性表
 * 底层结构:  双向链表
 */
public class MyDBLinkedList {

    private Node head;// 双向链表的头结点
    private Node end; // 双向链表的尾结点
    private int size; // 这个链表中存储了多少元素

    /**
     * 添加方法
     * @param str : 要添加元素
     * @return : 添加是否成功
     */
    public boolean add(String str){
        // 不存储null
        if (str == null) throw new IllegalArgumentException("parame is null");

        if (isEmpty()){ // 判断链表是否为空
           // 如果是空链表, 新添加的元素, 既是头结点, 又是尾结点
            head = new Node(null, str, null);
            end = head;
            size++;
            return true;
        }

        // 如果原链表不空, 意味着这个元素只需要添加到尾部即可

        Node node = new Node(end, str, null);
        end.next = node;
        end = node;
        size++;

        return true;
    }

    /**
     * 删除方法
     * @param str: 要删除的内容
     * @return : 删除是否成功
     */
    public boolean remove(String str){
        // 判断链表是否为空
        if (isEmpty()) throw new RuntimeException("list is empty");

        if (head.value.equals(str)){// 判断要删除的是不是头结点
            // 删除头结点

            // 判断链表中是否仅剩这一个结点了
            if (size == 1){
                // 删除的这个结点既是头又是尾
                head = null;
                end = null;
                size--;
                return true;

            }else{
                // 删除的仅仅是头结点, 并且后面还有元素
                head = head.next;
                head.pre = null;
                size--;
                return true;
            }
        }

        // 删除的如果不是头结点 --> 遍历, 查找要删除的结点
        Node mid = head;

        // mid的下一个元素存在, 并且mid的下一个元素存储的内容不是要删除的元素 --? 接着向后遍历
        while (mid.next != null && !mid.next.value.equals(str)){
            mid = mid.next;
        }

        // 上述循环两个跳出条件
        // 1, mid.next == null, 链表中没有这个要删除的值
        // 2, mid.next.value 就是要查找的值
        if (mid.next == null)return false;


        // 获得要删除的结点
        Node removeNode = mid.next;

        if (removeNode.next == null){
            // 说明这个删除的结点是尾结点
            end = end.pre;
            end.next = null;
            size--;
            return true;

        }else {
            // 说明删除的不是尾结点
            removeNode.pre.next = removeNode.next;
            removeNode.next.pre = removeNode.pre;
            size--;
            return true;
        }
    }


    // 根据内容的查找
    // 根据内容的替换
    

    public boolean contains(String str){
        if (isEmpty()) throw  new RuntimeException("linked is empty");

        Node mid = head;
        if (str == null){
            // mid遍历元素, 不为null, 并且mid里面存储的元素也不是要查找的元素
            while (mid != null  && mid.value != str){
                mid = mid.next;
            }
            if (mid == null) {
                // 没有找到
                return false;
            }
            return true;

        }else {
            // mid遍历元素, 不为null, 并且mid里面存储的元素也不是要查找的元素
            while (mid != null  && !str.equals(mid.value)){
                mid = mid.next;
            }
            if (mid == null) {
                // 没有找到
                return false;
            }
            return true;
        }
    }

    public boolean set(String oldValue, String newValue){
        if (isEmpty()) throw  new RuntimeException("linked is empty");

        if (oldValue == null){
            // 先找到要替换的结点, 再替换
            Node mid = head;
            // mid遍历元素, 不为null, 并且mid里面存储的元素也不是要查找的元素
            while (mid != null  && mid.value != oldValue){
                mid = mid.next;
            }
            //
            if (mid == null) return false;

            // mid就是要替换的值
            mid.value = newValue;
            return true;

        }else {

            // 先找到要替换的结点, 再替换
            Node mid = head;
            // mid遍历元素, 不为null, 并且mid里面存储的元素也不是要查找的元素
            while (mid != null  && !oldValue.equals(mid.value)){
                mid = mid.next;
            }
            //
            if (mid == null) return false;

            // mid就是要替换的值
            mid.value = newValue;
            return true;
        }
    }


    // ---------------------------------------------------------------------------

    /**
     * 根据下标的添加方法
     * @param index : 下标
     * @param str : 要添加的内容
     * @return : 添加是否成功
     */
    public boolean add(int index, String str){
        // str不是null
        if (str == null) throw new IllegalArgumentException("parame is null");
        //下标是否合法
        if (index < 0 || index > size) throw new IllegalArgumentException("index is Illegal");

        // 判断原链表是否为空
        if (isEmpty()){
            head = new Node(null, str, null);
            end = head;
            size++;
            return true;
        }

        // 走到这意味着链表必定已经存储了元素
        if ( index == 0 ){
            // 如果添加的是头结点
            Node node = new Node(null, str, head);
            head.pre = node;
            head = node;
            size++;
            return true;
        }

        if (index == size){
            // 添加到尾部
            return  add(str);
        }
        Node mid = head;

        // 添加中间位置
        if (index <= size/2){
            // 偏头位置
           mid = head;
            int tag = 1;
            while (tag != index){
                mid = mid.next;
                tag++;
            }
            // mid 是要添加位置的之前的一个位置

        }else {
            // 偏尾位置
            mid = end;
            int tag = size;
            while (tag != index){
                mid = mid.pre;
                tag--;
            }
            // mid 是要添加位置的之前的一个位置
        }

        // 要添加的元素在mid之后
        Node node = new Node(mid , str , mid.next);
        mid.next = node;
        node.next.pre = node;
        size++;

        return true;
    }

    /**
     * 根据下标的删除方法
     * @param index : 下标
     * @return :被删除的内容
     */
    public String remove(int index){
        if (isEmpty())throw new RuntimeException("list is empty");
        if (index < 0 || index >= size) throw  new IllegalArgumentException("index is Illegal");

        if (index == 0){
            // 删除的是头结点
            if (size == 1){
                // 说明这个链表中只有一个结点, 既是头又是尾
                String oldValue = head.value;
                head = null;
                end = null;
                size--;
                return oldValue;
            }else {
                // 链表存储了多个元素
                String oldValue = head.value;
                head = head.next;
                head.pre = null;
                size--;
                return oldValue;
            }
        }

        if (index == size-1){
            // 删除的是尾结点
            String oldValue = end.value;
            end = end.pre;
            end.next = null;
            size--;
            return oldValue;
        }


        Node mid = head;
        // 删除普通结点,
        if (index <= size/2){
            // 偏头位置
            int tag = 1;
            while (tag != index){
                mid = mid.next;
                tag++;
            }

        }else {
            // 偏尾位置
            int tag = size;
            mid = end;
            while (index != tag){
                mid = mid.pre;
                tag--;
            }
        }

        // mid是要查找位置的之前的一个位置
        Node removeNode = mid.next;

        removeNode.next.pre = removeNode.pre;
        removeNode.pre.next = removeNode.next;
        size--;

        return removeNode.value;
    }


    // 根据下标的查找get
    // 根据下标的替换
    
        public  String get(int index){
        if (index < 0 || index >= size) throw new IllegalArgumentException("size = " + size);

        Node mid = null;
        //  添加的不是头结点
        if (index > size/2){
            // 偏后
            mid = end;
            int tag = size - 1;
            while (tag != index){
                mid = mid.pre;
                tag--;
            }// 执行完这个循环, mid要添加位置之前的位置

        }else {
            // 偏前
            mid = head;
            int tag = 0;
            while (tag != index){
                mid = mid.next;
                tag++;
            }// 执行完这个循环, mid要添加位置的前一个位置
        }

        // mid就是要查找之前一个元素
        return mid.value;
    }


    public String set(int index, String str){
        if (index < 0 || index >= size) throw new IllegalArgumentException("size = " + size);

        Node mid = null;
        //  添加的不是头结点
        if (index > size/2){
            // 偏后
            mid = end;
            int tag = size - 1;
            while (tag != index){
                mid = mid.pre;
                tag--;
            }// 执行完这个循环, mid要添加位置之前的位置

        }else {
            // 偏前
            mid = head;
            int tag = 0;
            while (tag != index){
                mid = mid.next;
                tag++;
            }// 执行完这个循环, mid要添加位置的前一个位置
        }

        // mid就是要查找之前一个元素
        String oldStr = mid.value;
        mid.value = str;
        return oldStr;
    }



    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }


    class Node{
        String value; // 值域
        Node next;// 后指针域
        Node pre;// 前指针域

        public Node( Node pre, String value,  Node next) {
            this.value = value;
            this.next = next;
            this.pre = pre;
        }
    }
}