ArrayList和LinkedList的优缺点和使用场景

傷城~ 2022-02-19 11:19 410阅读 0赞

参考源码,可以知道,ArrayList是用数组方式来实现的,要求内存连续.  
所以ArrayList查找数据和替换数据是很快的.也就是get(int index)和set(int index)方法  
但是ArrayList进行add(int index)和delete(int index)就很慢,因为需要在指定位置,把index后面的元素,全部都往后移动.所以除非新增删除元素是在ArrayList的末端,不然就很容易照成大量元素移动

LinkedList增加元素,删除元素,速度快;但是调用get(int index)的效率很慢,因为需要从头到尾的一个个遍历,直到指针计数=index

从ADT(抽象数据类型,abstract date type)的角度来说  
ArrayList是表的数组实现  
LinkedList是表的双向链表实现

总结:  
ArrayList适用在查找多,增删少的场景  
LinkedList适用在增删多,查找少的场景

其他人的说法:  
ArrayLIst查询效率高：ArrayLIst是连续存放元素的，找到第一个元素的首地址，再加上每个元素的占据的字节大小就能定位到对应的元素。

LinkedList插入删除效率高。因为执行插入删除操作时，只需要操作引用即可，元素不需要移动元素，他们分布在内存的不同地方，通过引用来互相关联起来。而ArrayLIst需要移动元素，故效率低。

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        transient Object[] elementData; // non-private to simplify nested class access
    
        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
    
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
        @SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }
    }

从源码得知,LinkedList查找元素的时候,需要从头到尾,或者从尾部到头部的顺序来查找元素的index

public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
        
        /**
         * Returns the (non-null) Node at the specified element index.
         */
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }