4.23JavaLinkList的get方法

方法描述：

根据传入的索引位置返回对应的元素---形参就是传入的索引

无查询优化：

package com.MyCollection;
​
/**
 * 新增get方法的自定义列表---version 2.0
 * @author Lucifer
 */
public class LcfLinkedList02 {
​
    /*自定义列表定义第一个节点*/
    private Node first; //开始为null
    /*定义最后一个节点*/
    private Node last; //开始为null
​
    /*定义元素总数量*/
    private int size;
​
    /*往链表加东西，定义一个add方法*/
    //"[]"--->"["a"]"
    public void add(Object obj){
        /*因为一开始节点为空，没有数据内容，所以往里面加内容---创建一个节点*/
        Node node = new Node(obj);
        /*
        这样就创建好了一个节点
        目前和链表没啥关系
         */
​
        /*判断是否是第一次往链表里面放元素*/
        if (first == null){
            /*赋值node给first*/
            first = node;
            /*赋值给last*/
            last = node;
            //注意Node类中的元素一开始是否为空
            /*
            下面继续往里面放元素
            "["a","b"]"
            第二次放入的时候first不为空了
            再建一个新对象，放入新节点
             */
        }else {
            /*将上一个节点的尾节点赋值给下一个节点的头节点*/
            node.previous = last;
            /*第二个元素的尾节点为空*/
            node.next = null;
            /*让last的下一个属性指向*/
            last.next = node;
            /*last本身指向node*/
            last = node;
        }
        size++;
    }
​
    /*get方法---根据传入的索引返回对应的值*/
    //假设有一个链表["a","b","c","d","e","f"]---现在需要取出元素c---传进来索引2，找到c
    public Object get(int index){
        if (index < 0 || index > size - 1){
            throw new RuntimeException("索引数字不合法!");
        }else {
            //定义临时节点，该节点=头节点
            Node temp = first;
            //循环头节点，反复复制给新的尾节点，返回对应节点的数据本身
            for (int i = 0; i < index; i++){
                temp = temp.next;
            /*
            假设传入2
            temp = first指向了"a"
            循环0，1---2不循环
            第0次运行完之后指向了"b",把"b"又给了temp变量
            在循环一次，指向了c,把"c"返回给了temp
            循环结束，拿到内容
            这样的方法如果数据多了以后效率就很低下---因为这是从头开始遍历查找
            考虑效率问题，可以通过二分查找然后选择部分进行遍历
             */
            }
            return temp.element;
        }
    }
​
    /*希望输出的结果可视化，重写toString方法*/
    //从first开始打印，然后依次往下找
    //假设有一个链表["a","b","c"]--->first = a, lsat = c--->最终打印要打印出a,b,c
    @Override
    public String toString(){
        /*StringBuilder方法*/
        StringBuilder sb = new StringBuilder("[");
        //TODO Auto-generated method stub
        /*定义一个零时节点*/
        Node temp = first;
        /*在这里做判断---temp不为空，打印一次*/
        while (temp != null){
            /*打印出temp，同时让temp指向尾节点*/
//            System.out.println(temp.element);
            /*再"["后＋元素*/
            sb.append(temp.element + ",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length() - 1,']');
        return sb.toString();
    }
​
    /*测试方法*/
    public static void main(String[] args) {
        /*创建对象，调用方法*/
        LcfLinkedList02 list = new LcfLinkedList02();
​
        /*使用add方法*/
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");
​
        System.out.println(list.get(3)); //因为没有重写toString方法，所以打印出来的内容是包名加数据地址(Hash码)
    }
}
​

利用二分的思想做查询优化：

package com.MyCollection;
​
/**
 * 新增get方法的自定义列表---version 2.0
 * @author Lucifer
 */
public class LcfLinkedList02 {
​
    /*自定义列表定义第一个节点*/
    private Node first; //开始为null
    /*定义最后一个节点*/
    private Node last; //开始为null
​
    /*定义元素总数量*/
    private int size;
​
    /*往链表加东西，定义一个add方法*/
    //"[]"--->"["a"]"
    public void add(Object obj){
        /*因为一开始节点为空，没有数据内容，所以往里面加内容---创建一个节点*/
        Node node = new Node(obj);
        /*
        这样就创建好了一个节点
        目前和链表没啥关系
         */
​
        /*判断是否是第一次往链表里面放元素*/
        if (first == null){
            /*赋值node给first*/
            first = node;
            /*赋值给last*/
            last = node;
            //注意Node类中的元素一开始是否为空
            /*
            下面继续往里面放元素
            "["a","b"]"
            第二次放入的时候first不为空了
            再建一个新对象，放入新节点
             */
        }else {
            /*将上一个节点的尾节点赋值给下一个节点的头节点*/
            node.previous = last;
            /*第二个元素的尾节点为空*/
            node.next = null;
            /*让last的下一个属性指向*/
            last.next = node;
            /*last本身指向node*/
            last = node;
        }
        size++;
    }
​
    /*get方法---根据传入的索引返回对应的值*/
    //假设有一个链表["a","b","c","d","e","f"]---现在需要取出元素c---传进来索引2，找到c
    public Object get(int index){
        if (index < 0 || index > size - 1){
            throw new RuntimeException("索引数字不合法!");
        }else {
            //定义临时节点，该节点=头节点
            Node temp = first;
            //运用二分法判断传入的index选择查询---类似二分查找，优化查询速度
            if (index <= (size >> 1)){
                //从一半开始查找
                for (int i = 0; i < index; i++){
                    temp = temp.next;
                }
            }else {
                for (int i = size - 1; i > index; i--){
                    temp = temp.previous;
                }
            }
            return temp.element;
        }
    }
​
    /*希望输出的结果可视化，重写toString方法*/
    //从first开始打印，然后依次往下找
    //假设有一个链表["a","b","c"]--->first = a, lsat = c--->最终打印要打印出a,b,c
    @Override
    public String toString(){
        /*StringBuilder方法*/
        StringBuilder sb = new StringBuilder("[");
        //TODO Auto-generated method stub
        /*定义一个零时节点*/
        Node temp = first;
        /*在这里做判断---temp不为空，打印一次*/
        while (temp != null){
            /*打印出temp，同时让temp指向尾节点*/
//            System.out.println(temp.element);
            /*再"["后＋元素*/
            sb.append(temp.element + ",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length() - 1,']');
        return sb.toString();
    }
​
    /*测试方法*/
    public static void main(String[] args) {
        /*创建对象，调用方法*/
        LcfLinkedList02 list = new LcfLinkedList02();
​
        /*使用add方法*/
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");
​
        System.out.println(list.get(3)); //因为没有重写toString方法，所以打印出来的内容是包名加数据地址(Hash码)
    }
}
​