Collection之list源码分析

男娘i 2021-12-21 13:43 308阅读 0赞

Java中常用到ArrayList和LinkedList，面试中也常问到两者的区别，各自的使用场景。要想清楚的明白他们的区别，那还是得从源码入手。

# List接口 #

List接口中的方法有很多，但最重要的无非是增删查改，我们从ArrayList与LinkedList的实现上来讨论他们的增删查改性能问题。先列出这几个重要的方法:

public interface List<E> extends Collection<E> {
        ...
        //增
        boolean add(E e); 
        void add(int index, E element);
        //查
        E get(int index);
        //改
        E set(int index, E element);
        //删
        E remove(int index);
        boolean remove(Object o);
        ...
    }

集合的关系图如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70][]

### LinkedList与ArrayList ###

它们都实现了List接口。但是内部实现上有些区别，我们具体看下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70 2][]

插入操作

默认顺序插入

**按照默认顺序插入，两者耗费的时间都是O(1)。**

// LinkedList add操作
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        // 新建一个节点。然后让最后一个节点指向新加入的节点
        // 如果最后一个为空，那么这是第一个新插入的节点
        // 否则，节点按链表方式接在后面
         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++;
        }

// ArrayList插入
        public boolean add(E e) {
            // 确保数组的容量足够。这个方法感兴趣可以看一下。
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

指定index插入元素

**ArrayList的最坏情况下性能为O(n)，最好情况下为O（1）**  
**LinkedList在任何情况下都是O(1)**

// LinkedList
       public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
        
        // LinkedList节点的查找方法
            Node<E> node(int index) {
            // 不断的遍历索引的位置。
            // 如果index 为小于size的一半，从头遍历
            // index 大于size的一半，从尾部索引
            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;
            }
        }
        
        // 直接修改要插入
        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++;
        }

//ArrayList 。
        //需要调用 System.arraycopy 扩充数组，数组中的元素都往后挪一个位置，在底层实现上应该是进行了(n-index)次的赋值操作。
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

### 删除操作 ###

删除元素，与插入本质上是类似的，有兴趣可以阅读JDK内部实现方式。  
**ArrayList的删除操作最差情况下性能为O(n)，最好为O(1),删除最后一个元素的时候性能为O(1)**  
**LinkedList删除任何元素的性能都为O(1)**

### 搜索元素 ###

**ArrayList的搜索性能为O(1)**  
**LinkedList的搜索性能差一些，最差为O(n/2)**

//LinkedList的搜索
    public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
        
        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;
            }
        }

// ArrayList搜索
        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
        
        //直接从数组的下标拿到元素即可。
        E elementData(int index) {
            return (E) elementData[index];
        }

## ##

想要获取线程安全的List

List list = Collections.synchronizedList(new ArrayList());
    ...
    synchronized(list) {
          Iterator i = list.iterator(); // 必须在 synchronized 块中
          while (i.hasNext())
              foo(i.next());
      }

# 总结 #

*  ArrayList因为是基于动态数组去实现，在随机存取时，有着良好的性能。而增删时需要扩容，整块移动元素，所以相对较慢。但在数据量很大，顺序添加时是个例外，这种情况下它的性能优于LinkedList。
 *  LinkedList因为是基于链表实现，随机增删较快，而存取时需要遍历查询，相对于ArrayList会更慢。
 *  之后会比较下两种实现的迭代器性能。
 *  它们都不是非线程安全的。
 *  因为ArrayList要维护索引结构（下标）所以在频繁的插入和删除的时候，性能比LinkedList慢，但是也正因为有着索引下标在做查询搜索的时候，性能比LinkedList快。
 *  **使用场景：1.在频繁的插入和删除的时候，可以考虑使用LinkedList**
    
    **                  2.在频繁的搜索的时候，考虑使用ArrayList**

最后来比较下Vector、ArrayList和LinkedList

1）Vector和ArrayList

相同点：两者都是基于存储元素的数组来实现的，它们会在内存中开辟块连续的空间来存储，由于数据存储是连续的，它们支持用序号（下标）来访问元素，但是插入和删除是要移动容器中的元素，所以执行较慢。两者都有一个初始化的容量的大小，为10；当里面存储的元素超过这个大小时，就会动态的进行扩容。Vector默认扩充为原来的2倍，ArrayList默认扩充为原来的1.5倍。

区别：二者最大的区别在与synchronization（同步）的使用。在ArrayList中没有一个方法是同步的，而在Vector中，绝大部分方法都是同步的。所以Vector是线程安全的，而ArrayList不是线程安全的。由于Vector提供同步，所以性能上较低于ArrayList。

2）ArrayList和LinkedList

*  ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于双向链表的数据结构
 *  对于随机访问，ArrayList要优于LinkedList，因为LinkedList要移动指针
 *  对于插入和删除，LinkedList较占优势，ArrayList要移动数据。
 *  ArrayList和LinkedList都是非线程安全的容器

在实际使用中，若对数据的主要操作为索引或只在集合的末端增加、删除元素，使用Arraylist和vector效率比较高；若对数据的操作主要为指定位置的插入或删除操作，使用Linkedlist效率比较高；当在多线程中使用容器时（即多个线程会同时访问该容器，），选用vector较为安全。

参考：  
链接：https://www.jianshu.com/p/de271d35591c

链接：https://www.jianshu.com/p/1df64730af96

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70]: /images/20211220/8d688685e25044c0900578a41c4d65a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70 1]: /images/20211220/8189f6c93c3740df957cbec5b8177e95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW80MzA_size_16_color_FFFFFF_t_70 2]: /images/20211220/9c5a60fdb26049529ffa54462d538a23.png