ArrayList与LinkedList

我就是我 2024-03-30 09:22 20阅读 0赞

ArrayList底层基于数组实现，LinkedList底层是基于双向链表实现的

对于随机访问时ArrayList优于LinkedList

对于插入删除操作LinkedList优于ArrayList

ArrayList的扩容机制

ArrayList在用默认方法构造时初始容量为10，如果使用参数构造时则初始容量为指定的

ArrayList的扩容方法主要是在add方法中调用,ArrayList的扩容是通过ensureExplicitCapaCity的方法去判断是否需要扩容的，如果需要扩容则调用grow方法对ArrayList进行扩容，扩容时该方法会将AarryList扩容至原始容量的1.5倍，然后将原来ArrayList的元素复制到新的ArrayList中。下面为grow方法的源码：

private void grow(int minCapacity) {
    
            // overflow-conscious code
    
            int oldCapacity = elementData.length;
    
            int newCapacity = oldCapacity + (oldCapacity >> 1);
    
            if (newCapacity - minCapacity < 0)
    
                newCapacity = minCapacity;
    
            if (newCapacity - MAX_ARRAY_SIZE > 0)
    
                newCapacity = hugeCapacity(minCapacity);
    
            // minCapacity is usually close to size, so this is a win:
    
            elementData = Arrays.copyOf(elementData, newCapacity);
    
       }

LinkedList基于链表实现就没有什么扩容机制了,但是链表底层使用JNI方法进行创建节点

回答：话说数组增删慢，链表增删快，为什么这个输出耗时链表的时间反而多呢？有谁能解释一下呢？这样的疑问

![c2eee5d4240c4e79b9bfcb4a415ed7d1.jpeg][]

本题中ArrrayList将要被扩容30多次，而LinkedList则要创建1000000个节点这就可以对比出效果了，LinkedList创建了节点在就局部性上来说是比较差的，cache的命中率是不高的。

就ArrayList中的add方法而言如果在没有扩容的情况下插入数据的时间复杂度为o（1），如果涉及到扩容它的时间复杂度则由Arrays.copyof()方法的时间复杂度决定

就增删快和查询快应该是建立在已经拥有一个ArrayList和LinkedList且里面是有数据，对里面数据需要修改时的结论，而不是目前这样，如果要进一步测试这个结论还需要以下的代码:

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    public class ArrayListandLinkList {
        public static void main(String[] args) {
            ArrayList arrayList =new ArrayList();
            LinkedList linkedList =new LinkedList();
            for(int i=0;i<10000;i++){
                arrayList.add(i);
                linkedList.add(i);
            }
            System.out.println("ArrayList调用add方法:"+getTime());
            System.out.println("LinkedList调用add方法:"+getTime1());
            System.out.println("LinkedList头插法:"+getTime2());
            System.out.println("LinkedList尾插法:"+getTime6());
            System.out.println("LinkedList0处添加" + getTime7());
            System.out.println("ArrayList按位置插入:"+getTime3());
            System.out.println("ArrayList访问时间:"+getTime4(arrayList));
            System.out.println("LinkedList访问时间："+getTime4(linkedList));
            System.out.println("ArrayList插入时间:"+getTime5(arrayList));
            System.out.println("LinkedList插入时间："+getTime5(linkedList));
        }
        public static long getTime(){
            long millis = System.currentTimeMillis();
            ArrayList arrayList =new ArrayList();
            for(int i=0;i<1000000;i++){
                arrayList.add(i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime3(){
            long millis = System.currentTimeMillis();
            ArrayList arrayList =new ArrayList();
            for(int i=0;i<1000000;i++){
                arrayList.add(i,i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime1(){
            long millis = System.currentTimeMillis();
            LinkedList linkedList =new LinkedList();
            for(int i=0;i<1000000;i++){
                linkedList.add(i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime2(){
            long millis = System.currentTimeMillis();
    
            LinkedList linkedList =new LinkedList();
            for(int i=0;i<1000000;i++){
                linkedList.addFirst(i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime4(List list){
            long millis = System.currentTimeMillis();
            for(int i=0;i<10000;i++){
                int index=Collections.binarySearch(list,list.get(i));
                if(index!=i){
                    System.out.println("Error");
                }
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime5(List list){
            long millis = System.currentTimeMillis();
            for(int i=100;i<10000;i++){
                 list.add(10,i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime6(){
            long millis = System.currentTimeMillis();
    
            LinkedList linkedList =new LinkedList();
            for(int i=0;i<1000000;i++){
                linkedList.addLast(i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
        public static long getTime7(){
            long millis = System.currentTimeMillis();
    
            LinkedList linkedList =new LinkedList();
            for(int i=0;i<1000000;i++){
                linkedList.add(0,i);
            }
            long millis1= System.currentTimeMillis();
            long time=millis1-millis;
            return time;
        }
    }

测试结果:

![86587dfe484d43aaa99426c6ac079dad.png][]

根据上述代码的测试就更加印证了LinkedList比ArrayList增加快，ArrayList比LinkedList访问快的说法，删除的话有兴趣的可以进行自测。

[c2eee5d4240c4e79b9bfcb4a415ed7d1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f7e19c584d464b79adc6d5d00e087590.jpeg
[86587dfe484d43aaa99426c6ac079dad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0cbd9a1db60a4b80898ab1d07bb46fea.png