ArrayList、LinkedList、CopyOnWriteArrayList的区别联系

素颜马尾好姑娘i 2023-07-21 11:27 9阅读 0赞

## ArrayList和LinkedList的区别 ##

1.  **是否保证线程安全**： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
2.  **底层数据结构**： Arraylist 底层使用的是动态的Object数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。）
3.  **对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。**： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
4.  **对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针**： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
5.  **内存空间占用**： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

## ArrayList和LinkedList的应用场景如下 ##

ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况。

## CopyOnWriteArrayList的实现原理 ##

安全的原因：加了锁，并且读写分离。先加锁，再复制一份，在复制的上面进行修改，修改结束将原先数组指向修改后的数组。

1.  内部数据会被copy
2.  读写分离
3.  可能的数据延迟

**内部数据会被copy**

当调用这个类的任何有关修改的操作的时候（比如add，remove），CopyOnWriteArrayList里面整个的内容都会被重新copy一份。

**读写分离**

所以当我们做修改操作的时候，我们修改的是重新copy的一份数据同时依旧可以顺畅的迭代读取数组里面的内容。因为当我们调用iterator()函数的时候，其实得到也是一个CopyOnWriteArrayList内部内容的snapshot。

**可能的数据延迟**

这个snapshot是从iterator()调用的时刻起，被创建的，所以如果在同时有其他线程add or remove元素，这次迭代是看不到的,只有在后续操作中才可以。

源码如下：

public E remove(int index) { 
            final ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                Object[] elements = getArray();
                int len = elements.length;
                E oldValue = get(elements, index);
                int numMoved = len - index - 1;
                if (numMoved == 0)
                    setArray(Arrays.copyOf(elements, len - 1));
                else { 
                    Object[] newElements = new Object[len - 1];
                    System.arraycopy(elements, 0, newElements, 0, index);
                    System.arraycopy(elements, index + 1, newElements, index,
                                     numMoved);
                    setArray(newElements);
                }
                return oldValue;
            } finally { 
                lock.unlock();
            }
        }

应用场景：读多写少的并发场景，它读不加锁，性能很高。

缺点：

1.  **内存占用问题**，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；
2.  **无法保证实时性**，CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。
3.  **大量写操作性能极差**。

原文链接：https://blog.csdn.net/liuxiao723846/article/details/88172222

https://baijiahao.baidu.com/s?id=1643844551415985694&wfr=spider&for=pc