【java学习】Arraylist和LinkedList使用场景与性能对比

刺骨的言语ヽ痛彻心扉 2022-08-31 11:04 204阅读 0赞

###  ###

*  介绍
 *   *  ArrayList
     *  LinkedList
     *  使用场景对比
     *  两个实例：
     *   *  二分查找
         *  插入元素
 *  总结

# 介绍 #

List 的三个子类的特点：  
ArrayList 底层结构是数组,底层查询快,增删慢。  
LinkedList 底层结构是链表型的,增删快,查询慢。  
vector 底层结构是数组 线程安全的,增删慢,查询慢。  
链表增删快，查找慢；ArrayList：基于数组实现，非线程安全的，效率高，便于索引，但不便于插入删除；Vector：基于数组实现，线程安全的，效率低，现在使用较少

ArrayList和LinkedList都实现了List接口，他们有以下的不同点：  
ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。  
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

## ArrayList ##

源码：

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
        private static final long serialVersionUID = 8683452581122892189L;
    
        /** * Default initial capacity. */
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * Shared empty array instance used for empty instances. */
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
        /** *存储ArrayList元素的数组缓冲区 *当添加第一个元素时，将扩展到默认容量。 */
        transient Object[] elementData; // non-private to simplify nested class access
            public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
      public ArrayList(Collection<? extends E> c) { 
            Object[] a = c.toArray();
            if ((size = a.length) != 0) { 
                if (c.getClass() == ArrayList.class) { 
                    elementData = a;
                } else { 
                    elementData = Arrays.copyOf(a, size, Object[].class);
                }
            } else { 
                // replace with empty array.
                elementData = EMPTY_ELEMENTDATA;
            }
        }
     public void ensureCapacity(int minCapacity) { 
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) { 
                ensureExplicitCapacity(minCapacity);
            }
        }
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

## LinkedList ##

在LinkedList 中有一个私有的内部类，定义如下：

private static class Entry { 
     Object element;
     Entry next;
     Entry previous;
     }

Linkelist可以进行的遍历操作：

for(int i = 0;i < list.size(); i++)
    
    System.out.println(list.get(i));
    
    for(String s:list)
    
    System.out.println(s);
    
    //迭代器遍历：
    
    Iterator<String>iter = list.iterator();
    while(it.hasNext())
        System.out.println(iter.next());

一些头插 尾插 获取头结点 尾结点等 方法的源码：

/** * Links e as first element. */
        private void linkFirst(E e) { 
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    
    //Links e as last element.
       void linkLast(E e) { 
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
        /** * Inserts element e before non-null Node succ. */
        void linkBefore(E e, Node<E> succ) { 
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    
        /** * Returns the first element in this list. * * @return the first element in this list * @throws NoSuchElementException if this list is empty */
        public E getFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
    
        /** * Returns the last element in this list. * * @return the last element in this list * @throws NoSuchElementException if this list is empty */
        public E getLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }

## 使用场景对比 ##

要对集合更新操作时，ArrayList 和LinkedList 哪个更适合？  
1.ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。  
2.如果集合数据是对于集合随机访问get 和set，ArrayList 绝对优于LinkedList，因为LinkedList 要移动指针。  
3.如果集合数据是对于集合新增和删除操作add 和remove，LinedList 比较占优势，因为ArrayList 要移动数据。  
ArrayList 和LinkedList 是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用ArrayList 来存储一系列的String 或者Integer。那 么ArrayList 和LinkedList 在性能上有什么差别呢？什么时候应该用ArrayList 什么时候又该用LinkedList 呢？

ArrayList 的内部实现是基于基础的对象数组的，因此，它使用get 方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList 快。LinkedList 中的get 方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList 而言，访问列表中的某个指定元素没有更快的方法了。

## 两个实例： ##

### 二分查找 ###

public class Aboutlist { 
        public static final int N=50000;//总数
        public static List values;//要查找的集合
        //放入50000个数字给value
        static { 
            Integer vals[] = new Integer[N];
            Random r = new Random();
            for(int i = 0, currval = 0; i < N; i++)
            { 
                vals[i] = new Integer(currval);
                currval += r.nextInt(100)+1;
            }
            values = Arrays.asList(vals);
        }
    
        //二分查找
        static long timeList(List list)
        { 
            long start = System.currentTimeMillis();
            for(int i = 0;i < N;i++)
            { 
                int index = Collections.binarySearch(list, values.get(i));
                if(index != i)
                    System.out.println("error");
            }
            return System.currentTimeMillis() - start;
        }
    
        public static void main(String[] args) { 
            System.out.println("Arrarlist:"+timeList(new ArrayList(values)));
            System.out.println("Linkedlist:"+timeList(new LinkedList(values)));
        }
    }

结果：  
![在这里插入图片描述][d61cd49b4397496a80cbe44b066f3cc4.png]  
但是基本上ArrayList 的时间要明显小于LinkedList 的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList 是不支持快速的随机访问的。对一个LinkedList 做随机访问所消耗的时间与这个list 的大小是成比例的。而相应的，在ArrayList 中进行随机访问所消耗的时间是固定的。这是否表明ArrayList 总是比 LinkedList 性能要好呢？这并不一定，在某些情况下LinkedList 的表现要优于ArrayList，有些算法在LinkedList 中实现 时效率更高。**比方说，利用Collections.reverse 方法对列表进行反转时，其性能就要好些**。

### 插入元素 ###

看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：

//执行大量插入操作
        static long timeList(List list)
        { 
            long start = System.currentTimeMillis();
          Object o = new Object();
          for(int i = 0;i < N;i++)
              list.add(0,o);
            return System.currentTimeMillis() - start;
        }
    
        public static void main(String[] args) { 
         
            System.out.println("Arrarlist:"+timeList(new ArrayList(values)));
            System.out.println("Linkedlist:"+timeList(new LinkedList(values)));
        }

![在这里插入图片描述][b74fc9f39aeb40e581019656e1b58417.png]

# 总结 #

ArrayList 和LinkedList 在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：  
1．对ArrayList 和 LinkedList 而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList 而言，主要是在内部数组中增加一项，指向所添加的元素，偶 尔可能会导致对数组重新进行分配；而对LinkedList 而言，这个开销是统一的，分配一个内部Entry 对象。  
2．在ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList 的中间插入或删除一个元素的开销是固定的。  
3．LinkedList 不支持高效的随机元素访问。  
4．ArrayList 的空间浪费主要体现在在list 列表的结尾预留一定的容量空间，而LinkedList 的空间花费则体现在它的每一个元素都需要消耗相当的空间  
可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList 会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList 了。

[d61cd49b4397496a80cbe44b066f3cc4.png]: /images/20220829/6d689b66d3bd4c4c882c85c7259248da.png
[b74fc9f39aeb40e581019656e1b58417.png]: /images/20220829/80c8a2cb9696415baf3b2f4c31d0c0b9.png